Dowód spójnosci grafu.
-
- Użytkownik
- Posty: 6
- Rejestracja: 7 wrz 2009, o 15:46
- Płeć: Mężczyzna
- Lokalizacja: Bielsk Podlaski
- Podziękował: 1 raz
Dowód spójnosci grafu.
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.
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.
Dowód spójnosci grafu.
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.
Dowód spójnosci grafu.
Możesz mi wytlumaczyc po co to robimy? Wszystkie wierzcholki SĄ JUŻ stopnia \(\displaystyle{ d}\). Więc zupelnie nie rozumiem tego krokuabc666 pisze:Tworzymy graf pełny żeby wszystkie wierzchołki były stopnia d
Dowod dla mnie jest lekko skopany Ale pozwolę Ci go bronic.
Ja bym to zrobił z definicji od razu.
Dowód spójnosci grafu.
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.
Dowód spójnosci grafu.
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
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
Dowód spójnosci grafu.
Sam pewnie wiesz, że zanim się pójdzie na studia to często umykają takie niuanse, wyrobie się :-p .
Ale jeśli pokażemy, że nie da się takiego grafu skonstruować, to w którym miejscu ingerujemy w jego dowolność?Trochę ingerujemy w dowolnosc tego grafu.
- Inkwizytor
- Użytkownik
- Posty: 4105
- Rejestracja: 16 maja 2009, o 15:08
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 1 raz
- Pomógł: 428 razy
Dowód spójnosci grafu.
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.abc666 pisze: Ale jeśli pokażemy, że nie da się takiego grafu skonstruować, to w którym miejscu ingerujemy w jego dowolność?
Ostatnio zmieniony 7 wrz 2009, o 21:27 przez Inkwizytor, łącznie zmieniany 1 raz.
Dowód spójnosci grafu.
Tak jak mowi Inkwizytor Dowod musi mieć odpowiednią forme jednak.abc666 pisze:Ale jeśli pokażemy, że nie da się takiego grafu skonstruować, to w którym miejscu ingerujemy w jego dowolność?
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.
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Dowód spójnosci grafu.
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}\).
\(\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}\).
-
- Użytkownik
- Posty: 6
- Rejestracja: 7 wrz 2009, o 15:46
- Płeć: Mężczyzna
- Lokalizacja: Bielsk Podlaski
- Podziękował: 1 raz
Dowód spójnosci grafu.
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ą?
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Dowód spójnosci grafu.
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...
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...