szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 13: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ć?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 14:46 
Gość Specjalny

Posty: 5709
Lokalizacja: Toruń
Moim zdaniem trzeba powołać się na Twierdzenie Ore.
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 15: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 15:18 
Gość Specjalny

Posty: 5709
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 15: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 15:36 
Gość Specjalny

Posty: 5709
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 17: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 21:38 
Gość Specjalny

Posty: 5709
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 
 Udowodnij istnienie ciągu  Dario1  1
 Liczba kombinacji n po k - dowód nieindukcyjny?  tranto  1
 Promień grafu  malaker  0
 Liczba wierzcholkow grafu.  czerkawska  3
 Notacja asymptotyczna - dowód  rekja  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl