I. Undirected graph do not have cross edges in DFS. But can have cross edges in directed graph. Hence True.
II. Just draw a triangle ABC. Source is A. Vertex B and C are at same level at distance 1. There is an edge between B and C too. So here |i - j| = |1 - 1| = 0.
Hence, False.

Given undirected weighted graph with distinct positive edges. Every edge weight is increased by the same value say,

P: Minimum Spanning Tree will not change ABC in both the cases.
Q: Shortest path will change because in 1st figure the path from A to C calculated as ABC but in fig.2, it is AC (Direct path).

Let vertices be A, B, C and D.
x directly connects C to D.
The shortest path (excluding x) from C to D is of weight 12 (C-B-A-D).

Applying BFS on Undirected graph give you twin pointer. Visit every vertex level-wise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.
Note: Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.

DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V²).

There are no cycles in the graph, so topological orderings do exist.
We can consider P & S as starting vertex, followed by R & Q.
Hence, PSRQ & SPRQ are the topological orderings.

One of the application of BFS algorithm is to find the shortest path between nodes u and v.
But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from W to every vertex of the graph.

Note: We should not consider backtrack edges, it reduces recursion depth in stack.
So the maximum possible recursive depth will be 19.

The possible minimum path is,
B → A, A → E, E → C.

To find the number of connected components using either BFS or DFS time complexity is θ(m+n).
Suppose if we are using Adjacency matrix means it takes θ(n²).

Check with the options:
Option A: MNOPQR
→ If queue starts with M then neighbour nodes are {N,Q,R}.
→If Q starts with M then string is not matching with neighbour nodes.
So, option A is wrong.
Option B: NQMPOR
→ Neighbours of N is ⇒ {Q,M,O}
String is not matched with neighbours.
So, option B is wrong.

→ In Spanning tree n nodes require n-1 edges. The above question they mentioned 2 disjoint spanning trees. So, it requires n-1 + n-1 =2n-2 edges. Except option D everything is correct.
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
-> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
-> Option C: True: A spanning tree covers all the vertices. So, 2 edge-disjoint spanning trees in G means, between every pair of vertices in G we have two edge-disjoint paths (length of paths may vary).

I) After visiting 'f', 'c' or 'g' should be visited next. So, the traversal is incorrect.
IV) After visiting 'c', 'e' or 'f' should be visited next. So, the traversal is incorrect.

The process to find topological order is,
(i) Go with vertex with indegree 0.
(ii) Then remove that vertex and also remove the edges going from it.
(iii) Repeat again from (i) till every vertex is completed.
Now we can see that in option (D), '3' is given first which is not possible because indegree of vertex '3' is not zero.
Hence option (D) is not topological ordering.

Option A:
d[u] Option B:
d[u] Option C:
f[u] So, option D is True.

Very difficult assume a graphs here. So, As per the GATE key they given Option D is correct answer.

In a strongly connected component every two vertices must be reachable from one to other and itis maximal component.
From given graph {P, Q, R, S, T, V} and {U} are strongly connected components.

Since, d(q) = d(p) + 1 and f(q) < f(p) which means p and q are connected and r is separate, so (D) is the answer.

From given data, we can say that the given graph is complete graph with all edge weights 1. Hence weight of MST is n-1.
Since the weights of every edge is 1 so there are different MST's are possible with same cost, i.e., (n-1).

Since every edge has distinct edge weights. So, the edge with minimum weight will definitely be present in MST.

Let us first understand what is minimum congestion actually.
Minimum congestion is the edge with maximum weight among all other edges included in the path.
Now suppose shortest path from A→B is 6, but in MST, we have A→C→B(A→C=4, C→B=3), then along the path in MST, we have minimum congestion i.e., 4.

If there is a sink in the graph, the adjacency matrix will contain all 1's (except diagonal) in one column and all 0's (except diagonal) in the corresponding row of that vertex. The given algorithm is a smart way of doing this as it finds the sink in O(n) time complexity.
The first part of the code, is finding if there is any vertex which doesn't have any outgoing edge to any vertex coming after it in adjacency matrix. The smart part of the code is E₂, which makes rows slip when there is no edge from i to it, making it impossible for them to form a sink. This is done through
E₁: A[i][j]
and
E₂: i = j
E₁ makes sure that there is no edge from i to j and i is a potential sink till A[i][j] becomes 1. If A[i][j] becomes 1, i can no longer be a sink. Similarly, all previous j can also not be a sink. Now, the next potential candidate for sink is j. So, in E₂, we must make i = j.
So, answer is (C).

First go through the explanation of previous question.
Now, the loop breaks when we found a potential sink-that is a vertex which does not have any outgoing edge to any coming after it in adjacency matrix.
So, if the column in which this vertex comes is all 1's and the row is all 0's (except diagonal), this is the sink. Otherwise there is no sink in the graph. So, E₃ is checking this condition. But in the code flag is used for storing the state that sink is present or not. And as per the usage of flag in code, by default sink is considered present.
So, the condition is E₃ must make flag = 0, if the found i is not a sink. So, the condition should be
A[i][j] | | !A[j][i]
So, option (D) is the answer.

We consider ABDF at t, they are:
The distance between A and the nodes B, D, F respectively are:
t: 1 2 3
t + 1: 3 2 3
t + 2: 3 4 3
t + 3: 5 4 5
t + 4: 5 6 5
t + 5: 7 6 7
t + 6: 7 8 7
t + 7: 9 8 9
t + 8: 9 to 10
and this continues.
So, in every two steps they get incremented by 2.
So,
at t + 99, F is 101
at t + 100, F is 101.

Breadth first search:
It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.

I) a → b → e → g → h → f (✔️)
II) a → b → f → e (✖️)
III) a → b → f → h → g → e (✔️)
IV) a → f → g → h → b → e (✔️)

Here, we have two functionalities i.e., from j to k, there exists a path then it results otherwise 0.
If there exist a path then it results
A[j,k] = max(A[j,k], A[j,i]+A[i,k])
i.e., if there exists a path from j to k, every simple path from j to k contains the atmost A[j,k] edges.

In DFS after visiting u, there is no child node then back tracking is happen and then visit the nodev. There is no need of (u,v) be an edge.

Here, vertex 2, 3, 5 are the articulation points. By removing these vertices then the graph will be disconnected.
Total no. of articulation points = 3

If a graph have n vertices and n edges (n>2) then it is to be cyclic graph. Then it have atleast one cycle and if we remove two edges then it is not connected.
For example let us consider, n=3

Forest is a graph with no cycle.
Now, '0' edges for p-1 vertices (p-1 components) and n-p edges for n-p+1 vertices (1 component).
So, total of n-p edges for p components.

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

Yes, Linear time algorithm is there for testing the planarity of finite graphs.