szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 lip 2015, o 10:35 
Użytkownik

Posty: 37
Lokalizacja: Leszno
"Wykazać, że w grafie prostym istnieją przynajmniej dwa wierzchołki tego samego
stopnia." - Graf prosty to taki, który zawiera jedną i tylko jedną krawędź łączącą dwa różne wierzchołki (choć to zapewne wielu z Was to wie). No i właśnie jak w przypadku zadania numer dwa, nie mogę tego chyba narysować. Mam to bowiem wykazać w przypadku każdego grafu prostego (potwierdzone info), tylko właśnie w jaki sposób to zrobić ?

W wyniku rozwiązania tego zadania doszliśmy do tego zapisu:
2m =  \sum_{}^{v  \in  V}  deg(v)

Gdzie m jest to ilość krawędzi.
No i właśnie nie potrafię rozgryźć, co ten zapis oznacza i jak do niego dojść. W jaki sposób, przy użyciu jakich twierdzeń, własności i wzorów można coś takiego uzyskać ?
Góra
Mężczyzna Offline
PostNapisane: 3 lip 2015, o 10:42 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Odpowiedź jest prosta. Każda krawędź w grafie wnosi 2 do sumy stopni wierzchołków (ma początek i koniec). Więc suma stopni wszystkich wierzchołków to dwa razy liczba krawędzi.
Góra
Mężczyzna Offline
PostNapisane: 3 lip 2015, o 10:48 
Użytkownik

Posty: 37
Lokalizacja: Leszno
Hmm, coś w tym jest. Weźmy przykładowo kwadrat, jako przykład grafu prostego - w nim mamy 4 krawędzie o stopniu dwa, zatem suma tych stopni wynosi 8. Krawędzi jest 4. 8/4 = 2

Wszystko się zgadza.
Jak zatem dojść do tego równania ?
2m =  \sum_{}^{v  \in  V}  deg(v)

Tak, aby wszystko było jasne ?
Góra
Mężczyzna Offline
PostNapisane: 3 lip 2015, o 10:54 
Użytkownik

Posty: 29
Lokalizacja: abc
To jest tak zwany lemat o usciskach dloni. Sprobuj zapisac sobie graf w postaci binarnej macierzy incydencji, czyli tam gdzie jest krawedz jest 1, a tak gdzie nie ma 0. I sprobuj zliczyc wszystkie konce krawdzi na dwa sposoby. W jednym wychodzi z automatu 2m, a w drugim wlasnie ta suma
Góra
Mężczyzna Offline
PostNapisane: 3 lip 2015, o 10:58 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Dowód jest taki jak napisałem wyżej albo bardziej szczegółowy -indukcyjny.

Niech to będzie indukcja ze względu na k-liczbę krawędzi. Dla k=0 suma zer wynosi 0 i dwa razy zero to też zero. Zgadza się. Przyjmijmy,że wzór prawdziwy dla jakiegoś k. Teraz rozpatrzmy graf o k+1 krawędziach. Usuńmy jedną krawędź (można bo zbiór krawędzi jest nie pusty).Suma stopni z założenia indukcyjnego wynosiła 2k. Zmniejszyła się o ona o 2 (bo usunęliśmy krawędź) więc pierwotnie musiała wynosić :
2k+2=2(k+1). Czyli zgadza się z założeniem indukcyjnym. I to kończy dowód
Góra
Mężczyzna Offline
PostNapisane: 3 lip 2015, o 11:14 
Użytkownik

Posty: 37
Lokalizacja: Leszno
gardner napisał(a):

2k+2=2(k+1). Czyli zgadza się z założeniem indukcyjnym. I to kończy dowód


c.n.d.

Dzięki za pomoc ;D
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 cykle w grafie 2-spójnym  forever17  0
 Wierzchołki sześciokąta foremnego  krokus50  1
 Dwa różne wierzchołki grafu o tym samym stopniu  rajban  2
 liczba krawędzi w grafie  dhreal  3
 Ścieżka P5 w grafie  pozone  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl