szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Kobieta Offline
 Tytuł: Teoria grafów
PostNapisane: 2 mar 2018, o 14:08 
Użytkownik

Posty: 13
Lokalizacja: Podkarpacie
Mam udowodnić takie twierdzenie ale nie wiem od czego zacząć? :
Każdy maksymalny zbiór niezależny grafu G jest minimalnym zbiorem dominującym tego grafu.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 3 mar 2018, o 20:13 
Użytkownik

Posty: 1076
Lokalizacja: Lublin/Warszawa
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 10 wierzchołkami. Maksymalny zbiór niezależny to zbiór liści tego drzewa, ma wielkość 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ść.
Góra
Kobieta Offline
 Tytuł: Teoria grafów
PostNapisane: 6 mar 2018, o 21:31 
Użytkownik

Posty: 13
Lokalizacja: Podkarpacie
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.
Góra
Mężczyzna Offline
PostNapisane: 10 mar 2018, o 00:26 
Użytkownik

Posty: 1076
Lokalizacja: Lublin/Warszawa
Nie masz racji. Podałem kontrprzykład, więc twierdzenie jest fałszywe.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Teoria grafów - zadanie 5  Trojan90  3
 Teoria grafów - zadanie 9  kiler69  2
 Teoria grafów - zadanie 8  trusiekpt  8
 teoria grafów - zadanie 4  dusia17  2
 Teoria grafów - zadanie 7  kasienka16m  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl