In the 1998 technical note "Computing on data streams" by Monika Rauch Henzinger , Prabhakar Raghavan , Sridar Rajagopalan (found here: http://www.eecs.harvard.edu/~michaelm/E210/datastreams.pdf)

They define a directed multigraph with node set V1 union V2 union … union Vk, all of whose edges are directed from a node in Vi to a node in Vi+1.

I cannot see how this allows for disconnected components? Can anyone clarify this?

  • $\begingroup$ There can be disconnected components if any of the $V_i$ is disconected. All $V_i$ are node sets as well, right? $\endgroup$
    – Trylks
    Aug 8, 2013 at 15:00
  • 1
    $\begingroup$ I don't see the problem: consider the union of some disjoint directed paths, each with $k$ vertices? $\endgroup$ Aug 8, 2013 at 15:14
  • $\begingroup$ I misunderstood the definition $\endgroup$
    – S0rin
    Aug 23, 2013 at 8:28

1 Answer 1


The definition says that every edge that exists has to go from some $V_i$ to $V_{i+1}$. It doesn't say that every possible edge from $V_i$ to $V_{i+1}$ has to be there. For example, $V_1=\{a,b\}$, $V_2=\{c,d\}$ with edges $ac$ and $bd$ gives a disconnected graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.