stopień w grafie a spójnośc

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
owen1011
Użytkownik
Użytkownik
Posty: 568
Rejestracja: 29 sty 2009, o 13:59
Płeć: Mężczyzna
Podziękował: 230 razy

stopień w grafie a spójnośc

Post autor: owen1011 » 10 cze 2010, o 19:29

Pokazac, ze jesli minimalny stopien w grafie rzedu n, \(\displaystyle{ \partial{G) \ge \frac{n-1}{2}}\) to graf jest spójny.

z gory dzieki za pomoc

Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

stopień w grafie a spójnośc

Post autor: Dumel » 10 cze 2010, o 19:53

hint: rozważ składową z najmniejszą liczbą wierzchołków

owen1011
Użytkownik
Użytkownik
Posty: 568
Rejestracja: 29 sty 2009, o 13:59
Płeć: Mężczyzna
Podziękował: 230 razy

stopień w grafie a spójnośc

Post autor: owen1011 » 11 cze 2010, o 19:44

ok, tylko dalej nie wiem za bardzo jak to zrobic, mozesz cos wiecej dopisac

Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

stopień w grafie a spójnośc

Post autor: Dumel » 11 cze 2010, o 22:29

liczba wierzcholków w tej składowej to co najmniej \(\displaystyle{ 1+\frac{n-1}{2} > \frac{n}{2}}\) wiec jest tylko jedna składowa tj. graf jest spójny

owen1011
Użytkownik
Użytkownik
Posty: 568
Rejestracja: 29 sty 2009, o 13:59
Płeć: Mężczyzna
Podziękował: 230 razy

stopień w grafie a spójnośc

Post autor: owen1011 » 12 cze 2010, o 18:40

jescze nie rozumiem, skad ta nierownosc i skad ten wniosek

Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

stopień w grafie a spójnośc

Post autor: Dumel » 12 cze 2010, o 19:29

gdyby istniała inna składowa to miałaby też wiecej niz \(\displaystyle{ \frac{n}{2}}\) wierzchołków i razem byłoby \(\displaystyle{ >\frac{n}{2}+\frac{n}{2}=n}\) wierzchołków

albo inaczej
weźmy 2 niesąsiadujące ze sobą wierzchołki. każdy ma co najmniej n/2 sąsiadów wiec zbiory sąsiadów nie mogą być rozłączne, czyli wierzchołki niesąsiednie mają wspólnego sąsiada

aga285
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 28 sty 2015, o 20:28
Płeć: Kobieta
Lokalizacja: dom

stopień w grafie a spójnośc

Post autor: aga285 » 17 cze 2016, o 18:47

a dlaczego zakładamy, że każdy z tych dwóch niesąsiadujących wierzchołków ma co najmniej \(\displaystyle{ \frac{n}{2}}\) sąsiadów, a nie \(\displaystyle{ \frac{n-1}{2}}\) ?

Mruczek
Użytkownik
Użytkownik
Posty: 1111
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 155 razy

stopień w grafie a spójnośc

Post autor: Mruczek » 4 wrz 2016, o 15:42

Dumel chyba się pomylił i powinno być \(\displaystyle{ \frac{n-1}{2}}\). Jeżeli te wierzchołki nie mają wspólnych sąsiadów i nie sąsiadują ze sobą to mamy łącznie \(\displaystyle{ 2 + 2 \cdot \frac{n-1}{2} > n}\) wierzchołków, sprzeczność.

ODPOWIEDZ