66666666666666666666666666666666666666666666666666666666666666666666 Directed 3- cycles in Tournaments Recall that a tournament is a directed graph without parallel edges whose underlying graph is K”. We showed in class: Theorem. The number of transitive triples 9(0) in a tournament D of order n is [(0) = E Z od(v) (od(v) – 1). vEV(D) Corollary. The number of directed 3-cycles IS (3) – f(D). 1) Explain why the corollary IS true and why [(0) S (3) as a consequence. 2) Explain the possible effects on f (D) of reversing the orientation of a single edge 11!). Suppose before the switch that od(u) = a and od(v) = b. 3) Suppose a tournament of order n has two teams who have beaten n – 2 other teams. Must there be a directed 3-cycle in this situation? 4) Use the theorem and problem 2 to show that the only way for f (D) = (g) is for the out-degrees to cover the entire set {0.12, …,n – 1}. 5) Math/CSci 553 students should find recipes for tournaments that maximize f(D) and tournaments that minimize f(D) as well, with justifications.

You can leave a response, or trackback from your own site.