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.
Skojarzenie, pokrycie wierzchołkowe, a zbiór niezależny
-
- 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
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:
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