szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 cze 2016, o 21:50 
Użytkownik

Posty: 8
Lokalizacja: Śląsk
Niech G=(V,E) będzie grafem spójnym oraz \left| V\right| \ge 3. Pokaż, że nie istnieje wierzchołek v\in V taki, że G-v nie jest spójny wtedy i tylko wtedy, gdy dowolne dwa różne wierzchołki tego grafu leżą na jednym cyklu.
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2016, o 23:51 
Użytkownik

Posty: 322
Lokalizacja: Toruń
Lepiej zapisać to tak:
Dla każdego wierzchołka v graf 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.

\Longleftarrow:
Rozważmy dowolny wierzchołek v. Pokażemy, że G- v jest spójny.
Niech p,q\in G- v.Skoro p,q leżą na jednym cyklu w grafie G, to na pewno istnieją dwie rozłączne (różne wierzchołki poza końcami) drogi w grafie G łączące te punkty (to wynika z (*)). Co najwyżej na jednej z tych dróg leży v. Zatem wierzchołki p,q są połączone drogą w G-v.

\Longrightarrow:
To jest bardziej skomplikowane, i może warto skorzystać z jakiegoś twierdzenia, ale ja przedstawię szkic bezpośredni.

Niech x\sim y \iff x=y lub x,y leżą na jednym cyklu.

Lemat 1. Jeśli x,y to sąsiadujące wierzchołki, to x\sim y.
Dowód opiera się na założeniu |V|>2 i na założeniu tej implikacji.
Niech z\notin\{x,y\}.
Istnieje droga x\to\to z bez wierzchołka y.
Istnieje droga z\to\to y bez wierzchołka x.
Łącząc te drogi dostaniemy pewną drogę łączącą x i y bez krawędzi x-y. Jeśli połączymy najkrótszą taką ścieżkę z krawędzią y-x dostajemy cykl w sensie (*).

Lemat 2. Relacja \sim to relacja równoważności.
Zwrotność i symetryczność jest jasna. Trzeba sprawdzić przechodniość.

Niech x\sim y (leżą na cyklu \alpha) i y\sim z ((leżą na cyklu \beta)). Rozważmy graf G'=G-y. Niech \gamma będzie najkrótszą ścieżką w G' łączącą dowolny wierzchołek cyklu \alpha oraz dowolny wierzchołek cyklu \beta (takie ścieżki istnieją z założenia implikacji, więc możemy wybrać pewną najkrótszą).
Teraz odpowiednio kombinując z \alpha,\beta,\gamma wygenerujemy cykl, na którym leżą 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 \sim ma jedynie jedną klasę abstrakcji równą całemu grafowi. To kończy dowód.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Spójność grafu - zadanie 3  Annoyer13  1
 Spójność grafu - zadanie 5  alto de aitana  3
 Spójność grafu  Arst  0
 Spójność grafu - zadanie 2  Paragon16  1
 Istnienie grafu  Anonymous  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl