Discrete Mathematics for Computer Science

408 CHAPTER 6 Graph Theory

16. For the tournament shown, find a ranking of the players:

a b

d c

17. Let D = (V, E) be a tournament. Prove that if a has maximum score, then for any
    vertex y, either there is an edge (a, y) or a vertex w and edges (a, w) and (w, y).


18. Prove that a tournament with no cycles is transitive.


19. Prove that if D is a tournament, then it has a directed Hamiltonian path.


20. Show that a transitive tournament can have its vertices ordered so that if a precedes b,
    then the score of a is greater than or equal to the score of b.


21. Show that the figure

6 3

54

can be used to schedule a "tournament" for seven players. The tournament has a di-

rected edge (i, j) if and only if i beats j. (Hint: Rotate the edges but not the vertices.)

Representing a Relation. A digraph can be used to represent a relation. For a relation

R on a set A, define the digraph D = (V, E) as follows: Let V = A. There is an edge

(i, j) e E if and only if (i, j) E R. The definition of a digraph needs to be extended slightly

to allow representation of elements of the form (x, x) c R. A loop in a digraph is an edge

with both ends the same. We think of a loop as starting and ending at the same vertex. For

example, we can represent the relation R on {1, 2, 3, 4, 5} with elements {(1, 1), (2, 3), (3,

4), (4, 1), (2, 5)) as

4 3

22. Represent by a digraph the partial order defined on P({ 1, 2, 3, 4}) where the relation
    is set inclusion.


23. Represent by a digraph the partial order divides defined on the integers 0 through 11.


24. Let R be the relation on {1, 2, 3, 4, 5} with elements {(1, 1), (2, 1), (3, 2), (2, 3), (1, 4),
    (3, 5), (5, 2)). Represent R as a digraph.


25. Let R be the relation on {1, 2, 3, 4, 51 with elements {(l, 1), (2, 1), (3, 2), (2, 3), (1, 4),
    (3, 5), (5, 2)). Represent the reflexive closure of R as a digraph.