d420 Discrete Math: Functions and Relations - Set 5 - Part 1

Correct Answer: A function that is both injective and surjective

A bijection is a function that is both injective (one-to-one) and surjective (onto), meaning every element of the domain maps to a unique element of the codomain, and all elements of the codomain are covered.

Correct Answer: Distinct elements in the domain map to distinct elements in the codomain

A function is injective if every distinct element in the domain maps to a distinct element in the codomain, meaning no two elements in the domain map to the same element in the codomain.

Correct Answer: The application of g followed by f

The composition of two functions, denoted f(g(x)), involves applying function g first and then applying function f to the result of g.

Correct Answer: Every element in the codomain is mapped by at least one element in the domain

A function is surjective (onto) if every element in the codomain is the image of at least one element from the domain.

Correct Answer: The inverse undoes the effect of the original function

A function's inverse undoes the effect of the original function, meaning that applying the function and then applying its inverse will return the original input.

Correct Answer: The function must be both injective and surjective

For a function to have an inverse, it must be bijective, meaning it is both injective (one-to-one) and surjective (onto).

Correct Answer: A logical statement whose truth value depends on one or more variables

A predicate is a logical statement that involves variables, and its truth value depends on the values assigned to those variables.

Correct Answer: It must be reflexive, symmetric, and transitive

An equivalence relation is a relation that is reflexive, symmetric, and transitive, meaning it satisfies these three properties.

Correct Answer: A reflexive relation includes self-loops for every element, while an irreflexive relation has no self-loops

A reflexive relation includes self-loops for every element in the set, while an irreflexive relation has no self-loops for any element.

Correct Answer: If a is related to b, then b is related to a

A relation is symmetric if whenever one element is related to another, the reverse relation also holds.

Correct Answer: If a is related to b and b is related to a, then a=b

A relation is antisymmetric if for all elements a and b, if a is related to b and b is related to a, then a=b.

Correct Answer: If a is related to b, and b is related to c, then a is related to c

A relation is transitive if, whenever a is related to b and b is related to c, it follows that a is related to c.

Correct Answer: A graph where edges have a direction from one vertex to another

A directed graph, also known as a digraph, has edges with directions, meaning that an edge from vertex a to vertex b is not necessarily the same as an edge from b to a.

Correct Answer: All edges have no direction, meaning connections between vertices are mutual

In an undirected graph, the edges do not have a direction, so if there is an edge between two vertices, the connection is mutual.

Correct Answer: It is a path that starts and ends at the same vertex with no repeated edges

In graph theory, a cycle is a path that starts and ends at the same vertex without repeating any edges.

Correct Answer: A sequence of vertices connected by edges, where vertices and edges can be repeated

A walk in graph theory is a sequence of vertices and edges where both vertices and edges can be repeated.

Correct Answer: It is a subgraph that contains all vertices of the original graph and is acyclic

A spanning tree is a subgraph that contains all the vertices of the original graph, but it has no cycles.

Correct Answer: A vertex with no children

In a tree graph, a leaf is a vertex that has no children, meaning it has no further vertices connected to it.

Correct Answer: The number of edges from the root to the deepest leaf

The height of a tree graph is the length of the longest path from the root to any leaf, measured in the number of edges.

Correct Answer: The graph remains connected even after any k−1 vertices are removed

A graph is k-vertex connected if it remains connected after any k−1 vertices are removed, meaning it is resilient to the removal of vertices.