1. Consider the following directed graph:
The number of different topological ordering of
the vertices of the graph is
Your email address will not be published. Required fields are marked *
Save my name, email, and website in this browser for the next time I comment.
2. Write the adjacency matrix representation of the
graph given in figure.
3. Let G be a directed graph whose vertex set is the
set of numbers from 1 to 100. There is an edge
from a vertex i to a vertex j iff either j = i + 1 or
j = 3i. The minimum number of edges in a path
in G from vertex 1 to vertex 100 is
4. The most efficient algorithm for finding the
number of connected components in an undirected
graph on n vertices and m edges has time
Θ(m + n)
5. 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 adjacency list of
u, and [u] in the adjacency list of v. These are
called twins of each other. A twin pointer is a
pointer from an adjacency list entry to its twin. If
|E| = m and |V| = n, and the memory size is
not a constraint, what is the time complexity of
the most efficient algorithm to set the twin pointer
in each entry in each adjacency list?
Θ(n + m)
UGC NET PAPER 1
UGC NET Management
UGC NET COMPUTER SCIENCE
UGC NET COMMERCE
GATE COMPUTER SCIENCE
CFA Level 1
Login with Facebook
Login with Google
Forgot your password?
Lost your password? Please enter your email address. You will receive mail with link to set new password.
Back to login