815 views

1 Answer

2 votes
2 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.

Related questions

0 votes
0 votes
1 answer
1
Crime Master Gogo asked May 3, 2017
2,952 views
Is every k connected graph is k-1 connected or the reverse? I always get confused. Can someone explain with the help of an example.
0 votes
0 votes
2 answers
2
Jai Singh asked Jun 26, 2023
444 views
Consider a graph with n vertices that is a collection of k disjoint trees, where 𝑛 𝑘 1 . How many edges does this graph have?(A) n-1 (B) k (n-1) (C) n-k (D) n-k-1...
1 votes
1 votes
2 answers
3
admin asked Dec 15, 2022
695 views
What is the minimum number of nodes required in a DAG (Directed Acyclic Graph) for the following block?\[\begin{aligned}U=Z & =V+W \\X=Y & =U+1 \\A & =X+Y\end{aligned}\]