Lesson 14

The toy graph above is undirected (also called symmetric). We specify its edges as subsets of size two (for example, \(\{B, K\}\)) to emphasize that the order of the nodes does not matter (thus, \(\{K, B\}\) is the same edge as \(\{B, K\}\)). There are many applications where one needs to model asymmetric relations between objects. In this case, we say that the corresponding graph is directed and specify its edges as tuples. Directed edges are also called arcs. For example, a directed graph \(G(V, E)\) where \[V=\{1, 2, 3, 4, 5\} \text{ and }E=\{(1, 5), (2, 3), (4, 5), (1, 2), (3, 4)\}\] has five nodes and five edges. The edge \((2, 3)\) goes from \(2\) to \(3\) and it is not the same edge as \((3, 2)\).

Directed edges are shown with arrows: