ximum number of edges that can exist in an undirected graph? Why? Explain.
*Data Structures and
Question:
Answer the following questions about graphs.
(a) What is the maximum number of edges that can exist in an undirected graph? Why? Explain.
(b) What is a cycle in a directed graph?
(c) Given a graph G(V, E), its inverse consists of a graph G′ where the edges of the original graph is inverted. That is, for all (u, v) ∈ G.E, ∃(v, u) ∈ G′ .E. Describe a nonempty directed graph G such that G = G′ .
(d) Topological sorting in a directed graph is a linear ordering of its vertices. Does existence of a cycle in a graph violate a topological sorting? Why/why not?
(e) Depth First Search can be used as a subroutine to solve other problems, topological sorting being an example of this. Explain the intuition behind using DSF in the calculation of topological sort. (Note: I'm not asking you about how DFS is used in topological sorting. Rather, I'm asking what is needed to topologically sort graphs and how DFS becomes useful to achieve this)
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 3 images
