D420 Discrete Math: Functions and Relations - Set 4 - Part 2

Correct Answer: It is symmetric

The adjacency matrix of an undirected graph is symmetric because the graph has undirected edges, meaning the edge from A to B is the same as the edge from B to A.

Correct Answer: The number of edges incident to the vertex

The degree of a vertex is the number of edges that are incident to it, representing how many edges connect to that vertex.

Correct Answer: A graph with no loops or parallel edges

A simple graph is a graph that contains no loops (edges that connect a vertex to itself) and no parallel edges (multiple edges connecting the same pair of vertices).

Correct Answer: A vertex that is not connected to any other vertex

An isolated vertex is a vertex that has no edges connecting it to any other vertices in the graph.

Correct Answer: A circuit that visits every edge of a graph exactly once and returns to the starting vertex

An Euler circuit is a closed path that visits every edge of a graph exactly once and returns to the starting vertex.

Correct Answer: A path that visits every vertex of a graph exactly once

A Hamiltonian path is a path that visits every vertex of a graph exactly once without revisiting any vertices.

Correct Answer: Its vertex set can be divided into two disjoint sets such that no two vertices within the same set are adjacent

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.

Correct Answer: If n+1 or more objects are placed into n boxes, at least one box must contain more than one object

The Pigeonhole Principle states that if more objects than containers are available, at least one container must hold more than one object.

Correct Answer: It is an ordered arrangement of all elements in the set

A permutation of a set is an ordered arrangement of all the elements in the set.

Correct Answer: An unordered selection of r elements from the set

An r-combination of a set is an unordered selection of r elements from the set, where order does not matter.

Correct Answer: The set of all subsets of a given set

The power set of a set is the set of all its subsets, including the empty set and the set itself.

Correct Answer: The set of all elements that are in either set or in both sets

The union of two sets is the set of all elements that are in either set or in both sets.

Correct Answer: The set of elements that are in both sets

The intersection of two sets is the set of elements that are common to both sets.

Correct Answer: The set of all elements in the universal set that are not in the given set

The complement of a set is the set of all elements in the universal set that are not in the given set.

Correct Answer: The set of all ordered pairs formed by taking one element from each of two sets

The Cartesian product of two sets is the set of all ordered pairs formed by taking one element from the first set and one from the second set.

Correct Answer: A formula used to calculate the size of the union of two or more sets by subtracting the sizes of the intersections

The principle of inclusion-exclusion is a formula used to calculate the size of the union of two or more sets by subtracting the sizes of their intersections.

Correct Answer: A variable that is not bound by a quantifier

A free variable in a predicate is a variable that is not bound by a quantifier, meaning it can take on any value within its domain.

Correct Answer: A variable that is bound by a quantifier

A bound variable in a predicate is a variable that is restricted by a quantifier, meaning it is associated with a specific condition or range of values.

Correct Answer: A proposition that is always true

A tautology is a proposition that is always true, regardless of the truth values of its individual components.

Correct Answer: A proposition that is always false

A contradiction is a proposition that is always false, regardless of the truth values of its individual components.