G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?

I. If e is the lightest edge of __some__ cycle in G, then every MST of G __includes__ e

Option 2 : II only

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, 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. 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).

Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:

I) Minimum Spanning Tree of G is always unique.

II) Shortest path between any two vertices of G is always unique.

Which of the above statements is/are necessarily true?

Option 1 : I only

**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.

Option 2 : O(m log m)

Kruskal’s algorithm is one of the algorithms used to find a minimum spanning tree of a graph G. Following are the steps for it.

- Sort all the edges according to their weight in non-decreasing order. Sorting of edges takes O(mLogm) time
- Pick the smallest edge. This step is called find-union algorithm and it takes O(mLogn) time
- If it forms a cycle with the spanning tree formed so far, skip it and move on to the next edge in the order.
- If cycle is not formed, include this edge.

- Repeat step no 2 until there are (V-1) edges in the spanning tree.

So overall complexity is O(mLogm + mLogn) time. The value of m can be atmost O(n^{2}), so O(Logn) and O(Logm) are same. Therefore, overall time complexity is O(mlogm) or O(mlogn).

**Data:**

W(MST) = 500

V = 100

Increase in weight = wt = 5

**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:**

W(MST) = x + y + w

New W(MST) = x + y + w + 5 + 5 + 5 = x + y + w + 15

**Formula:**

New W(MST) = W(MST) + wt × (V – 1)

**Calculation:**

New W(MST) = 500 + 5 × (100 – 1)

New W(MST) = 995

**Note:**

W(MST) → Weight of minimum spanning tree

New W(MST) → new Weight of minimum spanning tree

An undirected graph G (V, E) contains n (n > 2) nodes named ν_{1}, ν_{2}, ....ν_{n}. Two nodes ν_{i}, and ν_{j} are connected if and only if 0 < |i - j| ≤ 2. Each edge (ν_{i}, ν_{j}) is assigned a weight i + j.

The cost of the minimum spanning tree of such a graph with 10 nodes is :

Option 2 : 91

The correct answer is **option 2**

**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:**

- Two nodes νi, and νj are connected if and only if 0 < |i - j| ≤ 2
- Each edge (νi, νj) is assigned a weight i + j.

**Graph from the given conditions**

3 + 4 + 8 + 8 + 12 + 16 + 18 = 91

Therefore the minimum cost is 91

Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is ______

__ 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_{1} 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.

Let G be any connected, weighted, undirected graph.

I. G has a unique minimum spanning tree, if no two edges of G have the same weight.

II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.

Which of the above two statements is/are TRUE?Option 3 : Both I and II

**Concept:**

**Example:**

Graph G(V, E)

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

If edge weights are distinct then there exist unique MST.

Hence option 1 is correct

**Theorem:**

If for every cut of a graph there is a unique light edge crossing the cut then the graph has a unique minimum spanning tree, but converse may not be true.

Consider the undirected graph below:

Using Prim's algorithm to construct a minimum spanning tree starting with node a, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?

Option 3 : (a, b), (b, c), (c, i), (c, f), (f, g), (g, h), (c, d), (d, e)

The correct answer is** option 1 and option 3.**

Concept:

__Key Points__

** **

**The final sequence will be **(a, b), (b, c), (c, i), (c, f), (f, g), (g, h), (c, d), (d, e) with a cost 37.

**Another final sequence is** (a, b), (a, h), (g, h), (f, g), (c, f), (c, i), (c, d), (d, e) with a cost is 37(Two sequences possible ).

Consider the graph given below:

Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are chosen is?

Option 3 : GC, AD, GB, GA, BF, AE

**Concept****:**

Krushkal Algorithm

1. First Sort All Edges in non Decreasing order. ( Generally Uses Min Heap )

2. Delete Minimum Edge from Min heap.

3. Add it to MST if does not create a cycle else ignore it.

Repeat 2,3 until there are (V-1) edges in MST.

**Explanation****:**

__Given:__

Non-Decreasing Order will be {AD, GC, AG, GB, EA, DG, BC, BF, ED, CF}

So correct Sequence will be AD, GC, GB, GA, BF, AE

**Note****:**

1. Sequence of Equal Weight Edges can be interchanged.

2. We Assumed that BD's edge weight is greater than all the other edges in the graph. as BD's edge weights not given and considering '1' as edge weight of BD not possible with the given options.

Option 3 : No minimum spanning tree contains e_{max}

__Concept:__

__Example:__

It cannot always be the case that the edge with e_{max} should not be present in MST.

e_{max} is present in MST.

Option 4 : It may use binomial max heap to represent the priority queue

Concept:

- The first step of prim’s algorithm: Initially the roots key and nodes are initialized to zero
- Prim’s algorithm can be implemented without binary heap in O ( V
^{2}) - Prim’s algorithm can be implement with binary heap in : O ( V log V )+ O( E log V ) + O ( E ) = O (E log V )
- Prim’s algorithm can be implemented with a Fibonacci heap is: O( V log V + O ( E ) )
- Prim’s algorithm doesn’t use binomial max heap to represent the priority queue.

Hence option 4 statement is false.

Vertices set V = {1, 2, 3, 4, 5…., 100}

Edges between 1-2, 2-3, 3-4 and so on with weight 1.

Hence, the MST will have 99 edges to cover 100 vertices. The weight of the edge will be 2-1 or 3-2 or so on.

The MST will have all the edges of weight 1. Hence weight of spanning tree is 1*99 =99.Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

P: Minimum spanning tree of G does not change

Q: Shortest path between any pair of vertices does not changeOption 1 : P only

Concept:

Example:

Graph G(V, E)

Shortest path between A and C = A → B and B → C, that is,1 + 2 = 3

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

Increase the weight of G(V, E) by 10

Graph G'(V, E)

Shortest path between A and C = A → C = 20 (different path)

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

__Statement P:__ TRUE

Minimum spanning the tree of G does not change

__Statement Q:__ False

Shortest path between any pair of vertices may change

Option 4 : Θ(|V|)

**Concept:**

The Minimum Spanning Tree (MST) of a graph G(V, E) with* v* vertices has *(v-1)* edges.

**Explanation: **

T is the MST of the given graph G and now a new edge has been added to G(V, E). Now there can be two scenarios:

__Case I__:

The edge weight of newly added edge (u, v) is greater than the weight of every edge in MST. In this case, MST would not be altered. (Best Case scenario)

__Case II__:

The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ________.

Concept:

**Explanation:**

Since minimum spanning tree is given, in order to obtain a minimum sum of weights for the graph and to exclude the edge while building MST.

|AB| = max(9,2) + 1 = 10 (1 is added because weights are distinct)

|ED| = max(6,4) + 1 = 7

|CD| = max(15, 2, 7) + 1 = 16

Hence the minimum sum of weights for the graph is 36 + 10 + 7 + 16 = 69.

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_{ij} in the matrix W below is the weight of the edge {i, j}

\(W = \begin{pmatrix} 0 & 1 & 8 & 1 & 4 \\\ 1 & 0 & 12 & 4 & 9 \\\ 8 & 12 & 0 & 7 & 3 \\\ 1 & 4 & 7 & 0 & 2 \\\ 4 & 9 & 3 & 2 & 0 \end{pmatrix}\)

Option 2 : 8

The correct answer is **option 2**

__Concept:__

Graph from the Adjacency matrix:

Minimum possible weight of a path P from vertex 1 to vertex 2:

Sum of the weight = 1 + 4 + 3 = 8

So, 8 is the minimum possible wait with three edges.

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_{ij} in the matrix W below is the weight of the edge {i, j}

\(W = \begin{pmatrix} 0 & 1 & 8 & 1 & 4 \\\ 1 & 0 & 12 & 4 & 9 \\\ 8 & 12 & 0 & 7 & 3 \\\ 1 & 4 & 7 & 0 & 2 \\\ 4 & 9 & 3 & 2 & 0 \end{pmatrix}\)

Option 4 : 10

The correct answer is **option 4**

__Concept:__

__Graph from the Adjacency matrix:__

\(W = \begin{pmatrix} 0 & 1 & 8 & 1 & 4 \\\ 1 & 0 & 12 & 4 & 9 \\\ 8 & 12 & 0 & 7 & 3 \\\ 1 & 4 & 7 & 0 & 2 \\\ 4 & 9 & 3 & 2 & 0 \end{pmatrix}\)

Minimum possible weight of a spanning tree taking the vertex 0 as a leaf node:

Sum of the weight of this MST = 1 + 4 + 2 + 3 = 10

So,10 is the minimum possible weight of a spanning tree when taking vertex 0 as a leaf node

An undirected graph G(V, E) contains n (n > 2) nodes named ν_{1}, ν_{2} ν_{3}, ...ν_{n}. Two nodes v_{i},v_{j} are connected if and only if 0 < | i - j | ≤ 2. Each edge (v_{i},v_{j}) is assigned a weight i + j. A sample graph with n = 4 is shown below.

Option 3 : 31

The correct answer is **option 3.**

__Key Points__

For n=10, The graph is

Cost of the minimum spanning tree (MST) of a graph with n=10 nodes

The length of the path from ν5 to ν6 in the MST= 8+4+3+6+10 = 31

The path is V5⇒V6: (V5-V3-V1-V2-V4-V6)

An undirected graph G(V, E) contains n (n > 2) nodes named ν_{1}, ν_{2} ν_{3}, ...ν_{n}. Two nodes v_{i},v_{j} are connected if and only if 0 < | i - j | ≤ 2. Each edge (v_{i},v_{j}) is assigned a weight i + j. A sample graph with n = 4 is shown below.

Option 2 : n^{2} - n + 1

The correct answer is **option 2.**

__Key Points__

Pattern observed in weight of MST being formed:

For n=3 ⇒ (1+2+3)+(1)

For n=4 ⇒ (1+2+3+4)+(1+2)

For n=5 ⇒ (1+2+3+4+5)+(1+2+3)

For n=6 ⇒ (1+2+3+4+5+6)+(1+2+3+4)

In general, the total weight of the minimum spanning tree for n:

= \(\sum_{i=1}^{n} i + \sum_{i=1}^{n-2} i\)

=n^{2 }- n + 1

**Hence the correct answer is*** n2-n+1.*

__Alternate Method__

For n = 5, The graph is

Cost of the minimum spanning tree (MST) of a graph with n=5 nodes

only option B satisfy.

Option 4 : None of the above

The correct answer is **“option 4”.**

__CONCEPT:__

A **spanning tree** of graph G is a subset of G which has all vertices covered with the minimum possible number of edges.

Some **properties** of spanning tree are:

1. Spanning tree **doesn’t contain any cycle**.

2. Spanning tree** cannot be disconnected**.

Every connected and undirected graph G has at least** one spanning tree.**

__EXPLANATION:__

Consider graph **G** with edge weights > 1,

Consider graph **G’ **with squared edge weights of graph G,

The minimum spanning tree **(T)** of graph G is:

Minimum Spanning Tree **(T’)** of graph G’ is:

So, **T is not equal to T'and t' < t ^{2}.**

**Hence, the correct answer is "option 4".**