Mam udowodnić takie twierdzenie ale nie wiem od czego zacząć? :
Każdy maksymalny zbiór niezależny grafu \(\displaystyle{ G}\) jest minimalnym zbiorem dominującym tego grafu.
Teoria grafów
-
- Użytkownik
- Posty: 12
- Rejestracja: 15 paź 2015, o 09:50
- Płeć: Kobieta
- Lokalizacja: Podkarpacie
- Podziękował: 1 raz
Teoria grafów
Ostatnio zmieniony 2 mar 2018, o 15:01 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa także do pojedynczych symboli.
Powód: Używaj LaTeXa także do pojedynczych symboli.
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Teoria grafów
Powyższe twierdzenie jest fałszywe.
Weźmy np. graf gwiazdę, czyli drzewo, które ma jeden wierzchołek w korzeniu i jest połączone z \(\displaystyle{ 10}\) wierzchołkami. Maksymalny zbiór niezależny to zbiór liści tego drzewa, ma wielkość \(\displaystyle{ 10}\). Jest on też zbiorem dominującym, ale nie minimalnym, bo minimalny zbiór dominujący tego drzewa składa się z jednego wierzchołka - korzenia.
Prawdziwe jest za to twierdzenie:
Każdy maksymalny zbiór niezależny grafu jest pewnym zbiorem dominującym tego grafu.
Dowód:
Bierzemy ten maksymalny zbiór niezależny. Dowód nie wprost. Przypuśćmy, że nie jest to zbiór dominujący. Wtedy istniałby wierzchołek w tym grafie, który nie jest zdominowany przez ten zbiór niezależny. To znaczy, że ten wierzchołek nie jest sąsiadem żadnego z wierzchołków tego zbioru niezależnego, czyli możemy dodać go do poprzedniego maksymalnego zbioru niezależnego zwiększając zbiór niezależny, sprzeczność.
Weźmy np. graf gwiazdę, czyli drzewo, które ma jeden wierzchołek w korzeniu i jest połączone z \(\displaystyle{ 10}\) wierzchołkami. Maksymalny zbiór niezależny to zbiór liści tego drzewa, ma wielkość \(\displaystyle{ 10}\). Jest on też zbiorem dominującym, ale nie minimalnym, bo minimalny zbiór dominujący tego drzewa składa się z jednego wierzchołka - korzenia.
Prawdziwe jest za to twierdzenie:
Każdy maksymalny zbiór niezależny grafu jest pewnym zbiorem dominującym tego grafu.
Dowód:
Bierzemy ten maksymalny zbiór niezależny. Dowód nie wprost. Przypuśćmy, że nie jest to zbiór dominujący. Wtedy istniałby wierzchołek w tym grafie, który nie jest zdominowany przez ten zbiór niezależny. To znaczy, że ten wierzchołek nie jest sąsiadem żadnego z wierzchołków tego zbioru niezależnego, czyli możemy dodać go do poprzedniego maksymalnego zbioru niezależnego zwiększając zbiór niezależny, sprzeczność.
-
- Użytkownik
- Posty: 12
- Rejestracja: 15 paź 2015, o 09:50
- Płeć: Kobieta
- Lokalizacja: Podkarpacie
- Podziękował: 1 raz
Teoria grafów
Przeanalizowałam definicje i minimalny zbiór dominujący to taki, że po usunięciu wierzchołka już nie będzie zbiorem dominującym zatem to twierdzenie jest prawidłowe.