The Gateway to Computer Science Excellence
+1 vote
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them is

But I think that a multi-stage graph is also a DAG. Are multi-stage graphs a special kind of DAG?
in Graph Theory by Active (2.2k points) | 100 views

1 Answer

0 votes
Yes, you are correct. A multi-stage graph is indeed a special type of DAG. However, the difference here is that you cannot have an edge between any two vertices of the same stage. And any edge MUST be from a $S_i$ to $S_{i+1}$, where $S_i$ and $S_{i+1}$ are stages that are topologically sorted. The example below should make it clear:

G=(V, E)
where V = {A, B, C}
and E = {(A,B), (B,C), (A,C)}

The above-given graph is surely a DAG, but it is NOT a multistage graph (because A and C can be put into different stages, but you can't place B in any stage, and moreover you can't create a new stage for B since there is an edge from A to C)

Do let me know if you have any more questions on this :-)

P.S: Usually multi-stage graphs are weighted, but I have neglected the weights here because they are irrelevant here. If you want to be mathematically rigorous, you can assume that all the edges are of unit length.
by (55 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,705 answers
107,565 users