# “Computing on data streams” clarification

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?

• There can be disconnected components if any of the $V_i$ is disconected. All $V_i$ are node sets as well, right? – Trylks Aug 8 '13 at 15:00
• I don't see the problem: consider the union of some disjoint directed paths, each with $k$ vertices? – András Salamon Aug 8 '13 at 15:14
• I misunderstood the definition – 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.