1

Suppose four teams, the Aces, the Birds, the Cats, and the Dogs, played each other once. The Aces beat all three opponents except the Birds. The Birds lost to all opponents except the Aces. The Dogs beat the Cats. Represent the results of these games with a directed graph.

A dominance order is a listing of teams such that the ith team in the order beats the (i+1)th team. Find all dominance orders in the graph.

enter image description here

This is the directed graph for the teams, but I don't get the second part. Would a dominance order be ADCB?

thebottle394
  • 129

1 Answers1

2

Yes, it would. There is no other dominance order that begins AD: you can have ADB, but B does not beat C, so you can’t complete the order. If you start with AC, the next team clearly must be B, and the order cannot be completed. AB is impossible, so ADCB is the only dominance order beginning with A.

If you begin with B, you must continue with A, and since CD is impossible, the only possible further continuation yields the order BADC.

Similarly, it’s easy to check that CBAD is the only possibility starting with C.

I’ll leave the Dxxx case to you to finish off.

Brian M. Scott
  • 616,228
  • if looking at BADC, would ADC be another dominance order or would it be redundant to mention it? – ponderingdev Oct 13 '15 at 19:53
  • 1
    @curiousmind1995: It would not be a dominance order on the given set of teams. It would be a dominance order (and in fact the only one) on the subset ${A,C,D}$ of teams. – Brian M. Scott Oct 13 '15 at 19:58
  • Sorry, I just wish to develop my understanding on something. Why wouldn't something like ACBA work? Since B dominates A? –  Aug 25 '20 at 04:23
  • 1
    @SleeperMan23: A dominance order is a list of all of the teams in which each occurs exactly once and beats the team that immediately follows it in the order. ACB cannot be completed, because the only team left is D, and B does not beat D. – Brian M. Scott Aug 25 '20 at 06:43