Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.