Mówimy, że graf prosty \(\displaystyle{ G = \langle V,E \rangle}\) jest spójny, jeśli zwrotne i przechodnie domknięcie relacji \(\displaystyle{ E}\) jest równe \(\displaystyle{ V \times V}\) (w języku teorii grafów oznacza to, że każde dwa wierzchołki są połączone ścieżką). Pokaż przez indukcję, że (dla wszystkich dodatnich liczb naturalnych n) każdy n-elementowy graf spójny ma conajmniej n - 1 krawędzi.
Widziałem już taki temat wcześniej, lecz został on usunięty. Proszę o pomoc.
Z góry dziękuję.
Indukcja. Graf prosty.
Indukcja. Graf prosty.
Ostatnio zmieniony 16 sty 2013, o 11:12 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Temat umieszczony w złym dziale.
Powód: Temat umieszczony w złym dziale.
-
yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
Indukcja. Graf prosty.
Krok pierwszy jest łatwy.
Krok indukcyjny: Idea: Bierzemy graf spójny o \(\displaystyle{ n+1}\) wierzchołkach. Wyrzucamy z niego tyle krawędzi, by przestał być spójny. Rozpadnie się więc na dwa kawałki o mniejszej liczbie wierzchołków \(\displaystyle{ k}\) i \(\displaystyle{ l}\)
Z założenia każdy z nich ma co najmniej \(\displaystyle{ k-11}\) i \(\displaystyle{ l-1}\) krawędzi. Teraz do tego dodajemy jedną krawędź, by uspójnić oba kawałki (krawędź bierzemy taką, którą wcześniej usuwaliśmy, by rozspójnić graf). Ile jest teraz krawędzi?
Krok indukcyjny: Idea: Bierzemy graf spójny o \(\displaystyle{ n+1}\) wierzchołkach. Wyrzucamy z niego tyle krawędzi, by przestał być spójny. Rozpadnie się więc na dwa kawałki o mniejszej liczbie wierzchołków \(\displaystyle{ k}\) i \(\displaystyle{ l}\)
Z założenia każdy z nich ma co najmniej \(\displaystyle{ k-11}\) i \(\displaystyle{ l-1}\) krawędzi. Teraz do tego dodajemy jedną krawędź, by uspójnić oba kawałki (krawędź bierzemy taką, którą wcześniej usuwaliśmy, by rozspójnić graf). Ile jest teraz krawędzi?