Istnienie cyklu w grafie

[Majeskas]

Niech \(\displaystyle{ C}\) i \(\displaystyle{ D}\) będą różnymi cyklami w grafie \(\displaystyle{ G}\), a \(\displaystyle{ e}\) krawędzią wspólną dla cykli \(\displaystyle{ C}\) i \(\displaystyle{ D}\). Pokazać, że graf \(\displaystyle{ G}\) zawiera cykl nieprzechodzący przez \(\displaystyle{ e}\).

[M Maciejewski]

Jeśli graf jest skierowany, to teza jest nieprawdziwa.
Jeśli graf jest nieskierowany, to dowód jest prosty.
Rozważmy dwa cykle C i D, w której kolejne krawędzie oznaczmy następująco:
\(\displaystyle{ C:\ c_1,c_2,\ldots,c_m}\),
\(\displaystyle{ D:\ d_1,d_2,\ldots,d_n}\), przy czym tak oznaczamy krawędzie, aby \(\displaystyle{ c_1=d_1=e}\). Wtedy cyklem niezawierający \(\displaystyle{ e}\) jest cykl:
\(\displaystyle{ d_m,d_{m-1},\ldots,d_3,d_2,c_2,c_3,\ldots,c_m}\).

[Majeskas]

To nie jest prawda. Nikt nie broni cyklom \(\displaystyle{ C}\) i \(\displaystyle{ D}\) się zazębiać i wtedy powyższa trasa nie jest cyklem.

[M Maciejewski]

A co to przeszkadza? Jak rozumiem, wymagany jest dodatkowy warunek na cykl? Że np. nie powtarzają się wierzchołki, krawędzie, lub coś podobnego?

[Majeskas]

Tak, właśnie o tyle to przeszkadza. Wiem, że cykl cyklowi nierówny, ale tutaj chodzi o drogę zamkniętą, a więc o coś, co np. na Wikipedii nazywa się "cyklem prostym".

[M Maciejewski]

W takim razie wystarczy pokazać, że jeśli istnieje cykl, w którym wierzchołki się powtarzają, to istnieje cykl, w którym wierzchołki się nie powtarzają. Można to zrobić na dwa sposoby:
1) à la indukcyjnie: jeśli w cyklu powtarza się dany wierzchołek, a więc gdy częścią cyklu jest tak fragment:
\(\displaystyle{ \cdots \to A_0\to \mathbf{A_1}\to A_2\to\cdots A_k\to \mathbf{A_1}\to A_{k+1}\to \cdots}\),
to usuwamy z cyklu całą drogę \(\displaystyle{ A_0\to\cdots\to A_0}\) i zostaje nam
\(\displaystyle{ \cdots \to A_0\to \mathbf{A_1}\to A_{k+1}\to \cdots}\).
Ponieważ za każdym razem skraca nam się cykl, nie możemy takiej procedury powtarzać w nieskończoność. Zatem po skończonej liczbie kroków usuniemy wszystkie takie wystąpienia.
2) Metodą minimalną (tak tę metodę tymczasowo nazwijmy). Skoro istnieją cykle, to rozważmy ten najkrótszy. W nim nie mogę się powtarzać wierzchołki, bo moglibyśmy usunąć (jak w punkcie pierwszym) fragment cyklu, skracając jego długość, a przecież on jest najkrótszy.

[Majeskas]

Rozważmy dwa cykle C i D, w której kolejne krawędzie oznaczmy następująco:
\(\displaystyle{ C:\ c_1,c_2,\ldots,c_m}\),
\(\displaystyle{ D:\ d_1,d_2,\ldots,d_n}\), przy czym tak oznaczamy krawędzie, aby \(\displaystyle{ c_1=d_1=e}\). Wtedy cyklem niezawierający \(\displaystyle{ e}\) jest cykl:
\(\displaystyle{ d_m,d_{m-1},\ldots,d_3,d_2,c_2,c_3,\ldots,c_m}\).

A co właściwie oznacza \(\displaystyle{ c_1=d_1=e}\)?-- 27 maja 2016, 23:04 --

W takim razie wystarczy pokazać, że jeśli istnieje cykl, w którym wierzchołki się powtarzają, to istnieje cykl, w którym wierzchołki się nie powtarzają. Można to zrobić na dwa sposoby:
1) à la indukcyjnie: jeśli w cyklu powtarza się dany wierzchołek, a więc gdy częścią cyklu jest tak fragment:
\(\displaystyle{ \cdots \to A_0\to \mathbf{A_1}\to A_2\to\cdots A_k\to \mathbf{A_1}\to A_{k+1}\to \cdots}\),
to usuwamy z cyklu całą drogę \(\displaystyle{ A_0\to\cdots\to A_0}\) i zostaje nam
\(\displaystyle{ \cdots \to A_0\to \mathbf{A_1}\to A_{k+1}\to \cdots}\).
Ponieważ za każdym razem skraca nam się cykl, nie możemy takiej procedury powtarzać w nieskończoność. Zatem po skończonej liczbie kroków usuniemy wszystkie takie wystąpienia.

Weźmy taki graf, że
\(\displaystyle{ C:\ c_1,c_2,c_3}\)
\(\displaystyle{ D:\ d_1,d_2,d_3,d_4}\)
i \(\displaystyle{ d_1=c_1, d_3=c_2, d_4=c_3}\) oraz \(\displaystyle{ e=\left\{ c_1,c_3\right\}=\left\{ d_1,d_4\right\}}\), i postępujmy zgodnie z podaną procedurę. Piszemy sumę cykli:
\(\displaystyle{ d_4=c_3, d_3=c_2, d_2, d_1=c_1, c_2, c_3}\) i zaczynamy usuwać powtórki. Wycinamy drogę \(\displaystyle{ d_2,c_1,c_2}\) i zostajemy z \(\displaystyle{ c_3, c_2, c_3}\).
Procedura usuwania powtórek się skończyła, a cyklu brak.

2) Metodą minimalną (tak tę metodę tymczasowo nazwijmy). Skoro istnieją cykle, to rozważmy ten najkrótszy. W nim nie mogę się powtarzać wierzchołki, bo moglibyśmy usunąć (jak w punkcie pierwszym) fragment cyklu, skracając jego długość, a przecież on jest najkrótszy.

Ta argumentacja opiera się na tym samym założeniu co w punkcie 1), tj. że skracanie cyklu zawsze prowadzi do cyklu, co - jak widać - nie jest prawdą.

[michals95]

Być może ten dowód będzie prawidłowy.

Skoro cykle \(\displaystyle{ C}\) i \(\displaystyle{ D}\) mogę się zazębiać, to załóżmy, że mają one \(\displaystyle{ k}\) wspólnych krawędzi, a więc muszą mieć także \(\displaystyle{ k+1}\) wspólnych wierzchołków (wierzchołki są incydentne do krawędzi). W związku z tym graf \(\displaystyle{ C \cup D - e}\) ma \(\displaystyle{ \left| C\right| + \left| D\right| - k - 1}\) krawędzi oraz co najwyżej \(\displaystyle{ \left| C\right| + \left| D\right| - k - 1}\) wierzchołków. Ponieważ otrzymany graf ma co najmniej tyle krawędzi co wierzchołków, to musi istnieć cykl.

[Majeskas]

Bardzo eleganckie rozwiązanie!

Od siebie dodam ścisłe uzasadnienie ostatniego stwierdzenia. Być może strzelę z armaty, ale ja nie potrafię tego prościej wykazać.

Ponieważ otrzymany graf ma co najmniej tyle krawędzi co wierzchołków, to musi istnieć cykl.

Stwierdzenie równoważne: jeśli w \(\displaystyle{ G}\) nie ma cyklu, to \(\displaystyle{ |E(G)|<|V(G)|}\).

Dowód. Graf \(\displaystyle{ G}\) jest lasem, a więc sumą \(\displaystyle{ k}\) drzew \(\displaystyle{ T_i}\), gdzie \(\displaystyle{ k \ge 1}\). Z charakteryzacji drzew mamy teraz:

\(\displaystyle{ |E(G)|=\sum_{i=1}^k|E(T_i)|=\sum_{i=1}^k(|V(T_i)|-1)=\sum_{i=1}^k|V(T_i)|-k=|V(G)|-k \le |V(G)|-1<|V(G)|}\)