CODEWITHSUNDEEP
algorithmgraphdirected-acyclic-graphs
DolceVita34
DolceVita34

Reputation: 115

Add edges to a directed acyclic graph without introducing a cycle and/or new vertices

Consider we have a directed Graph G = (V, E). Assume |V| ≥ 5. Is it possible to add |V| directed edges to G without introducing a cycle (and without introducing new vertices)? How would that be possible, and what would a formal proof look like? There were similar questions but none that have this case(the graph is strictly directed, vertices cannot be added) as far as I saw.

Thank you in advance.

Upvotes: 1

Views: 597

Answers (1)

Dave
Dave

Reputation: 9085

DAG nodes can be topologically sorted, which means that for each arc (a,b), node a is to the left of node b in the sort.

One way to do what you want is to first topologically sort the DAG. Say it has n nodes total. After the sort, a node at position i will have n-i-1 nodes after it. If the outdegree of the node at i is < n-i-1 for any i, then you can add an arc.

Now, if you are guaranteed that you have a DAG and want to know how many arcs you can add and still preserve the DAG attribute, but you don't need to identify them, you can do that much quicker. Notice that in a complete DAG (one with all possible arcs), after the topo sort the outdegrees will be [n-1, n-2, ..., 1, 0], and their sum will be n*(n+1)/2.

Find the count of arcs == sum of indegrees == sum of outdegrees. If this is less than n*(n+1)/2, the difference is the number of arcs you can add to the DAG while keeping it a DAG.

Upvotes: 3

Related Questions