Exercises 407- Verify that the following graph D is a dag. Perform a topological sort on the vertices
of the graph. a
hf
e
D- Prove that if C1, C2. Ck is a sequence of cycles in a directed graph D such that
every two consecutive cycles have at least one common vertex, then the subgraph
determined by the union of these cycles is strongly connected. - Prove that if a graph G contains an Eulerian circuit, then G is orientable.
- Prove that each of the following graphs is orientable:
(^68 1)
5 7 7 123 9 21
12 11 10 12
D1 D2 D3
- Prove that a connected undirected graph is orientable if and only if each edge is con-
tained in a cycle. - Show that any graph with a Hamiltonian cycle is orientable.
- Prove that if a directed graph is Eulerian, then it is strongly connected.
- Prove that a directed graph D = (V, E) is strongly connected if and only if for any
partition V1, V 2 of V there is an edge (x, y) with x E V 1 and y E V 2. - Find a directed graph that is not Eulerian but for which the underlying graph is
Eulerian. - Devise an algorithm to find an Eulerian circuit in a directed graph, if one exists. Modify
the algorithm to find all Eulerian circuits in a graph. - Challenge: A complete directed graph is a directed graph whose underlying graph is
a complete graph. Show that the sum of the squares of the indegrees over all vertices
is equal to the sum of the squares of the outdegrees over all vertices in any directed
complete graph.
Definition 1. A tournament Tn is a directed graph on n vertices such that each pair of
vertices v, w is joined by one and only one of the directed edges (v, w) or (w, v). The
score of a vertex of a tournament is its outdegree. The score sequence, or ranking, of a
tournament is the sequence formed by arranging the scores of its vertices in nondecreasing
order. A tournament is transitive if the existence of edges (a, b) and (b, c) imply the
existence of the edge (a, c). The complement of a tournament is formed by reversing all
the directions on the edges of a tournament.