szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 26 maja 2012, o 16:06 
Użytkownik

Posty: 136
Lokalizacja: Warszawa
Twierdzenie:
W każdym grafie G zachodzi nierówność:
\kappa \left( G\right) \le \lambda \left( G\right) \le \delta \left( G\right)

Proszę o pomoc w dowodzie tej nierówności.

\kappa \left( G\right)-spójność wierzchołkowa
\lambda \left( G\right)-spójność krawędziowa
\delta \left( G\right)-minimalny stopień
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 23 wrz 2012, o 11:19 
Użytkownik

Posty: 1301
Lokalizacja: Skierniewice/Warszawa
Drugą nierówność łatwo uzasadnić w ten sposób, że dowolny graf można rozspójnić usuwając wszystkie krawędzie wychodzące z dowolnego wierzchołka. Więc jeśli weźmiemy wierzchołek o najmniejszym stopniu i usuniemy z niego wszystkie krawędzie to graf będzie niespójny. Możliwe, że da się zrobić to lepiej, czyli usuwając mniej krawędzi. :)
Góra
Mężczyzna Offline
PostNapisane: 11 lip 2015, o 17:08 
Użytkownik

Posty: 541
Lokalizacja: Kielce
Podbijam gdyż też poszukuje dowodu
Góra
Mężczyzna Offline
PostNapisane: 11 lip 2015, o 17:34 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Pierwsza nierówność jest również oczywista,gdyż usuwając wierzchołek usuwamy również wchodzące i wychodzące z niego krawędzie. Tzn. usuwając dowolną krawędź na pewno można ją usunąć poprzez usunięcie wierzchołka z którym jest połączona (zawsze zabieramy co najmniej jedną krawędź - a dokładnie tyle ile wynosi deg v gdzie v to nasz wierzchołek) Oczywiste jest więc,że spójność wierzchołkowa jest mniejsza od krawędziowej (zawsze można rozspójnić graf "szybciej" usuwając wierzchołek niż krawędź)
Góra
Mężczyzna Offline
PostNapisane: 17 lip 2015, o 07:20 
Gość Specjalny

Posty: 3051
Lokalizacja: Gołąb
Dowód lewej nierówności wcale nie jest taki łatwy. Jeśli nikt tego nie zrobi, napiszę go po pracy.
Góra
Mężczyzna Offline
PostNapisane: 17 lip 2015, o 14:54 
Użytkownik

Posty: 541
Lokalizacja: Kielce
dzięki wielkie!
Góra
Mężczyzna Offline
PostNapisane: 17 lip 2015, o 23:53 
Użytkownik

Posty: 548
Lokalizacja: Warszawa
http://matmauksw.ovh.org/dyskretna/MAD-w04.pdf

Twierdzenie 4.6 i jego dowód. Nie sprawdzałem dokładnie, czy dowód jest w 100% poprawny, ale na pewno trzeba zastosować indukcję.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 nierownosc z 5 zmiennymi - ile rozwiazan w l. naturalnych?  Anonymous  25
 Nierówność z silnią  Zasados  2
 Wariancja i pewna nierówność  sszbig  0
 nierownosc z symbolem newtona  piwne_oko  1
 Wyznacz zbór które nie spełniają nie nierówność  CoLLeR  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl