szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 1 wrz 2016, o 15: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 2018
Góra
Mężczyzna Offline
PostNapisane: 1 wrz 2016, o 16: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 16: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 16: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 na prostokąt na płaszczyźnie  Anal_Iza  2
 Dowód na nie istnienie danego grafu  tomek1172  1
 graf prosty - zadanie 2  olkab  5
 Dowód tożsamości (symbol newtona)  addmir  2
 Dowód z modulo  jackblack  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl