Appearance
Directed graphs
A directed graph (or digraph) consists of vertices and ordered pairs of edges . Each directed edge is written as , meaning that this is an edge from to . Notice that for directed graphs .
If , we say that is an out-neighbor of and is an in-neighbor of . Denote by and the numbers of out- and in-neighbors of respectively.
Exercise 25 (Directed Handshake)
Let be a digraph. Prove:
Given an undirected graph , we say that a digraph is an orientation of if it can be obtained by "giving directions" to edges in . More formally, and for each edge , exactly one of or belongs to . Notice that every undirected graph has different orientations. When is an orientation of , we say that is a symmetrization of (obtained by removing directions from ).
There are two notions of connectedness in digraphs. For a digraph , if a symmetrization of is connected, we say that is weakly connected. If, for every , there is a directed walk from to in , then is said to be strongly connected.
Exercise 26
Prove that a weakly connected digraph contains at least edges and a strongly connected digraph contains at least edges.