Maths Week 11 Graded Assignments IIT Madras

 

 

1 point

 

3. Suppose $A$ is the adjacency matrix of a connected undirected graph $G$. If $A^2=\left[\begin{array}{cccccc}1& 1& 1& 0& 1& 1\\ 1& 1& 1& 1& 0& 1\\ 1& 1& 1& 1& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1& 1\\ 1& 1& 0& 1& 1& 1\end{array}\right]$ and the shortest path between any two vertices has length at most 2, then which of the following may represent the graph $G$?

 

 

 

1 point

 

4. Suppose $G$ is a graph with 6 vertices {$0,1,2,3,4,5$} and the adjacency matrix of the graph $G$ is $A=\left[\begin{array}{cccccc}0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$. Which of the following statements is True?

 

 

The graph $G$ is a directed acyclic graph.

 

From vertex 4, every other vertex is reachable.

 

The longest path in the graph $G$ has length 4, in terms of number of edges.

 

 

The longest path in the graph is $4⟶0⟶2⟶3$

 

 

 

USE THE FOLLOWING INFORMATION FOR QUESTIONS [7-8]:
Shreya needs to perform 10 tasks namely {$A,B,C,D,\dots ..J$}. Some tasks needs to be performed after performing a particular task. In the below table, column 1 shows the tasks and column 2 shows the sets of tasks that can be performed only after performing the particular task.

                                                                                       

 

 

1 point

 

An undirected weighted graph $G$ is shown below. Find the set of all positive integer values of $x$ such that if we use Dijkstra’s algorithm, there will be a unique shortest path from vertex $a$ to vertex $j$ that contains the edge $(b,e)$.

 

 

$\{x|x\in \mathbb{Z},0<x<8\}$

 

 

$\{x|x\in \mathbb{Z},0<x<7\}$

 

 

$\{x|x\in \mathbb{Z},0<x<6\}$

 

 

$\{x|x\in \mathbb{Z},0<x<9\}$

 

 

 

1 point

 

A directed graph $G$ is shown below. Suppose we are trying to perform an algorithm to find the shortest path from vertex $v^0$ to $v^4$. Which of the following statements is (are) correct?

 

 

Dijkstra’s algorithm can be used to find the shortest path from $v^0$ to $v^4$.

 

 

Bellman-Ford algorithm can be used to find the shortest path from $v^0$ to $v^4$ because there are negative weighted edges.

 

 

The weight of the shortest path from $v^0$ to $v^4$ is $1$.

 

 

Bellman-Ford algorithm cannot be used to find the shortest path from $v^0$ to $v^4$ because there is a negative cycle in the given graph.

 

 

 

1 point

Which of the following statements is (are) INCORRECT?

 

In an undirected graph $G$, if all edges have different positive weights, then the minimum cost spanning tree of graph $G$ is unique.

 

 

If there is a cycle of weight $0$ in a directed graph $G$, then we cannot find the shortest path using Bellman-Ford algorithm.

 

 

Suppose an acyclic undirected graph $G$ with $n$ vertices has $n-1$ edges. Then the graph is connected.

 

 

In a graph $G$, every edge with the minimum weight will be in the minimum cost spanning tree.

 

 

 

(Use the following information for questions 10 & 11)

(Use the following information for questions 12 & 13)

(Use the following information for questions 14 & 15)