Graph Theory
Q2.
Consider the following directed graph: Which of the following is/are correct about the graph?[MSQ]Q3.
Let G be a simple, finite, undirected graph with vertex set \{v_1,...,v_n\}. Let \Delta (G) denote the maximum degree of G and let N=\{1,2,...\} denote the set of all possible colors. Color the vertices of G using the following greedy strategy: for i = 1,...,n color(v_i)\leftarrow min\{ j \in N: \text{ no neighbour of } v_i \text{ is colored } j\} Which of the following statements is/are TRUE?Q4.
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace ofQ5.
The following simple undirected graph is referred to as the Peterson graph.Which of the following statements is/are TRUE?MSQQ6.
Graph G is obtained by adding vertex s to K_{3,4} and making s adjacent to every vertex of K_{3,4}. The minimum number of colours required to edge-colour G is _______Q7.
In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1. The sum of the quality-scores of all vertices on the graph shown above is ______Q8.
Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,...,100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y+ 10z = _____.Q9.
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?