szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 10 cze 2010, o 18:29 
Użytkownik

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

z gory dzieki za pomoc
Góra
Mężczyzna Offline
PostNapisane: 10 cze 2010, o 18:53 
Użytkownik

Posty: 2001
Lokalizacja: Stare Pole/Kraków
hint: rozważ składową z najmniejszą liczbą wierzchołków
Góra
Mężczyzna Offline
PostNapisane: 11 cze 2010, o 18:44 
Użytkownik

Posty: 568
ok, tylko dalej nie wiem za bardzo jak to zrobic, mozesz cos wiecej dopisac
Góra
Mężczyzna Offline
PostNapisane: 11 cze 2010, o 21:29 
Użytkownik

Posty: 2001
Lokalizacja: Stare Pole/Kraków
liczba wierzcholków w tej składowej to co najmniej 1+\frac{n-1}{2} > \frac{n}{2} wiec jest tylko jedna składowa tj. graf jest spójny
Góra
Mężczyzna Offline
PostNapisane: 12 cze 2010, o 17:40 
Użytkownik

Posty: 568
jescze nie rozumiem, skad ta nierownosc i skad ten wniosek :)
Góra
Mężczyzna Offline
PostNapisane: 12 cze 2010, o 18:29 
Użytkownik

Posty: 2001
Lokalizacja: Stare Pole/Kraków
gdyby istniała inna składowa to miałaby też wiecej niz \frac{n}{2} wierzchołków i razem byłoby >\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
Góra
Kobieta Offline
PostNapisane: 17 cze 2016, o 17:47 
Użytkownik

Posty: 39
Lokalizacja: dom
a dlaczego zakładamy, że każdy z tych dwóch niesąsiadujących wierzchołków ma co najmniej \frac{n}{2} sąsiadów, a nie \frac{n-1}{2} ?
Góra
Mężczyzna Offline
PostNapisane: 4 wrz 2016, o 14:42 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Dumel chyba się pomylił i powinno być \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 2 + 2  \cdot \frac{n-1}{2} > n wierzchołków, sprzeczność.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Elementy zbioru, drogi w grafie  novikxxx  1
 Cykl hamiltona w grafie o 6 wierzchołkach  Anonymous  4
 D-d ze nie ma drogi prostej w grafie  filip.wroc  2
 Dwa wierzchołki w grafie prostym  Nitr0Skay  5
 Cykle i przekroje w grafie  jpxx  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl