szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 28 maja 2016, o 14:55 
Użytkownik

Posty: 32
Lokalizacja: W-wa
Niech G = (V,E) będzie grafem majączym co najmniej 4 wierzchołki oraz spełniającym (\forall A \subseteq V)(\left| A\right|=3 \Rightarrow |{A\choose 2}  \cap  E| > 1). Wykazać, że G jest grafem hamiltonowskim.
Wydaje mi się, że warunek oznacza, że pomiędzy każdymi wierzchołkami w grafie G istnieją co najmniej dwie krawędzie. Nie wiem, czy jest to właściwe, bo np. dla 6 wierzchołków dostawałem K_{6}
Góra
Kobieta Offline
PostNapisane: 29 maja 2016, o 09:48 
Użytkownik

Posty: 30
Lokalizacja: ba
Ten warunek oznacza, że dla każdych trzech wierzchołków v_1,v_2,v_3 istnieją w grafie co najmniej dwie krawędzie spośród trzech możliwych (v_i,v_j). Zauważ, że to oznacza, że każdy wierzchołek danego grafu jest połączony krawędzią z każdym innym poza co najwyżej jednym. Dlatego łatwo zadanie rozwiązać indukcją. Najpierw sprawdzamy, że dla czterech wierzchołków teza jest prawdziwa. To znaczy, że graf K_4 z usuniętymi dwoma krawędziami nie spotykającymi się w jednym wierzchołku jest hamiltonowski. Faktycznie, jest to cykl. Każdy graf czteroelementowy spełniający warunki zadania zawiera taki graf, czyli cykl czteroelementowy, więc mamy warunek początkowy indukcji. A dalej już łatwo. Zakładamy, że grafy spełniające założenia mające co najwyżej n wierzchołków są hamiltonowskie. Rozważmy graf G spełniający założenia mający n+1 wierzchołków. Wybieramy jeden wierzchołek, powiedzmy v_0. Graf powstały przez wyrzucenie v_0 jest na mocy założenia indukcyjnego hamiltonowski, więc ma cykl (v_1,v_2,\ldots,v_n). Wierzchołek v_0 jest połączony krawędzią z co najmniej n-1 wierzchołkami tego cyklu, powiedzmy z wierzchołkami v_1,\ldots,v_{n-1}. Wtedy jednak (v_1,v_0,v_2,v_3,\ldots,v_n) jest cyklem w G i teza pokazana.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Graf hamiltonowski - zadanie 3  Fray  0
 Graf hamiltonowski - zadanie 2  placky  4
 graf hamiltonowski  kamil.jack  1
 Graf Petersena nie posiada Cyklu hamiltonowskiego?  snowjay  2
 Wykaż, że... graf spójny - wierzchołki - jednakowe stopnie  gabilu  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl