Matematyka.pl

"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ć ?

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.

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 ?

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

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

gardner pisze:
\(\displaystyle{ 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