Graphs · Data Structures · GATE CSE

Breadth First Search $$(BFS)$$ is started on a binary tree beginning from the root vertex. There is a vertex $$t$$ at a distance four from the root. I...

Consider the following directed graph: The number of different topological orderings of the vertices of the graph is ________________....

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented a...

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only...

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a ...

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

Consider the following graph among the following sequences I. a b e g h f II. a b f e h g III. a b f h g e IV. a f g h b e What are depth first t...

Let G = (V, E) be a directed, weighted graph with weight function w: E $$ \to $$ R. For some function f: V $$ \to $$ R, for each edge (u, v) $$ \in $$...

Let $$G$$ be a simple undirected graph. Let $${T_D}$$ be a depth first search tree of $$G.$$ Let $${T_B}$$ be a breadth first search tree of $$G.$$ Co...

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

In an adjacency list representation of an undirected simple graph $$G = (V,E),$$ each edge $$(u, v)$$ has two adjacency list entries: $$[v]$$ in the a...

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For $$x \in V$$, let d(x) denote the shortest dista...

Let $$G$$ be a connected undirected graph of $$100$$ vertices and $$300$$ edges. The weight of a minimum spanning tree of $$G$$ is $$500.$$ When the w...

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be th...

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry Wij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\mat...

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry Wij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\mat...

Consider the following sequence of nodes for the undirected graph given below. 1.a b e f d g c 2.a b e f c g d 3.a d g e b c f 4.a d b c g e f A ...

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

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

Let T be a depth first search tree in an 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...

Let T be a depth-first search tree in an 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...

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths o...

How many undirected graphs (not necessarily connected) can be constructed out of a given set V = { v1,v2,........,vn } of n vertices?...

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and le...