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 »

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 »

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 »

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 »

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 »

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 »

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 »

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: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

stopień w grafie a spójnośc

Post autor: Mruczek »

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