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

Correct Answer: A graph where each vertex is connected to every other vertex

A complete graph is one where every vertex is directly connected to every other vertex.

Correct Answer: The number of edges coming from it

The degree of a vertex is the number of edges that are connected to it.

Correct Answer: A graph that can be divided into two groups, where no vertices in the same group are connected

In a bipartite graph, the vertices can be split into two groups such that edges only connect vertices from different groups.

Correct Answer: It is a circuit that visits every edge exactly once

An Euler circuit is a closed path in a graph that travels along each edge exactly once.

Correct Answer: If n items are put into m containers and n>m, then at least one container must contain more than one item

The Pigeonhole Principle states that when there are more items than containers, at least one container must hold more than one item.

Correct Answer: The complement of 1 is 0

In Boolean algebra, the complement of 1 is 0, and the complement of 0 is 1.

Correct Answer: Boolean multiplication

Boolean multiplication corresponds to the logical AND operation, where the result is true only if both operands are true.

Correct Answer: False when both inputs are true

The XOR operation is true when the inputs differ and false when the inputs are the same.

Correct Answer: The product of sums of literals

In conjunctive normal form, a Boolean expression is represented as the product of sums of literals.

Correct Answer: The expression is always true

A tautology in Boolean algebra is an expression that is always true, regardless of the values of the variables.

Correct Answer: De Morgan's Law

De Morgan's Law is used to simplify Boolean expressions by transforming the negation of conjunctions and disjunctions.

Correct Answer: It finds a minimum spanning tree by adding increasing cost arcs

Kruskal's algorithm is a greedy algorithm that finds the minimum spanning tree of a graph by adding edges in increasing order of cost.

Correct Answer: The logical OR of the variables

Boolean addition corresponds to the logical OR operation, where the result is true if at least one of the variables is true.

Correct Answer: To represent the edges between vertices in a graph

An adjacency matrix is used to represent a graph by showing which pairs of vertices are connected by edges.

Correct Answer: The dot product of row i from matrix A with column j from matrix B

The matrix product is computed by taking the dot product of rows from one matrix and columns from another.

Correct Answer: Each element in the domain maps to a unique element in the codomain

An injective function ensures that no two distinct elements in the domain map to the same element in the codomain.

Correct Answer: A function that is injective and surjective

A bijective function is both injective (one-to-one) and surjective (onto), meaning every element in the domain maps to a unique element in the codomain, and every element in the codomain is mapped.

Correct Answer: Every element in the codomain has at least one preimage

A surjective function ensures that every element in the codomain is the image of at least one element from the domain.

Correct Answer: The set of all images of the elements in the domain

The range of a function is the set of all images (outputs) of the elements in the domain.

Correct Answer: If a statement is true for a base case and holds for n+1 when it holds for n, then it is true for all n

The Principle of Mathematical Induction is used to prove statements for all natural numbers by showing that the base case holds and that the statement holds for n+1 when it holds for nnn.