Question 1 |

Let G=(V,E) be an undirected unweighted connected graph. The diameter of G is defined as:

diam(G)=\displaystyle \max_{u,v \in V} \{ \text{the length of shortest path between }u \text{ and }v \}

Let M be the adjacency matrix of G.

Define graph G_2 on the same set of vertices with adjacency matrix N, where

N_{ij}=\left\{\begin{array} {lcl} 1 &\text{if}\; M_{ij}>0 \text{ or } P_{ij}>0, \text{ where }P=M^2\\0 &\text{otherwise} \end{array}\right.

Which one of the following statements is true?

diam(G)=\displaystyle \max_{u,v \in V} \{ \text{the length of shortest path between }u \text{ and }v \}

Let M be the adjacency matrix of G.

Define graph G_2 on the same set of vertices with adjacency matrix N, where

N_{ij}=\left\{\begin{array} {lcl} 1 &\text{if}\; M_{ij}>0 \text{ or } P_{ij}>0, \text{ where }P=M^2\\0 &\text{otherwise} \end{array}\right.

Which one of the following statements is true?

diam(G_2)\leq \left \lceil diam(G)/2 \right \rceil | |

\left \lceil diam(G)/2 \right \rceil \lt diam(G_2) \lt diam(G) | |

diam(G_2) =diam(G) | |

diam(G) \lt diam(G_2) \leq 2 \; diam(G) |

Question 1 Explanation:

Question 2 |

Let G=(V,E) be a directed, weighed graph with weight function w:E\rightarrow \mathbb{R}. For some function f:V\rightarrow \mathbb{R}, for each edge (u,v) \in E, define w'(u,v) as w(u,v)+f(u)-f(v).

Which one of the options completes the following sentence so that it is TRUE?

"The shortest paths in G under w are shortest paths under w' too,_________".

Which one of the options completes the following sentence so that it is TRUE?

"The shortest paths in G under w are shortest paths under w' too,_________".

for every f:V\rightarrow \mathbb{R} | |

if and only if \forall u \in V,f(u) is positive | |

if and only if \forall u \in V,f(u) is negative | |

if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every verex of G |

Question 2 Explanation:

Question 3 |

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?

(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?

(I) only | |

(II) only | |

Both (I) and (II) | |

Neither (I) nor (II) |

Question 3 Explanation:

Question 4 |

Consider the weighted undirected graph with 4 vertices,where the weigh to edge {i, j} is given by the entry Wij in the matrix W.

W=\begin{bmatrix} 0 & 2&8 & 5\\ 2& 0& 5 &8 \\ 8 & 5 & 0& x\\ 5&8 & x&0 \end{bmatrix}

The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ____.

W=\begin{bmatrix} 0 & 2&8 & 5\\ 2& 0& 5 &8 \\ 8 & 5 & 0& x\\ 5&8 & x&0 \end{bmatrix}

The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ____.

8 | |

10 | |

12 | |

13 |

Question 4 Explanation:

Question 5 |

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increasedby 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 change

P: Minimum spanning tree of G does not change

Q: Shortest path between any pair of vertices does not change

P only | |

Q only | |

Neither P nor Q | |

Both P and Q |

Question 5 Explanation:

There are 5 questions to complete.