Udowodnij że w każdym niehamiltonowskim turnieju możliwy jest podział wierzchołków na dwie klasy A i B, taki że dla dowolnych wierzchołków \(\displaystyle{ a \in A}\) i \(\displaystyle{ b \in B}\) krawędź skierowana między nimi ma zwrot \(\displaystyle{ a \to b}\)
turniej niehamiltonowski
: 3 kwie 2013, o 00:30
autor: kaszubki
zadanie ze \(\displaystyle{ 101}\) nierozwiązanych problemów
Ukryta treść:
Niech \(\displaystyle{ A}\) będzie najdłuższym cyklem prostym (jeżeli nie istnieje żaden cykl, to zadanie jest trywialne).
Wówczas resztę można podzielić na 2 zbiory \(\displaystyle{ B_1,B_2}\) takie, że \(\displaystyle{ B_1 \rightarrow A}\) i \(\displaystyle{ A \rightarrow B_2}\). Wynika to z tego, że wybraliśmy, że \(\displaystyle{ A}\) jest maksymalnym cyklem. Ponadto na tej samej argumentacji dostajemy, że \(\displaystyle{ B_1 \rightarrow B_2}\). Zatem \(\displaystyle{ B_1 \rightarrow B_2 \cup A}\), czyli teza.
przypadek szczególny: gdy \(\displaystyle{ |B_1|=0}\), to \(\displaystyle{ A \rightarrow B_2}\), czyli teza. A \(\displaystyle{ |B_2|>0}\), bo turniej był niehamiltionowski.