szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 12:56 
Użytkownik

Posty: 246
Lokalizacja: Zamość
Witam.
Przygotowuję się do egzaminu i otrzymałem zadanie o treści:
Udowodnij, ze jeśli graf prosty o n wierzchołkach ma co najmniej \frac{1}{2}  \left( n-1\right) \left( n-2\right) +2 krawędzi, to jest grafem Hamiltona.

Oczywiście wiem, że jest to trzecie założenie Twierdzenia o liczbie krawędzi, które jeśli jest spełnione w danym to istnieje w tym grafie droga Hamiltona.. No, ale czy ja mam się powołać na to twierdzenie? Czy jakoś inaczej to udowadniać?
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 13:46 
Gość Specjalny

Posty: 5872
Lokalizacja: Toruń
Moim zdaniem trzeba powołać się na Twierdzenie Ore.
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 14:06 
Użytkownik

Posty: 246
Lokalizacja: Zamość
Na Twierdzenie Orego? No, ale tam mamy tylko że jeśli mamy dwa niesąsiednie wierzchołki u i v to d\left( u\right) + d\left( v\right)  \ge n gdzie n to liczba wierzchołków. Mówię tylko o 3 założeniu, bo 2 pierwsze są takie same w tw. Diraca, Orego jak i o liczbie krawędzi.
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 14:18 
Gość Specjalny

Posty: 5872
Lokalizacja: Toruń
Wydaje mi się, że właśnie to założenie wynika z tego oszacowania na liczbę krawędzi.
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 14:27 
Użytkownik

Posty: 246
Lokalizacja: Zamość
To muszę przyznać, że nie wiem jak to zrobić. Od czego zacząć?
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 14:36 
Gość Specjalny

Posty: 5872
Lokalizacja: Toruń
Ustalmy dowolne niesąsiednie wierzchołki u i v. Oznaczmy przez G' graf powstały poprzez usunięcie wierzchołka u i wierzchołka v wraz z ich krawędziami. Wówczas |E(G')| \leq \frac{(n-2)(n-3)}{2}, gdyż G' ma n-2 wierzchołki. Ponieważ u i v nie miały wspólnej krawędzi, to
|E(G)| = |E(G')| + \deg (v) + \deg (u)
Stąd
\deg(v) + \deg(u) = |E(G)| - |E(G')| \geq \frac{1}{2} \left( n-1\right) \left( n-2\right) +2 - \frac{(n-2)(n-3)}{2} = n.
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 16:24 
Użytkownik

Posty: 246
Lokalizacja: Zamość
To kończy dowód czy trzeba dalej, bo szczerze mówiąc to wiem co się dzieje w tym dowodzie, ale nie wiem co daje nam chociażby stworzenie grafu G', który uzyskujemy poprzez usunięcie u i v.
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 20:38 
Gość Specjalny

Posty: 5872
Lokalizacja: Toruń
Udowodniliśmy przecież, że dla niesąsiednich wierzchołków zachodzi nierówność
\deg(v) + \deg(u) \geq n
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilość podgrafów grafu K10 izomorficznych z W6 (gwazda 6)  chmielusek  2
 metoda wlaczen i wylaczen, kolorowanie grafu,drzewo binarne  anna_y  0
 dowód na nieskończoną algebrę Boole'a  kasia1404  0
 Relacja równoważności na zbiorze wierzchołków grafu  Majeskas  1
 Ile jest drzew n wierzchołkowych - dowód  wena  7
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl