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 '13 at 15:00
  • 1
    $\begingroup$ I don't see the problem: consider the union of some disjoint directed paths, each with $k$ vertices? $\endgroup$ – András Salamon Aug 8 '13 at 15:14
  • $\begingroup$ I misunderstood the definition $\endgroup$ – S0rin Aug 23 '13 at 8:28

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, privacy policy and cookie policy

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