Mathematics for Computer Science

Chapter 9 Directed graphs & Partial Orders260

1

2

4

3

5

6

Figure 9.10 DAG with edges not needed in paths

The following examples show that the above results don’t work in general for
digraphs with cycles.

(e)Describe two graphs with verticesf1;2gwhich have the same set of covering
edges, but not the same positive path relation (Hint:Self-loops.)

(f) (i) Thecomplete digraphwithout self-loops on vertices1;2;3has edges

between every two distinct vertices. What are its covering edges?

(ii) What are the covering edges of the graph with vertices1;2;3and edges

h^1!^2 i;h^2!^3 i;h^3!^1 i?

(iii) What about their positive path relations?

Problem 9.3.
In a round-robin tournament, every two distinct players play against each other just
once. For a round-robin tournament with with no tied games, a record of who beat
whom can be described with atournament digraph, where the vertices correspond
to players and there is an edgehx!yiiffxbeatyin their game.
Arankingis a path that includes all the players. So in a ranking, each player won
the game against the next lowest ranked player, but may very well have lost their
games against must lower ranked players —whoever does the ranking can have a
lot of room to play favorites.

(a)Give an example of a tournament digraph with more than one ranking.

(b)Prove that if a tournament digraph is a DAG, then it has at most one ranking.