A bipartite graph is a type of graph where the vertex set can be divided into two disjoint sets, and every edge connects a vertex from one set to a vertex from the other set. No edge connects vertices within the same set.
Which of the following is the correct formula for the number of edges in a complete graph with n vertices?
A n² – 1
B n(n+1)/2
C n(n-1)/2
D n²
In a complete graph with n vertices, each vertex is connected to every other vertex. The number of edges is given by the formula n(n 1)/2, as each edge connects two distinct vertices.
What is the result of a set intersection?
A Difference between sets
B All elements in A
C All elements in both sets
D Common elements of sets
The intersection of two sets A and B, denoted as A ∩ B, includes only the elements that are common to both sets. It represents the overlap between the two sets.
What is the value of the expression: (A OR B) AND (NOT A)?
A NOT A
B B
C A
D A AND B
The expression (A OR B) AND (NOT A) simplifies to B. This is because the condition “NOT A” eliminates A, leaving only B. Thus, the result is equivalent to B.
What is the degree of a vertex in a graph?
A Length of edges
B Number of edges
C Number of paths
D Number of adjacent vertices
The degree of a vertex in a graph is the number of edges connected to that vertex. It represents the number of adjacent vertices to the given vertex, indicating how connected it is within the graph.
Which of the following is true for a tree in graph theory?
A It is a connected graph with no cycles
B It contains exactly one cycle
C It is a disconnected graph
D It contains cycles
A tree is a type of graph that is connected and contains no cycles. It is a special type of acyclic graph where there is exactly one path between any two vertices.
What is the characteristic of a recurrence relation?
A Describes paths in graphs
B Defines sets of values
C Defines terms by previous terms
D Solves linear equations
A recurrence relation defines each term in a sequence based on the previous terms. It provides a way to express complex sequences in terms of simpler ones, often used in combinatorics and algorithm analysis.
What is the Boolean expression for “NOT A AND (B OR C)”?
A (NOT A OR B) AND C
B (NOT A) AND (B OR C)
C A AND (B OR C)
D (NOT A) AND B AND C
The Boolean expression “NOT A AND (B OR C)” evaluates as true if A is false and at least one of B or C is true. This follows the precedence of operations, where NOT is evaluated first, then AND and OR.
In graph theory, what is the concept of an Eulerian path?
A A path that visits every edge exactly once
B A cycle that visits every vertex
C A path with no cycles
D A path that visits every vertex
An Eulerian path in a graph is a path that visits every edge exactly once. A graph must meet certain conditions, such as having exactly zero or two vertices with an odd degree, for it to contain an Eulerian path.
What is the result of a logical NOR operation?
A True if both inputs are true
B True if any input is true
C False if any input is true
D False if both inputs are false
The NOR operation is the negation of the OR operation. It returns true only when both inputs are false. If any of the inputs is true, the result of NOR will be false.
In combinatorics, how many ways can 3 objects be arranged in a row?
A 6
B 3!
C 9
D 3
The number of ways to arrange 3 objects in a row is calculated by 3 factorial (3!). This equals 3 × 2 × 1 = 6, representing all possible permutations of the 3 objects.
Which operation is used to combine two sets to form a new set of all distinct elements?
A Difference
B Complement
C Union
D Intersection
The union of two sets includes all distinct elements from both sets. It is denoted by A ∪ B and combines elements from set A and set B, removing any duplicates.
What is the primary characteristic of a directed acyclic graph (DAG)?
A All vertices are connected
B Contains cycles
C Edges have no direction
D Edges have a direction
A directed acyclic graph (DAG) is a type of graph where edges have a direction, indicated by an arrow, and there are no cycles, meaning no vertex can be reached again by following the direction of the edges.
What is the result of the set difference A – B?
A Elements in A but not in B
B Elements in B but not in A
C Elements in neither A nor B
D Elements in both A and B
The set difference A – B consists of elements that are in set A but not in set B. It is also referred to as the relative complement of B in A, denoted by A \ B.
Which of the following is true for a complete bipartite graph K₍ₘ,ₙ₎?
A It contains exactly m edges
B It contains no edges
C Every vertex is connected to every other vertex
D Vertices are divided into two disjoint sets
A complete bipartite graph K₍ₘ,ₙ₎ consists of two disjoint sets of vertices, with every vertex in one set connected to every vertex in the other set. It does not contain edges within the same set.