Dowód spójnosci grafu.

[Mritke]

Witam

Mam do rozwiązania następujące zadanie:

Mamy graf G o 2d-1 wierzchołkach, wszystkich stopnia d. Udowodnij że graf G jest spójny.

Nie mam zielonego pojęcia jak przeprowadzić ten dowód.

[abc666]

Weźmy jeden wierzchołek, muszą istnieć krawędzie pomiędzy miedzy nim a \(\displaystyle{ d}\) innymi wierzchołkami. Tworzymy graf pełny żeby wszystkie wierzchołki były stopnia \(\displaystyle{ d}\). Wykorzystaliśmy już \(\displaystyle{ d+1}\) wierzchołków, więc zostało \(\displaystyle{ d-2}\). Weźmy dowolny wierzchołek z tych pozostałych. Skoro jest stopnia d to istnieją krawędzie pomiędzy nim a d innymi wierzchołkami. Ale zostało już tylko \(\displaystyle{ d-3}\) więc musi mieć on wspólną krawędź z co najmniej trzema wykorzystanymi na początku. Dalej postępując analogicznie z resztą wierzchołków dowodzimy tego że graf jest spójny.

[miodzio1988]

Tworzymy graf pełny żeby wszystkie wierzchołki były stopnia d

Możesz mi wytlumaczyc po co to robimy? Wszystkie wierzcholki SĄ JUŻ stopnia \(\displaystyle{ d}\). Więc zupelnie nie rozumiem tego kroku

Dowod dla mnie jest lekko skopany Ale pozwolę Ci go bronic.

Ja bym to zrobił z definicji od razu.

[abc666]

Chodziło mi o to, że zaczynamy z samymi wierzchołkami, a potem dodajemy krawędzie. Jak wybierzemy te \(\displaystyle{ d+1}\) wierzchołków to robimy z nich graf pełny, żeby były stopnia d. Chodziło mi o pokazanie tego, że nie da się zbudować grafu niespójnego z podanymi własnościami.

[miodzio1988]

Graf nasz ma Z GORY NARZUCONĄ konstrukcję. Nie można powiedziec tak: " Zaczynam od tego, że graf nie posiada zadnych krawędzi i dla \(\displaystyle{ d+1}\) wierzcholkow tworzę ..." . Ja u Wujka Tomka(wykladowca) za sam taki tekst bym dostał 0 pkt. Trochę ingerujemy w dowolnosc tego grafu.
Dowod powinien się zaczynać tak:
Mamy graf o \(\displaystyle{ 2d-1}\) wierzchołkach. Bierzemy dwa dowolne wierzcholki tego grafu i pokazujemy, że istnieje między nimi droga. No i dopiero teraz można wykorzystac to co powiedziales, bo to wcale glupie nie jest
Czepiam się, ale tak trzeba

[abc666]

Sam pewnie wiesz, że zanim się pójdzie na studia to często umykają takie niuanse, wyrobie się :-p .

Trochę ingerujemy w dowolnosc tego grafu.

Ale jeśli pokażemy, że nie da się takiego grafu skonstruować, to w którym miejscu ingerujemy w jego dowolność?

[Inkwizytor]

Ale jeśli pokażemy, że nie da się takiego grafu skonstruować, to w którym miejscu ingerujemy w jego dowolność?

Ale dowód na to że sie nie da zwykle opiera się na metodzie "nie wprost". Tzn. Zakładasz że się da. Nie ingerujesz wtedy w konstrukcję i dochodzisz do sprzeczności.

[miodzio1988]

Ale jeśli pokażemy, że nie da się takiego grafu skonstruować, to w którym miejscu ingerujemy w jego dowolność?

Tak jak mowi Inkwizytor Dowod musi mieć odpowiednią forme jednak.

abc666 , ale Twoje rozwiązanie aż takie złe nie jest Widać, że myslisz i sama idea jest naprawdę spoko Jesli Cie interesuje inne rozwiązanie tego zagadnienia to napisz mi PW. Jak tylko zdam egzamin (sroda!!!!) to coś Ci fajnego wymyślę
Pozdrawiam i wielki szacunek , że bierzesz się za takie rzeczy.

[xiikzodz]

Rozważmy dowolny graf, o \(\displaystyle{ s}\) składowych spójnych, w którym każdy wierzchołek ma stopień \(\displaystyle{ d}\). Wówczas w każdej składowej spójnej jest przynajmniej \(\displaystyle{ d+1}\) wierzchołków, bo w każdej składowej jest wierzchołek oraz jego \(\displaystyle{ d}\) sąsiadów nie leżących w innych składowych. Zatem taki graf ma przynajmniej

\(\displaystyle{ s(d+1)}\)

wierzchołków. Zatem w przypadku grafu z zadania mamy nierówność:

\(\displaystyle{ s(d+1)\le 2d-1}\)

skąd

\(\displaystyle{ s\le\frac{2d-1}{d+1}=\frac{2d+2}{d+1}-\frac{3}{d+1}=2-\frac{3}{d+1}<2}\)

czyli graf ma mniej niż dwie składowe.

Ten sam argument działa dla każdej liczby wierzchołków niewiększej niż \(\displaystyle{ 2d+1}\).

[Mritke]

Wielkie dzięki xiikzodz. To będzie chyba najlepszy sposób, wcześniej próbowałem ze wzoru Eulera, no ale on jeszcze potwierdza planarność grafu(co mnie w tym przypadku kompletnie nie interesuje) A spójne składowe jakoś omijałem.-- 8 wrz 2009, o 20:27 --Dla świętego spokoju może jeszcze obliczymy dla jakich d takie grafy istnieją?

[xiikzodz]

Dla \(\displaystyle{ d}\) parzystych. Dla nieparzystych nie mogą istnieć, bo Graf \(\displaystyle{ d}\) - regularny o \(\displaystyle{ n}\) wierzchołkach ma \(\displaystyle{ \frac{nd}2}\) krawędzi, lecz liczba \(\displaystyle{ (2d-1)d}\) nie jest podzielna przez \(\displaystyle{ 2}\) dla nieparzystych \(\displaystyle{ d}\).

Pozostaje więc skonstruować takie grafy dla \(\displaystyle{ d}\) parzystych.

W tym celu rozważmy graf \(\displaystyle{ G_1}\) zbudowany z \(\displaystyle{ \frac d2}\) rozłącznych kopii \(\displaystyle{ K_2}\) (odcinków) oraz graf \(\displaystyle{ G_2}\) o \(\displaystyle{ d-1}\) wierzchołkach, bez krawędzi. Teraz wystarczy polączyć wszystkie wierzchołki grafu \(\displaystyle{ G_1}\) ze wszystkimi wierzchołkami grafu \(\displaystyle{ G_2}\).

Całkiem miłe zadanie...