Witam,
Pokazać, że w turnieju nie będzie cyklu skierowanego wtedy i tylko wtedy gdy można graczom przyporządkować tak etykiety:
\(\displaystyle{ p_i,\ p_j}\), tak, że \(\displaystyle{ p_i}\) pokonał \(\displaystyle{ p_j}\) tylko jeśli \(\displaystyle{ i<j}\)
Czyli gracz pierwszy pokonał wszystkich...
I teraz z lewa na prawo:
Posortujmy topologicznie od lewej do prawej, a następnie nadajmy od lewej do prawej numery: \(\displaystyle{ 1,2,...,n}\)
Z prawa na lewo.
Załóżmy, że istnieje takie etykietowanie, jak żądają w treści.
Przypuśćmy przeciwnie, że istnieje cykl. Ale to oznacza, że jedna z krawędzi będzie prowadzić do mniejszego numery wierzchołka, sprzeczność.
Czy ten dowód jest ok ?
Wniosek z tego:
Możemy na \(\displaystyle{ n!}\) sposobów przepermutować etykiety. Żadne etykietowanie się nie może powtórzyć, bo każdy zawodnik wygrał inną ilość meczy. Więc jeśli w turnieju o \(\displaystyle{ n}\) graczach nie ma cyklu skierowanego to możemy na \(\displaystyle{ n!}\) sposobów wybrać wyniki dla zawodników - wyniki to ilość meczów przegranych.
Wniosek ok ?