stopień w grafie a spójnośc
-
- 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
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
z gory dzieki za pomoc
-
- 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
ok, tylko dalej nie wiem za bardzo jak to zrobic, mozesz cos wiecej dopisac
-
- 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
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
-
- 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
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
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
stopień w grafie a spójnośc
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}}\) ?
-
- 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
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ść.