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.
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2018, o 21:56 
Użytkownik

Posty: 1088
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 
 Funkcje zbioru w zbiór.  dee_jay  7
 Określ liczbę funkcji ze zbioru A w zbiór B  wbb  2
 4 losowanie z 8 elementow, potem z 7 - ten sam zbior  Forsakensky  7
 Dany jest zbiór Z={1,2,3,4,5,6,7,8}  Cynthia  3
 zbiór n-elementowy - zadanie 2  nina90  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl