szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 cze 2017, o 00:34 
Użytkownik

Posty: 12
Lokalizacja: Kraków
Udowodnij, że każdy graf rzędu n o rozmiarze większym niż \frac{(n-1)(n-2)}{2} jest spójny.

Dowód ten trzeba przeprowadzić na zasadzie indukcji, usuwając jeden wierzchołek. Nawet dochodzę do jakiegoś równania, ale nie bardzo rozumiem indukcje w tych grafach. Wiem, że nie ma sensu tutaj robić indukcji z założeniem że podgraf (bez jednego wierzchołka) jest spójny bo to jest wtedy oczywiste, że graf też jest spójny (o ile deg(v) \neq 0).
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 3 cze 2017, o 23:05 
Użytkownik
Avatar użytkownika

Posty: 1227
Weźmy graf o n+1 wierzchołkach, taki że liczba jego krawędzi jest większa, niż \frac{n(n-1)}{2}. Ponieważ

\sum_v deg(v) = 2|E|, więc

\sum_v deg(v) > n(n-1). Teraz trzeba pokazać, że można wybrać wierzchołek o dostatecznie małym stopniu (to że każdy stopień jest niezerowy powinno być jasne z powyższej nierówności), tzn na tyle małym, że jak go usuniemy, to będziemy mogli skorzystać z założenia indukcyjnego i dostaniemy spójność mniejszego grafu, co zakończy dowód. Pokombinuj, mam nadzieję, że moja wskazówka okaże się pomocna, powodzenia :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 graf prosty - zadanie 2  olkab  5
 Problem Casanovy Graf Znajomości  Avicularia  4
 Matematyka dyskretna - graf planarny  chlebzmaslem  4
 Dowód pokolorowania płaszczyzny i okregów dwoma kolorami  Oleszko12  1
 teoria grafów- dowód  tukanik  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl