Test: Graphs- 1 - Computer Science Engineering (CSE) MCQ

Connected components can be found in O(m + n) using Tarjan's algorithm. Once we have connected components, we can count them.

d(r, u) and d(r, v) will be equal when u and v are at same level, otherwise d(r, u) will be less than d(r, v)

In an undirected graph, there can be maximum n(n-1)/2 edges. We can choose to have (or not have) any of the n(n-1)/2 edges. So, total number of undirected graphs with n vertices is 2^(n(n-1)/2).

P is true for undirected graph as adding an edge always increases degree of two vertices by 1. Q is true: If we consider sum of degrees and subtract all even degrees, we get an even number because every edge increases the sum of degrees by 2. So total number of odd degree vertices must be even.

A cycle of length 3 can be formed with 3 vertices. There can be total ⁸C₃ ways to pick 3 vertices from 8. The probability that there is an edge between two vertices is 1/2. So expected number of unordered cycles of length 3 = (⁸C₃)*(1/2)³ = 7

Since the given graph is undirected, every edge contributes as 2 to sum of degrees. So the sum of degrees is 2E.

n * (n - 1) / 2 when not cyclic. An acyclic graph with the maximum number of edges is actually a spanning tree and therefore, correct answer is n-1 edges. So Answer is A

Background : Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together.

1. A spanning tree has exactly V - 1 edges.
2. A single graph can have many different spanning trees. A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.
3. There can be more that one possible spanning trees of a graph. For example, the graph in this question has 6 possible spanning trees.
4. MST has lightest edge of every cutset. Remember Prim's algorithm which basically picks the lightest edge from every cutset.

Choices of this question : a) There exists a cutset in G having all edges of maximum weight : This is correct. If there is a heaviest edge in MST, then there exist a cut with all edges with weight equal to heavies edge. See point 4 discussed in above background.

b) There exists a cycle in G having all edges of maximum weight : Not always TRUE. The cutset of heaviest edge may contain only one edge. In fact there may be overall one edge of heavies weight which is part of MST (Consider a graph with two components which are connected by only one edge and this edge is the heavies) c) Edge e cannot be contained in a cycle. Not Always True. The curset may form cycle with other edges. d) All edges in G have the same weight Not always True. As discussed in option b, there can be only one edge of heaviest weight.

Below explanation is for Previous Part of this question: For vertex i to be a sink, there should be no edge from i to any other vertex.

According the input given in question,

A[i][j] = 1 means there is an edge from vertex i to j.
A[i][j] = 0 means there is no edge from i to j

For a node to i to be sink,

A[i][j] should be 0 for all j
A[j][i] should be 1 for all j.

The above pseudo code checks every vertex i for sink, starting from i = 0. It basically checks every vertex j after i for being a sink. The trick in pseudo code is, it doesn't check for j smaller than i. The i picked by this loop may not be sink. It basically makes sure that we don't ignore a potential sink. The check whether i is actually a sink or not is done later after do while loop. Vertex i is a potential sink while A[i][j] is zero Thus, E1 : !A[i][j] If the above condition is false, then i is not a sink. All j < i can also not be a sink because there is no edge from i to j. Now, the next potential sink can be j. So, E2 : i = jExplanation for this question The following pseudo code basically checks if the potential sink picked by the code above is actually a sink or not.

flag = 1;
for (j = 0; j < n; j++)
      if ((j! = i) && E3)
            flag = 0;

flag equals to 0 means i is not a sink. The code sets the flag 0 as soon as it finds out that i is not a sink.

A node i is not a sink if either of the following two conditions become true for any j not equal to i.
A[i][j] is 1 for any j
OR A[j][i] is 0 for any j

E3 : (A[i][j] | | !A[j][i]) Therefore option D is correct

A graph is connected iff all nodes can be traversed from each node. For a graph with n nodes, there will be n-1 minimum number of edges. 
Given that there are n edges, that means a cycle is there in the graph.
The simplex graph with these conditions may be:

Now we can make a different spanning tree by removing one edge from the cycle, one at a time.
Minimum cycle length can be 3, So, there must be atleast 3 spanning trees in any such Graph.

In prims algorithm we start with any node and keep on exploring minimum cost neighbors of nodes already covered.

It’s a special case in which all edge weights are equal, so dfs would work and resultant depth first tree would be the spanning tree. So the answer would be O(m+n).

It is by definition that a graph is bipartite iff it does not contain odd length cycles. So the answer is O(1).

Case 1: If the vertex we are deleting from G is an isolated vertex, which is a component by itself, then number of components in G becomes 7.
Case 2: If G is a start Graph, then by deleting the cut vertex of G, we get 19 components.
Hence, number of components in G should lie between 7 and 19.