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ę.
Góra
Mężczyzna Offline
PostNapisane: 1 wrz 2016, o 15:03 
Użytkownik

Posty: 45
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: 45
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 indukcyjny na kombinacje bez powtórzeń  Janekradzi  1
 Graf nieskierowany - zadanie 3  kasia00  1
 dowód własności liczb stirlinga  MikolajB  4
 dowód indukcyjny - zadanie 50  tukanik  3
 Graf nieplenarny, hamiltonowski, nieeulerowski  stachurskipiotr424  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl