Twierdzenie:
W każdym grafie G zachodzi nierówność:
\(\displaystyle{ \kappa \left( G\right) \le \lambda \left( G\right) \le \delta \left( G\right)}\)
Proszę o pomoc w dowodzie tej nierówności.
\(\displaystyle{ \kappa \left( G\right)}\)-spójność wierzchołkowa
\(\displaystyle{ \lambda \left( G\right)}\)-spójność krawędziowa
\(\displaystyle{ \delta \left( G\right)}\)-minimalny stopień
Nierówność Whitney'a
-
silvaran
- Użytkownik
- Posty: 1300
- Rejestracja: 6 sty 2009, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice/Warszawa
- Podziękował: 60 razy
- Pomógł: 123 razy
Nierówność Whitney'a
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.
-
gardner
Nierówność Whitney'a
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 \(\displaystyle{ deg v}\) gdzie \(\displaystyle{ 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ź)
