Prasnya

Continue with Google

Loading

IITM BS Week 10 Mathematics 1 Questions | Prasnya

Mathematics 1 > Week 10

All PYQs

Topic Wise PYQs Start Weekly Test

28Q

Consider the directed graph given below: Suppose we perform BFS/DFS so that when we visit a vertex, we explore its unvisited neighbours in a random order. Which of the following options are correct?

Multiple correct

u

is called a root vertex of a directed graph if there is a directed path from

u

to every other vertex in the graph. Below is a directed graph

G

with the vertex set

\{0, 1, 2, 3, 4, 5\}

. Find the root vertex of

G

Suppose we obtain the following BFS tree rooted at node

A

for an undirected graph with vertices

\{A, B, C, D, E, F, G\}

. Which of the following cannot be an edge in the original graph?

21 December 2025

Consider the adjacency matrix of a graph

G

. Which of the following option(s) is/are true?

Multiple correct

21 December 2025

Consider the following directed graph: Which of the following orderings can be a valid topological sort of the graph?

Multiple correct

21 December 2025

Two families have decided to enter into an alliance by marriage. The first family has 4 sons (

S_1, S_2, S_3, S_4

) and the second family has 4 daughters (

D_1, D_2, D_3, D_4

). To avoid impropriety, the families insist that each one must marry someone either their own age, or someone one position younger or older. The graph representing these agreeable marriages is given below. How many different acceptable marriage arrangements are possible?

21 December 2025

G

is a graph, as shown in the below figure. Let

V

be the set of vertices of

G

V_i

be the maximum independent set and

V_c

be the minimum vertex cover. Which of the following is(are) true?

Multiple correct

Consider the graph given below. Which of the following option(s) is/are true?

Multiple correct

What is the minimum number of colors required to properly color the vertices of the given graph such that no two adjacent vertices share the same color?

Consider the adjacency matrix of an undirected graph

G

. Which of the following option(s) is/are true?

Multiple correct

22 December 2024

A company manufactures 10 chemicals

x_1, x_2, \dots, x_{10}

. Certain pairs of these chemicals are incompatible and would cause explosions if brought into contact with each other. The below graph shows the incompatibility of the chemicals, each vertex represents a chemical and each edge between a pair of chemicals represents that those two chemicals are incompatible. As a precautionary measure, the company wishes to partition its warehouse into compartments and store incompatible chemicals in different compartments. What is the least number of compartments into which the warehouse should be partitioned?

22 December 2024

Consider the following adjacency matrix of a graph

G

. Which of the following options is/are correct?

Multiple correct

01 September 2024

What is the minimum number of colours required to colour the graph given below?

01 September 2024

Suppose we obtain the following BFS tree rooted at node

A

for an undirected graph

G

\{A, B, C, D, E, F, G\}

. Which of the following cannot be an edge in

G

01 September 2024

The DFS (Depth First Search) tree of a graph starting with vertex

A

is shown below. Choose the option which might be the original graph.

What is the minimum number of colors required to color the graph

G

What is the size of the minimum vertex cover of graph

G

Which of the following options is/are true?

Use the below graph to answer the following question. Which of the following is/are the DFS tree starting from vertex 1 of the given graph?

Multiple correct

24 December 2023

Consider the given graph: Which of the following options is/are true?

Multiple correct

24 December 2023

Shreya needs to perform 10 tasks namely {A, B, C, D, E, F, G, H, I, J}. Some tasks need to be performed after performing a particular task. The below graph shows the dependency of tasks. Which of the following sequences may represent the possible order in which Shreya can perform the tasks?

Multiple correct

24 December 2023

Let G be a simple graph with the vertex set {1, 2, 3, 4, 5, 6}. Suppose two distinct vertices, say i and j, of G are adjacent if and only if gcd(|i - j|, 3) = 1. Find the number of edges in the graph G?

11 December 2022

Two families have decided to enter into an alliance by marriage. The first family has 4 sons (

S_1, S_2, S_3, S_4

) and the second family has 4 daughters (

D_1, D_2, D_3, D_4

). To avoid impropriety, the families insist that each one must marry someone either their own age, or someone one position younger or older. The graph representing these agreeable marriages is given below.

11 December 2022

G

is a graph with 6 vertices

0, 1, 2, 3, 4, 5

and the adjacency matrix of graph

G

A = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix}

Which of the following statements is INCORRECT?

11 December 2022

An IT convention is being organized in a fancy hotel. Many parallel sessions are planned. Each session has to take place in a separate hall. Sessions that do not overlap can share a hall. The organizer of the convention would like to know the minimum number of halls to reserve at the hotel to fit in all the sessions without any clashes. The organizer decides to model this as a graph where the nodes are the sessions and edges represent pairs of sessions with overlapping timings. In this setting, the graph theoretic question to be answered is:

Suppose a tree has two vertices of degree 4, two vertices of degree 3, and three vertices of degree 2. If all the other vertices have degree 1, then how many vertices are there in the graph?

Find the number of cross edges in the DFS tree.

Which of the following statements are correct?

Showing 28 questions.

Complete question index for this section:

Question 1 (multiple):
Question 2 (integer):
Question 3 (single):
Question 4 (multiple):
Question 5 (multiple):
Question 6 (integer):
Question 7 (multiple):
Question 8 (multiple):
Question 9 (integer):
Question 10 (multiple):
Question 11 (integer):
Question 12 (multiple):
Question 13 (integer):
Question 14 (single):
Question 15 (single):
Question 16 (integer):
Question 17 (integer):
Question 18 (comprehension):
Question 19 (multiple):
Question 20 (multiple):
Question 21 (multiple):
Question 22 (integer):
Question 23 (integer):
Question 24 (single):
Question 25 (single):
Question 26 (integer):
Question 27 (comprehension):
Question 28 (comprehension):