Directed graphs

#matematik-discmath

Definition: Directed graph

A directed graph or digraph is a set whose members are called vertices, together with a set , whose members are called edges or arcs, and we write .

Note that formally, a directed graph is just a Relation on : This means that results for relations can be applied to digraphs too. For example, a symmetric relation implies that , so all arcs in the graph can be thought of as double pointed.

Definition: Directed walk, directed path

A directed walk in a digraph is a sequence of vertices such that for every .

A directed path is a directed walk where all vertices are distinct.

A directed cycle is a directed walk where all vertices are distinct except that .

Definition: Tournament

A tournament is a digraph with exactly one arc between each pair of vertices.

Theorem

In any tournament there is a directed path containing all vertices.

Proof:
We show that any path not containing all vertices can be made longer. Take any path and suppose is a vertex not in the path. Then, if is an edge, we can prepend and we are done. Otherwise, is an edge. Then if is an edge, can be inserted between and . Otherwise, is an edge. Continue this process until either is inserted, or we reach , meaning is an edge, meaning can be appended to the end and we are done.