turniej - dowód

[cis123]

Udowodnij, że jeśli turniej nie zawiera skierowanego trójkąta, to można ustawić jego wierzchołki w takiej kolejności \(\displaystyle{ v_{1}, ..., v_{n}}\), że jeśli \(\displaystyle{ i < j}\), to skierowana krawędź prowadzi od \(\displaystyle{ v_{i}}\) do \(\displaystyle{ v_{j}}\).


Jeśli istnieje skierowany trójkąt to istnieją \(\displaystyle{ a, b, c}\), że:
\(\displaystyle{ v_{a} \rightarrow v_{b} \rightarrow v_{c} \rightarrow v_{a}}\)
Zatem nie jesteśmy w stanie ustawić wierzchołków w odpowiedniej kolejności.

Jeśli turniej nie zawiera skierowanego trójkąta to wydaje się oczywiste, że jesteśmy w stanie ułożyć wierzchołki w żądanej kolejności, ale nie potrafię tego udowodnić formalnie. Jakieś pomysły?

[Mruczek]

Pokażę dwa dowody:

Pierwszy dowód to zad. 3 tutaj:

Kod: Zaznacz cały

http://www.deltami.edu.pl/temat/matematyka/kombinatoryka/2016/11/26/Okragly_stol_i_trojkaty/

Drugi dowód:
Jest taki fakt, że jeżeli turniej zawiera cykl, to zawiera trójkąt (to zadanie nr 2 w powyższym linku).
W takim razie jeżeli ten turniej nie zawiera trójkątów, to nie zawiera też cykli, więc jest to skierowany graf acykliczny, a taki graf można posortować topologicznie, czyli ustawić jego wierzchołki w żądany sposób.