+1 vote
100 views
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?
| 100 views

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)

+1 vote