chapter  12
18 Pages

Graphs

A graph G consists of a set V of vertices and a set E ⊆ V × V of edges between the vertices. G is called undirected, if for each edge e = 〈v, u〉 ∈ E also the reverse 〈u, v〉 ∈ E, otherwise G is directed. For an edge 〈v, u〉 of a directed graph we say that it goes from v to u, and that the vertices v and u are adjacent.