9.12. Summary of Relational Properties 261
(c)Prove that every finite tournament digraph has a ranking.(d)Prove that the less-than relation,>, on the rational numbers,Qis a DAG and
a tournament graph that has no ranking.
Problem 9.4.
In ann-playerround-robin tournament, every pair of distinct players compete in a
single game. Assume that every game has a winner —there are no ties. The results
of such a tournament can then be represented with atournament digraphwhere the
vertices correspond to players and there is an edgehx!yiiffxbeatyin their
game.
(a)Explain why a tournament digraph cannot have cycles of length 1 or 2.(b)Is the “beats” relation for a tournament graph always/sometimes/never:asymmetric?
reflexive?
irreflexive?
transitive?Explain.
(c)Show that a tournament graph represents a path-total order iff there are no
cycles of length 3.
Problem 9.5.
Suppose that there arenchickens in a farmyard. Chickens are rather aggressive
birds that tend to establish dominance in relationships by pecking. (Hence the term
“pecking order.”) In particular, for each pair of distinct chickens, either the first
pecks the second or the second pecks the first, but not both. We say that chickenu
virtually peckschickenvif either:
Chickenudirectly pecks chickenv, or Chickenupecks some other chickenwwho in turn pecks chickenv.A chicken that virtually pecks every other chicken is called aking chicken.
We can model this situation with achicken digraphwhose vertices are chickens
with an edge from chickenuto chickenvprecisely whenupecksv. In the graph