Graph Theory Practice Questions

Let X be the adjacency matrix of a graph G with no self loops. The entries along the principal diagonal of X are

The $2^{n}$ vertices of graph G correspond to all subsets of a set of size n, for $n\geq 6$ . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in G is

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G=(V,E) with |V| divisible by 3 and DHAM3 be the problem of determining if a Hamltonian cycle exists in such graphs. Which one of the following is true?

Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?

If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a

Let T be a depth first search tree in a undirected graph G Vertices u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?

The $2^{n}$ vertices of graph G correspond to all subsets of a set of size n, for $n\geq 6$ . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in G is

The $2^{n}$ vertices of graph G correspond to all subsets of a set of size n, for $n\geq 6$ . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in G is

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that

Which one of the following statements is TRUE about the graph?

Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is,

A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G. i = 0; do { j = i + 1; while ((j < n) && E1) j++; if (j < n) E2; } while (j < n); flag = 1; for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0; if (flag) printf("Sink exists") ; else printf ("Sink does not exist"); Choose the correct expression for $E_3$ and $E_2$ .

A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G. i = 0; do { j = i + 1; while ((j < n) && E1) j++; if (j < n) E2; } while (j < n); flag = 1; for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0; if (flag) printf("Sink exists") ; else printf ("Sink does not exist"); Choose the correct expression for $E_3$ .

Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. then, the size of the maximum independent set of G is:

In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

Let G1=(V, E1) and G2=(V, E2) be connected graphs on the same vertex set V with more than two vertices. If G1 $\cap$ G2 = (V, E1 $\cap$ E2) is not a connected graph, then the graph G1 $\cup$ G2 = (V, E1 $\cup$ E2)

What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same colour, is

How many graphs on n labeled vertices exist which have at least $\frac{(n^{2}-3n)}{2}$ edges ?

What is the maximum number of edges in an acyclic undirected graph with n vertices?

Let G = (V,E) be a direction graph with n vertices. A path from $v_{i}$ to $v_{i}$ in G is sequence of vertices ( $v_{i}$ , $v_{i+1}$ ,....., $v_{j}$ ) such that ( $v_{k}$ , $v_{k+1}$ ) $\in$ E for all k in i through j - 1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follows.

Consider the following algorithm for i = 1 to n for j = 1 to n for k = 1 to n A [j , k] = max (A[j, k] (A[j, i] + A [i, k]); Which of the following statements is necessarily true for all j and k after terminal of the above algorithm?