szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 maja 2018, o 21:38 
Użytkownik

Posty: 7
Lokalizacja: Warszawa
Witam.
Treść zadania przedstawia się następująco.

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

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

Jakieś wskazówki?
Pozdrawiam.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2018, o 21:56 
Użytkownik

Posty: 1083
Lokalizacja: Lublin/Warszawa
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: http://smurf.mimuw.edu.pl/node/850
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest funkcji ze zbioru {1,2,3,4} w zbiór {1,2}.  koki55  0
 Zbiór i podzbiory  wojtek6214  4
 zbiór zadań z kombinatoryki  maksiu1818  1
 Zbiór z powtórzeniami - zadanie 3  lel1101  4
 Kombinatoryka - Zbiór zadań  daniel0214  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl