<p>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.</p>

CC BY-SA 3.0
2013-08-08T15:07:34.630Z
2013-08-08T15:07:34.630Z
David Richerby
<p>In the 1998 technical note "Computing on data streams" by Monika Rauch Henzinger , Prabhakar Raghavan , Sridar Rajagopalan (found here: <a href="http://www.eecs.harvard.edu/~michaelm/E210/datastreams.pdf" rel="nofollow">http://www.eecs.harvard.edu/~michaelm/E210/datastreams.pdf</a>)</p>

<p>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.</p>

<p>I cannot see how this allows for disconnected components?  Can anyone clarify this?</p>

CC BY-SA 3.0
2013-08-08T15:00:07.750Z
There can be disconnected components if any of the $V_i$ is disconected. All $V_i$ are node sets as well, right?
Trylks
CC BY-SA 3.0
2013-08-08T15:14:23.197Z
I don't see the problem: consider the union of some disjoint directed paths, each with $k$ vertices?
András Salamon
CC BY-SA 3.0
2013-08-23T08:28:11.760Z
I misunderstood the definition
S0rin
<data-streams><streaming>
"Computing on data streams" clarification
S0rin
# "Computing on data streams" clarification

(Asked by: username_0 on 2013-08-08)

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?

**Tags:** data-streams, streaming

> **Comments:**
> **username_1**: There can be disconnected components if any of the $V_i$ is disconected. All $V_i$ are node sets as well, right?  
> **username_2**: I don't see the problem: consider the union of some disjoint directed paths, each with $k$ vertices?  
> **username_0**: I misunderstood the definition  

---

## 1 answers

### Answer by username_3 on 2013-08-08. Score: 1 | Accepted answer

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.


---

