szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 10 cze 2010, o 19: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
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 10 cze 2010, o 19: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 19: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 22: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 18: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 19: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 18:47 
Użytkownik

Posty: 33
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 15:42 
Użytkownik

Posty: 1074
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 
 Dowód nierówności w grafie  Fray  4
 Zbiory niezależne w grafie a zależność rekurencyjna  pietr  9
 Spójność grafu - zadanie 5  alto de aitana  3
 cykle w grafie 2-spójnym  forever17  0
 Liczba chromatyczna a ilość krawędzi w grafie.  studciak123  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl