"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:
\(\displaystyle{ 2m = \sum_{}^{v \in V} deg(v)}\)
Gdzie \(\displaystyle{ 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ć ?
Dwa wierzchołki w grafie prostym
Dwa wierzchołki w grafie prostym
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.
-
- Użytkownik
- Posty: 34
- Rejestracja: 16 lut 2015, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: Leszno
- Podziękował: 10 razy
Dwa wierzchołki w grafie prostym
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 ?
\(\displaystyle{ 2m = \sum_{}^{v \in V} deg(v)}\)
Tak, aby wszystko było jasne ?
Wszystko się zgadza.
Jak zatem dojść do tego równania ?
\(\displaystyle{ 2m = \sum_{}^{v \in V} deg(v)}\)
Tak, aby wszystko było jasne ?
-
- Użytkownik
- Posty: 29
- Rejestracja: 6 gru 2011, o 16:00
- Płeć: Mężczyzna
- Lokalizacja: abc
- Pomógł: 2 razy
Dwa wierzchołki w grafie prostym
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
Dwa wierzchołki w grafie prostym
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ć :
\(\displaystyle{ 2k+2=2(k+1)}\). Czyli zgadza się z założeniem indukcyjnym. I to kończy dowód
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ć :
\(\displaystyle{ 2k+2=2(k+1)}\). Czyli zgadza się z założeniem indukcyjnym. I to kończy dowód
-
- Użytkownik
- Posty: 34
- Rejestracja: 16 lut 2015, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: Leszno
- Podziękował: 10 razy
Dwa wierzchołki w grafie prostym
c.n.d.gardner pisze:
\(\displaystyle{ 2k+2=2(k+1)}\). Czyli zgadza się z założeniem indukcyjnym. I to kończy dowód
Dzięki za pomoc ;D