Spójność grafu
-
piotrekgym
- Użytkownik
- Posty: 8
- Rejestracja: 12 wrz 2012, o 21:51
- Płeć: Mężczyzna
- Lokalizacja: Śląsk
- Podziękował: 2 razy
Spójność grafu
Niech \(\displaystyle{ G=(V,E)}\) będzie grafem spójnym oraz \(\displaystyle{ \left| V\right| \ge 3}\). Pokaż, że nie istnieje wierzchołek \(\displaystyle{ v\in V}\) taki, że \(\displaystyle{ G-v}\) nie jest spójny wtedy i tylko wtedy, gdy dowolne dwa różne wierzchołki tego grafu leżą na jednym cyklu.
-
M Maciejewski
- Użytkownik
- Posty: 318
- Rejestracja: 14 maja 2016, o 16:25
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Pomógł: 90 razy
Spójność grafu
Lepiej zapisać to tak:
Dla każdego wierzchołka \(\displaystyle{ v}\) graf \(\displaystyle{ G- v}\) jest spójny wtw
dowolne dwa różne wierzchołki grafu leżą na jednym cyklu.
Przez cykl musimy rozumieć taką drogę zamkniętą, w której nie powtarzają się wierzchołki (*). Inaczej to zdanie nie jest prawdziwe.
\(\displaystyle{ \Longleftarrow:}\)
Rozważmy dowolny wierzchołek \(\displaystyle{ v}\). Pokażemy, że \(\displaystyle{ G- v}\) jest spójny.
Niech \(\displaystyle{ p,q\in G- v}\).Skoro \(\displaystyle{ p,q}\) leżą na jednym cyklu w grafie \(\displaystyle{ G}\), to na pewno istnieją dwie rozłączne (różne wierzchołki poza końcami) drogi w grafie \(\displaystyle{ G}\) łączące te punkty (to wynika z (*)). Co najwyżej na jednej z tych dróg leży \(\displaystyle{ v}\). Zatem wierzchołki \(\displaystyle{ p,q}\) są połączone drogą w \(\displaystyle{ G-v}\).
\(\displaystyle{ \Longrightarrow:}\)
To jest bardziej skomplikowane, i może warto skorzystać z jakiegoś twierdzenia, ale ja przedstawię szkic bezpośredni.
Niech \(\displaystyle{ x\sim y \iff x=y}\) lub \(\displaystyle{ x,y}\) leżą na jednym cyklu.
Lemat 1. Jeśli \(\displaystyle{ x,y}\) to sąsiadujące wierzchołki, to \(\displaystyle{ x\sim y}\).
Dowód opiera się na założeniu \(\displaystyle{ |V|>2}\) i na założeniu tej implikacji.
Niech \(\displaystyle{ z\notin\{x,y\}}\).
Istnieje droga \(\displaystyle{ x\to\to z}\) bez wierzchołka \(\displaystyle{ y}\).
Istnieje droga \(\displaystyle{ z\to\to y}\) bez wierzchołka \(\displaystyle{ x}\).
Łącząc te drogi dostaniemy pewną drogę łączącą \(\displaystyle{ x}\) i \(\displaystyle{ y}\) bez krawędzi \(\displaystyle{ x-y}\). Jeśli połączymy najkrótszą taką ścieżkę z krawędzią \(\displaystyle{ y-x}\) dostajemy cykl w sensie (*).
Lemat 2. Relacja \(\displaystyle{ \sim}\) to relacja równoważności.
Zwrotność i symetryczność jest jasna. Trzeba sprawdzić przechodniość.
Niech \(\displaystyle{ x\sim y}\) (leżą na cyklu \(\displaystyle{ \alpha}\)) i \(\displaystyle{ y\sim z}\) ((leżą na cyklu \(\displaystyle{ \beta}\))). Rozważmy graf \(\displaystyle{ G'=G-y}\). Niech \(\displaystyle{ \gamma}\) będzie najkrótszą ścieżką w \(\displaystyle{ G'}\) łączącą dowolny wierzchołek cyklu \(\displaystyle{ \alpha}\) oraz dowolny wierzchołek cyklu \(\displaystyle{ \beta}\) (takie ścieżki istnieją z założenia implikacji, więc możemy wybrać pewną najkrótszą).
Teraz odpowiednio kombinując z \(\displaystyle{ \alpha,\beta,\gamma}\) wygenerujemy cykl, na którym leżą \(\displaystyle{ x,y}\) (pomijam szczegóły).
Mając te dwa lematy bez problemu dostajemy tezę:
skoro graf jest spójny, lemat 1 i 2. zapewnia nas, że relacja \(\displaystyle{ \sim}\) ma jedynie jedną klasę abstrakcji równą całemu grafowi. To kończy dowód.
Dla każdego wierzchołka \(\displaystyle{ v}\) graf \(\displaystyle{ G- v}\) jest spójny wtw
dowolne dwa różne wierzchołki grafu leżą na jednym cyklu.
Przez cykl musimy rozumieć taką drogę zamkniętą, w której nie powtarzają się wierzchołki (*). Inaczej to zdanie nie jest prawdziwe.
\(\displaystyle{ \Longleftarrow:}\)
Rozważmy dowolny wierzchołek \(\displaystyle{ v}\). Pokażemy, że \(\displaystyle{ G- v}\) jest spójny.
Niech \(\displaystyle{ p,q\in G- v}\).Skoro \(\displaystyle{ p,q}\) leżą na jednym cyklu w grafie \(\displaystyle{ G}\), to na pewno istnieją dwie rozłączne (różne wierzchołki poza końcami) drogi w grafie \(\displaystyle{ G}\) łączące te punkty (to wynika z (*)). Co najwyżej na jednej z tych dróg leży \(\displaystyle{ v}\). Zatem wierzchołki \(\displaystyle{ p,q}\) są połączone drogą w \(\displaystyle{ G-v}\).
\(\displaystyle{ \Longrightarrow:}\)
To jest bardziej skomplikowane, i może warto skorzystać z jakiegoś twierdzenia, ale ja przedstawię szkic bezpośredni.
Niech \(\displaystyle{ x\sim y \iff x=y}\) lub \(\displaystyle{ x,y}\) leżą na jednym cyklu.
Lemat 1. Jeśli \(\displaystyle{ x,y}\) to sąsiadujące wierzchołki, to \(\displaystyle{ x\sim y}\).
Dowód opiera się na założeniu \(\displaystyle{ |V|>2}\) i na założeniu tej implikacji.
Niech \(\displaystyle{ z\notin\{x,y\}}\).
Istnieje droga \(\displaystyle{ x\to\to z}\) bez wierzchołka \(\displaystyle{ y}\).
Istnieje droga \(\displaystyle{ z\to\to y}\) bez wierzchołka \(\displaystyle{ x}\).
Łącząc te drogi dostaniemy pewną drogę łączącą \(\displaystyle{ x}\) i \(\displaystyle{ y}\) bez krawędzi \(\displaystyle{ x-y}\). Jeśli połączymy najkrótszą taką ścieżkę z krawędzią \(\displaystyle{ y-x}\) dostajemy cykl w sensie (*).
Lemat 2. Relacja \(\displaystyle{ \sim}\) to relacja równoważności.
Zwrotność i symetryczność jest jasna. Trzeba sprawdzić przechodniość.
Niech \(\displaystyle{ x\sim y}\) (leżą na cyklu \(\displaystyle{ \alpha}\)) i \(\displaystyle{ y\sim z}\) ((leżą na cyklu \(\displaystyle{ \beta}\))). Rozważmy graf \(\displaystyle{ G'=G-y}\). Niech \(\displaystyle{ \gamma}\) będzie najkrótszą ścieżką w \(\displaystyle{ G'}\) łączącą dowolny wierzchołek cyklu \(\displaystyle{ \alpha}\) oraz dowolny wierzchołek cyklu \(\displaystyle{ \beta}\) (takie ścieżki istnieją z założenia implikacji, więc możemy wybrać pewną najkrótszą).
Teraz odpowiednio kombinując z \(\displaystyle{ \alpha,\beta,\gamma}\) wygenerujemy cykl, na którym leżą \(\displaystyle{ x,y}\) (pomijam szczegóły).
Mając te dwa lematy bez problemu dostajemy tezę:
skoro graf jest spójny, lemat 1 i 2. zapewnia nas, że relacja \(\displaystyle{ \sim}\) ma jedynie jedną klasę abstrakcji równą całemu grafowi. To kończy dowód.