Graphs/Spanning Tree and Shortest Paths MCQ Quiz - Objective Question with Answer for Graphs/Spanning Tree and Shortest Paths - Download Free PDF

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Explanation:

Edge set for the given graph = {2, 3, 4, 5, 6, 7, 8}

For 5 vertices, we need 4 edges in MST,

So, edge set for MST = {2, 3, 4, 6}

Minimum spanning tree

Minimum cost 2 + 3 + 4 + 6 = 15

The correct answer is DFS

Key Points

• Depth-First Search is typically implemented using a stack data structure. The algorithm explores as far as possible along each branch before backtracking. The stack helps in keeping track of the vertices to be visited, allowing the algorithm to backtrack efficiently.
• Breadth-First Search (BFS) is commonly implemented using a queue data structure.

The correct answer is option 1: queue

Key Points

• Breadth First Traversal (BFS) is a graph traversal technique that visits all the vertices of a graph in breadthward motion, i.e., level by level.
• BFS uses a queue data structure to keep track of the vertices that need to be explored next.
• Once a node is visited, all of its adjacent unvisited vertices are added to the queue.

Additional Information

• Stack is used in Depth First Search (DFS), not BFS.
• List or doubly linked list may be used for adjacency representation but not directly for traversal control in BFS.
• Queue ensures FIFO order, which is essential for BFS to maintain level-order traversal.

Therefore, the correct answer is: option 1: queue

The correct answer is option 1: nⁿ⁻²

Key Points

• The number of spanning trees in a **complete undirected graph** with n nodes is given by **Cayley’s formula**:
• This applies specifically to **complete graphs**, where every pair of distinct vertices is connected by a unique edge.

Examples:

• For n = 3 → spanning trees
• For n = 4 → spanning trees

Additional Information

• Option 2 (1): Only true for trees with exactly n − 1 edges, not for complete graphs.
• Option 3 (0): Invalid; a complete graph always has spanning trees if n ≥ 2.
• Option 4 (n/2): Not mathematically correct or relevant to spanning trees.

Hence, the correct answer is: option 1: nⁿ⁻²

The correct answer is Greedy algorithm.

Key Points

• Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights.
• It finds the shortest path from the source node to all other nodes in the graph.
• Dijkstra's algorithm follows the Greedy algorithm paradigm, where it makes a series of choices, each of which looks best at the moment, to find the shortest path.
• It maintains a set of nodes whose shortest distance from the source is already known and repeatedly selects the node with the smallest known distance.

Additional Information

• Branch and bound is a general algorithm for finding optimal solutions of various optimization problems, particularly in discrete and combinatorial optimization. It is not specifically used in Dijkstra's algorithm.
• Backtracking is a general algorithm for finding solutions by trying partial solutions and then abandoning them if they are not suitable. It is used in problems like the N-Queens problem, but not in Dijkstra's algorithm.
• Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is used in algorithms like the Floyd-Warshall algorithm, but Dijkstra's algorithm does not use this paradigm.

Answer:3 to 3

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Explanation:

The minimum weight in the graph is 0.1 choosing this we get.

Suppose we get two trees T₁ and T_2.

To connect to those two trees we got 3 possible edges of weight 0.9.

Hence we can choose any one of those 3 edges.

No of Minimum weight spanning tree is 3.

• Breadth-first search (BFS) and Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures.
• Depth First Search (DFS) uses Stack data structure. DFS uses backtracking technique. Remember backtracking can proceed by Stack.
• Breadth First Search (BFS) algorithm traverses a graph in a breadthwise manner and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

• Breadth-first search (BFS) and Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures.
• Breadth First Search (BFS) algorithm traverses a graph in a breadthwise manner and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.
• Depth First Search (DFS) uses Stack data structure. DFS uses backtracking technique. Remember backtracking can proceed by Stack.

At a distance four from the root, tree will be like:

In this tree, maximum possible value of n at a distance 4 from the root is 31.

Alternate solution:

A tree with height h has maximum number of nodes = 2^h+1 – 1

Here it is given that t is the nth vertex at a distance 4. We have to find the maximum value of n.

Here height = 4

Maximum value of n = 2⁴⁺¹ – 1 = 31

Prim's algorithm: spanning Tree

Dijkstra's algorithm: single source shortest path

Bellman ford algorithm: single source shortest path

Floyd warshalls algorithm: all pair shortest path

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Explanation:

Edge set for the given graph = {2, 3, 4, 5, 6, 7, 8}

For 5 vertices, we need 4 edges in MST,

So, edge set for MST = {2, 3, 4, 6}

Minimum spanning tree

Minimum cost 2 + 3 + 4 + 6 = 15

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Example:

Graph G(V, E)

G(V, V – 1) → minimum spanning tree

If edge weights are distinct then there exist unique MST.

Hence Statement I is correct.

When edge weights are distinct and positive in that case shortest path between any two vertices of the graph is not always unique. Shortest path can be different even if the edge weights are unique.

Example:

Distance between A → C (3) and A → B → C (1 + 2 = 3), both paths has same distance.

Hence statement II is incorrect.

I. If e is the lightest edge of some cycle in G, then every MST of G includes e          (INCORRECT)

Let G = (V, E) is a graph with 4 vertices and 5 edges. 

Here, cycle contains the edge weights (3, 4, 5) but edge weight 3 is not included in the MST.

So, according to the cut-property of MST if is the lightest edge of some cycle in G, then every MST of G may or may not include e.

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e          (CORRECT)

According to the cycle property of MST, same example as above. Here, cycle contains the edge weights (1, 2, 3)  and 3 is the heaviest so edge weight 3 is excluded in the MST.

If there is heaviest edge in cycle, then we will exclude it from the MST because there are other low-cost edges are available to include in MST (because edge weights are distinct here).

Concept:

This graph doesn’t have any cycle, hence there must exist a topological ordering.

R has an indegree from P and S. Q has indegree from P, R and S. Hence,

1. P and S must appear R in the topological ordering.
2. P, S, R must appear before Q in the topological ordering.
3. Sequence of P and S has no indegree can be interchanged.

Therefore, the valid topological orders are PSRQ and SPRQ.

Explanation:

For topological ordering, the starting vertex must have 0 indegree. Hence, any one from P or S can be chosen.

If we choose P, then we need to choose the next vertex with indegree only from P. Hence, S is chosen.

After P and S, we choose a vertex with indegree only from P and S. Hence. R then Q.

Same could be performed with S instead of P.

Concept:

A spanning tree is a subset of Graph G, which has all the vertices covered with the minimum possible number of edges. Spanning tree doesn’t have cycles and it cannot be disconnected.

Formula:

Number of spanning trees possible with n nodes = nn-2

Calculation:

Here, the number of vertices is 7.