Swipe to navigate through the chapters of this book
Please log in to get access to this content
To get access to this content you need the following product:
As quoted by Albert-László Barabási in his book Linked: TheNew Science of Networks (Basic Books, 2002).
You probably didn’t even think of it as an issue, but you can assume that V and E don’t overlap.
The functions would still be called V and E, even if we give the sets other names. For example, for a graph H = ( W, F), we would have V( H) = W and E( H) = F.
As explained later, though, the root is not considered a leaf. Also, for a graph consisting of only two connected nodes, calling them both leaves sometimes doesn’t make sense.
Note that this is the same terminology as for the in- and out-neighborhoods in digraphs. The two concepts coincide once we start orienting the tree edges.
This is true only if all nodes can be reached from the start node. Otherwise, the traversal may have to restart in several places, resulting in a spanning forest. Each component of the spanning forest will then have its own root.
- Graph Terminology
Magnus Lie Hetland
- Sequence number
- Chapter number
- Appendix C