Skojarzenie, pokrycie wierzchołkowe, a zbiór niezależny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
ucaps
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 22 mar 2017, o 19:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 5 razy

Skojarzenie, pokrycie wierzchołkowe, a zbiór niezależny

Post autor: ucaps »

Witam.
Treść zadania przedstawia się następująco.

Niech:
\(\displaystyle{ v(G)}\) - moc najliczniejszego skojarzenia,
\(\displaystyle{ r(G)}\) - moc najmniej licznego pokrycia wierzchołkowego,
\(\displaystyle{ a(G)}\) - moc najliczniejszego zbioru niezależnego
\(\displaystyle{ p(G)}\) - moc najmniej licznego pokrycia krawędziowego

Pokazać, że:
1) \(\displaystyle{ v(G) \le r(G)}\)
2) \(\displaystyle{ a(G) \le p(G)}\)
3) \(\displaystyle{ r(G) + a(G) = |V(G)|}\)

Jakieś wskazówki?
Pozdrawiam.
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

Re: Skojarzenie, pokrycie wierzchołkowe, a zbiór niezależny

Post autor: Mruczek »

To bardzo znane zależności.

1) Całe najliczniejsze skojarzenie musi być pokryte przez pokrycie wierzchołkowe, to znaczy z każdej krawędzi skojarzenia w pokryciu wierzchołkowym musi być przynajmniej jeden wierzchołek, a krawędzie skojarzenia są rozłączne wierzchołkowo, czyli wierzchołków w pokryciu musi być przynajmniej tyle co krawędzi skojarzenia.

2) Tutaj potrzebne jest dodatkowe założenie, że nie ma wierzchołków izolowanych (pokrycie krawędziowe musi istnieć). Każdy wierzchołek zbioru niezależnego musi być pokryty przez krawędź pokrycia krawędziowego. Nie istnieje krawędź pokrywająca dwa wierzchołki ze zbioru niezależnego, to znaczy że żeby pokryć cały zbiór niezależny musi być co najmniej tyle krawędzi w pokryciu co wielkość największego zbioru niezależnego.

3) To jedno z twierdzeń Gallai, dowód:

Kod: Zaznacz cały

http://smurf.mimuw.edu.pl/node/850
ODPOWIEDZ