wmw11-Graded_Assignment_Sep_2025_Mathematics_I_Qualifier (2)

Graded Assignment - (Sep 2025 - Mathematics I - Qualifier)

The due date for submitting this assignment has passed. Due on 2025-12-10, 23:59 IST. You may submit any number of times before the due date. The final submission will be considered for grading.

Last Submitted: You have last submitted on: 2025-12-10, 07:13 IST

Note: Note: This assignment will be evaluated after the deadline passes. You will get your score 48 hrs after the deadline. Until then the score will be shown as Zero.

---

Question 1

An undirected graph G has 38 vertices and the degree of each vertex is at least 7. What is the minimum number of edges that the graph G can have? Your Answer: 133

Status: Yes, the answer is correct. Score: 1

Accepted Answers:

(Type: Numeric) 133.0

---

Question 2

If G is a connected undirected graph such that every vertex has degree at most 7 , and the shortest path between any two vertices has length at most 2, then what is the maximum number of vertices in G? (Hint: Try to draw the BFS tree starting with any vertex) Your Answer: 50

Status: Yes, the answer is correct. Score: 1

Accepted Answers:

(Type: Numeric) 50

---

Question 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$?

• 
• 
• 
• 

Accepted Answers:

• 

---

Question 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$

Accepted Answers:

• The graph $G$ is a directed acyclic graph.
• From vertex 4, every other vertex is reachable.
• The longest path in the graph is $4⟶0⟶2⟶3$

---

Question 5

Which of the following sequences may represent the possible order in which Shreya can perform the tasks?

• $A,C,B,D,E,I,F,H,G,J$
• $A,D,C,B,E,I,F,H,G,J$
• $C,A,D,E,B,I,F,G,H,J$
• $D,C,A,B,E,I,F,H,G,J$

Status: Yes, the answer is correct. Score: 1

Accepted Answers:

• $A,C,B,D,E,I,F,H,G,J$
• $A,D,C,B,E,I,F,H,G,J$
• $D,C,A,B,E,I,F,H,G,J$

---

Question 6

If each task takes 5 minutes to complete and she performs all the independent tasks simultaneously, then the time(in minutes) taken by Shreya to complete all the tasks is Your Answer: 30

Status: Yes, the answer is correct. Score: 1

Accepted Answers:

(Type: Numeric) 30

---

Question 7

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\}$

Accepted Answers:

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

---

Question 8

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.

Status: Yes, the answer is correct. Score: 1

Accepted Answers:

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

---

Question 9

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.

Status: Yes, the answer is correct. Score: 1

Accepted Answers:

• If there is a cycle of weight $0$ in a directed graph $G$, then we cannot find the shortest path using Bellman-Ford algorithm.
• In a graph $G$, every edge with the minimum weight will be in the minimum cost spanning tree.

---

Question 10

An employee of that company wanted to travel from the city $C_2$ to the city $C_5$. If he travelled by the cheapest route possible, then the total fare (in thousands of rupees) he paid for flight journey was Your Answer: 15

Status: Yes, the answer is correct. Score: 1

Accepted Answers:

(Type: Numeric) 15

---

Question 11

If an inspection team member wanted to inspect all the branches of the company starting from $C_2$ and ending at $C_5$, visiting each branch exactly once, then which of the following routes should he choose in order to pay minimum fare for flight journey?

• $C_2⟶C_3⟶C_1⟶C_0⟶C_4⟶C_5$
• $C_2⟶C_1⟶C_3⟶C_4⟶C_0⟶C_5$
• $C_2⟶C_3⟶C_1⟶C_4⟶C_0⟶C_5$
• Such a route is not possible.

Accepted Answers:

• $C_2⟶C_1⟶C_3⟶C_4⟶C_0⟶C_5$

---

Question 12

What is the total maintenance cost (in hundreds of rupees) of the optimum subset of links? Your Answer: 15

Status: Yes, the answer is correct. Score: 1

Accepted Answers:

(Type: Numeric) 15

---

Question 13

Find the number of different ways of choosing an optimum subset of links for the given graph. Your Answer: 1

Accepted Answers:

(Type: Numeric) 4

---

Question 14

Suppose we perform Prim’s algorithm on the graph $G$ starting from vertex $A$ to find an MCST. Then the order in which the vertices are added is

• $A,C,F,G,B,D,E$
• $A,B,D,E,G,C,F$
• $A,B,G,C,F,D,E$
• $A,C,F,G,E,D,B$

Status: Yes, the answer is correct. Score: 1

Accepted Answers:

• $A,B,G,C,F,D,E$

---

Question 15

Suppose we perform Kruskal’s algorithm on the graph $G$ starting from vertex $C$ to find an MCST. Which of the following edges are not added to the minimum cost spanning tree?

• $(A,E)$
• $(B,D)$
• $(G,F)$
• $(A,G)$

Status: Yes, the answer is correct. Score: 1

Accepted Answers:

• $(A,E)$
• $(G,F)$

---