szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 1 wrz 2016, o 14:57 
Użytkownik

Posty: 8
Lokalizacja: Śląsk
Niech G=(V,E) będzie grafem, takim że |V| \ge 4 oraz dla dowolnych wierzchołków u,v,w co najmniej dwie spośród krawędzi uv, uw, i vw należą do E. Pokazać, że G jest hamiltonowski.

Prosiłbym o jakąś wskazówkę.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 1 wrz 2016, o 15:03 
Użytkownik

Posty: 44
Weź dwa dowolne nieincydentne wierzchołki u,v grafu i rozpatrz dowolną trójkę u,v,w. Udowodnij, że spełniony jest warunek Orego, czyli graf jest hamiltonowski.
Góra
Mężczyzna Offline
PostNapisane: 1 wrz 2016, o 15:11 
Użytkownik

Posty: 8
Lokalizacja: Śląsk
Mógłbyś coś więcej napisać, bo nie bardzo wiem jak udowodnić że spełniony jest warunek Orego.
Góra
Mężczyzna Offline
PostNapisane: 1 wrz 2016, o 15:22 
Użytkownik

Posty: 44
Weźmy dowolne u,v  \in V takie, że uv \not\in E. Jeśli takie wierzchołki nie istnieją, to graf jest grafem pełnym, więc z oczywistych względów istnieje cykl Hamiltona. Rozpatrzmy teraz dowolną trójkę u,v,w  \in V. Z warunków zadania \forall w \in V \setminus \left\{u,v \right\} uw \in E  vw \in E. Takich trójek jest n-2, zatem mamy spełnioną nierówność
deg u + deg v   \ge 2n - 4  \ge n, bo liczba wierzchołków jest większa lub równa 4. Zatem jest spełniony warunek Orego, dzięki czemu graf jest hamiltonowski.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Dowód, liczby Stirlinga  Kvothe  6
 Graf n - wierzchołkowy.  ugabuga333  0
 Jaki warunek powinien być spełniony, aby graf dwudzielny  Marien  0
 Dowód tożsamości - zadanie 2  djszaman  1
 Teoria grafów, dowód twierdzenia Bondy'ego-Chvatala  kgrafy  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl