Graphs
Chapters > Graphs
Graphs are similar to trees, except that its nodes have at least one predecessor. If the nodes of a graph comply with the following conditions, the graph is said to have a graph structure, or it is a graph:
- A distinguished node Source precedes all nodes, which does not have a predecessor
- A distinguished node Sink succeeds all nodes which does not have a successor
- Exactly one node has no predecessor (the Source)
- Exactly one node has no successor (the Sink)
- All other nodes have at least one predecessor, and at least one successor
Nodes which have more than one predecessor are targets of more than one path, like the paths [Joan, Bob] and [Joan, Neil, Bob] in this example.
There are two alternatives how we can represent a graph:
- Node-oriented (all examples we have seen so far)
- Edge-oriented
If a graph is represented as edge-oriented, its edges are used as nodes, and the nodes as edges. In this form of representation, tails and heads of edges are also edges. Our example would then have:
- (Joan,Bob), (Joan,Neil), (Neil,Bob) and (Bob,Melanie) as its nodes
- ((Joan,Bob),(Bob,Melanie)), ((Joan,Neil),(Neil,Bob)), and ((Neil,Bob),(Bob,Melanie)) as its edges
We will discuss the expressive power of edge-oriented graphs in the next chapter.
