Mathematics for Computer Science

9.11. Summary of Relational Properties 365

Problem 9.38.
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 one or two.

(b)Is the “beats” relation for a tournament graph always/sometimes/never:

asymmetric?

reflexive?

irreflexive?

transitive?

Explain.

(c)Show that a tournament graph is a linear order iff there are no cycles of length
three.

Homework Problems

Problem 9.39.
LetRandSbe transitive binary relations on the same set,A. Which of the follow-
ing new relations must also be transitive? For each part, justify your answer with a
brief argument if the new relation is transitive and a counterexample if it is not.

(a)R^1

(b)R\S

(c)RıR

(d)RıS

Exam Problems

Problem 9.40.
Suppose the precedence constraints on a set of 32 unit time tasks was isomorphic
to the powerset, pow.f1;2;3;4;5g/under the strict subset relation,.
For example, the task corresponding to the setf2;4gmust be completed be-
fore the task corresponding to the setf1;2;4gbecausef2;4g  f1;2;4g; the task