Maximum number edges to make Acyclic Undirected/Directed Graph

Given- Given V vertices, what is the maximum number of edges can be added to make Acyclic Undirected Graph. Follow up – what is the maximum number of edges that can be added to make Acyclic Directed Graph.

Example: 

Approach:

For Undirected Graph – It will be a spanning tree (read about spanning tree) where all the nodes are connected with no cycles and adding one more edge will form a cycle. In the spanning tree, there are V-1 edges. 

For Directed Graph – Construct the graph similar to topological order  (Read about topological order – where all the edges go to one direction and there will not be any circular dependency, means there is no cycle). Take the first vertex and have a directed edge to all the other vertices, so V-1 edges, second vertex to have a directed edge to rest of the vertices so V-2 edges, third vertex to have a directed edge to rest of the vertices so V-3 edges, and so on. This will construct a graph where all the edges in one direction and adding one more edge will produce a cycle. 

So the total number of edges = (V-1) + (V-2) + (V-3) +———+2+1 = V(V-1)/2. (sum of first N natural numbers is N(N+1)/2)

Complete Code:

Output:

Maximum edges to make Acyclic Undirected Graph with 3 vertices are: 2
Maximum edges to make Acyclic Directed Graph with 3 vertices are: 3
---------------------------------
Maximum edges to make Acyclic Undirected Graph with 4 vertices are: 3
Maximum edges to make Acyclic Directed Graph with 4 vertices are: 6
---------------------------------
Maximum edges to make Acyclic Undirected Graph with 5 vertices are: 4
Maximum edges to make Acyclic Directed Graph with 5 vertices are: 10

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: