Undirected Graphs quiz
What is the order of growth of the memory used to represent a graph with V vertices and E edges using the adjacency-lists representation?
V
E
E + V
V
2
Submit
In a graph G represented using adjacency-lists, depth-first search marks all vertices connected to s in time proprotional to:
the number of vertices in G
the number of edges in G
the number of vertices in the connected component containing s
the sum of the degrees of the vertices in the connected component containing s
Submit
In undirected graphs, the
is connected to
relation is:
reflexive
symmetric
transitive
all of the above
Submit
Which one of the following graph-processing problems is unlikely to have an algorithm whose running time is E+V?
determine whether a graph is bipartite
determine whether a graph has an Euler cycle
determine whether a graph has a Hamilton cycle
determine whether a graph can be drawn in the plane such that no two edges cross
Submit