WYKŁAD 5.
Skojarzenia – ciąg dalszy
• Skojarzenie
w grafie G to niezależny
zbiór krawędzi (rozłączne, bez
wspólnych końców).
• α’(G) – moc największego skojarzenia
w G.
• Skojarzenie M w grafie G nazywamy
doskonałym
, gdy |M|=|V(G)|/2.
Tw. Tutte’a
Niech q(G) będzie liczbą
nieparzystych składowych grafu G.
Tutte (1947)
G ma skojarzenie
doskonałe wgdy
zachodzi warunek Tutte’a:
|
|
:
)
(
S
S
G
q
G
V
S
Pokrycia wierzchołkowe
Podzbiór U zbioru V(G) nazywamy
pokryciem wierzchołkowym
(krawędzi), jeśli każda krawędź grafu
G ma przynajmniej jeden koniec w U.
Moc najmniejszego pokrycia - β(G).
Trywialnie,
)
(
'
2
)
(
)
(
'
G
G
G
Skojarzenia w grafach 2-
dzielnych – tw. Königa
Twierdzenie (König, 1931)
Dla grafów dwudzielnych
α’(G)= β(G).
Dowód tw. Königa (1)
• Niech M będzie największym skojarzeniem w
grafie 2-dzielnym G o dwupodziale (A,B).
• Wystarczy pokazać, że istnieje pokrycie U mocy
|M|.
• Ścieżka
M-naprzemienna
ma jeden koniec w A-
V(M), drugi w B i co drugą krawędź w M .
• Konstrukcja zbioru U: do U zaliczamy po 1
końcu każdej krawędzi M, wybierając koniec w
B, gdy kończy się w nim jakaś M-naprzemienna
ścieżka, a koniec w A – w przeciwnym razie.
• Zatem U zawiera końce wszystkich M-
naprzemiennych ścieżek
(
bo są M-nasycone
).
Ilustracja dowodu Tw.
Königa
A
B
U
U
Dowód tw. Königa (2)
• Niech ab będzie krawędzią (a z A, a b
z B).
• Pokażemy, że a lub b jest w U.
• Tak jest, gdy ab jest krawędzią
skojarzenia M lub b jest końcem M-
naprzemiennej ścieżki.
• W przeciwnym razie a jest M-nasycony
(bo M jest maksymalne).
• Niech ab’ należy do M.
Dowód tw. Königa (3)
• Jeśli a nie jest w U, to b’ jest, tzn.
b’ jest końcem M-naprzemiennej
ścieżki, która omija a i b.
•Przedłużając tę ścieżkę o
krawędzie b’a i ab, otrzymujemy
M-naprzemienną ścieżkę kończącą
się w b.
• Zatem b należy do U.
Warunek (konieczny) Halla
na istnienie
skojarzenia
zawierającego
(nasycającego) zbiór A
|
|
|
)
(
:|
S
S
N
A
S
A
B
Tw. Halla
Tw. Halla (1935)
Dwudzielny graf G o
dwupodziale (A,B)
posiada skojarzenie
nasycające A wgdy
zachodzi warunek Halla:
|
|
|
)
(
:|
S
S
N
A
S
1. dowód Tw. Halla
• U – minimalne pokrycie E(G)
• Jeśli G nie ma skojarzenia nasycającego
A, to z Tw. Königa: |U|= β(G) = α’(G )<|A|
• Nie ma krawędzi miedzy A-U i B-U. Zatem
|
|
|
|
|
)
(
|
U
A
U
B
U
A
N
i warunek Halla nie zachodzi dla S=A-U.
Ilustracja 1. dowodu Tw.
Halla
A
B
U
U
2. dowód Tw. Halla
• Indukcja względem |A|; prawda dla |A|=1.
• Niech |A|>1 i załóżmy prawdziwość dla <|A|.
Dwa przypadki
• I
.
Warunek Halla zachodzi z nadmiarem, tzn
.
1
|
|
|
)
(
:|
S
S
N
A
S
• Usuńmy końce dowolnej krawędzi ab:
G’=G-{a,b}
• G’ wciąż spełnia warunek Halla i z
założenia ind. ma skojarzenie nasycające
A-{a}, które wraz z krawędzią ab tworzy
skojarzenie nasycające A.
2. dowód Tw. Halla –
Przypadek II
:
• Z założenia ind. podgraf G’ indukowany
w G przez S’ i N(S’) ma skojarzenie
nas. S’.
• Ale podgraf G’’=G-V(G’) też spełnia
warunek Halla i z zał. ind. ma
skojarzenie nas. A-S’.
• Rzeczywiście, gdyby istniał podzbiór S’’
w A-S’, dla którego |N(S’’)|<|S’’|, to
|'
|
|
)
'
(
:|
'
S
S
N
A
S
|'
|
|'
'
|
|
)
'
(
|
|
)
''
(
|
|
)
'
''
(
|
'
''
S
S
S
N
S
N
S
S
N
G
G
--
sprzeczność.
Ilustracja
S’
N(S’)
G’’
S’’
N(S’’)
3. dowód Tw. Halla
• Prosty wniosek z Tw. Tutte’a (do
samodzielnego zastanowienia się)
? ?
?
?
Tw.Gallai’a
• Przypomnijmy: α(G), α’(G), β(G).
• Podzbiór F zbioru E(G) nazywamy
pokryciem krawędziowym
(wierzchołków),
jeśli każdy wierzchołek jest końcem
przynajmniej jednej krawędzi z F.
• β’(G) – moc minimalnego pokrycia
• Tw. (Gallai ,1959)
Jeśli G nie ma
wierzchołków izolowanych, to α’(G) +
β’(G) =|V(G)|.
Ilustracja Tw. Gallai’a
3+6=9
Dowód Tw. Gallai’a
• Niech M będzie skojarzeniem, |M|= α’ .
• U=V(G)-V(M) jest zbiorem niezależnym.
• Dla każdego u w U, weźmy krawędź o
końcu w u.
• Te krawędzie wraz z M tworzą pokrycie.
• Zatem
'
)
'
2
(
'
|
U
|
|
M
|
'
n
n
Ilustracja
U
M
Dowód Tw. Gallai’a – c.d.
• Niech L będzie pokryciem, |L|= β’.
• Niech M będzie największym
skojarzeniem w H=G[L]=(V(G),L), a
U=V(G)-V(M).
• U jest zbiorem niezależnym w H, więc
|
|
2
|
|
|
|
|
|
M
n
U
M
L
a stąd
n
L
M
|
|
|
|
'
'
Ilustracja
Tw. dualne do Tw. Königa
• Łatwo pokazać, że α(G) + β(G) =|V(G)|
dla każdego grafu G
(ćwiczenia).
• Wniosek.
Dla każdego grafu
dwudzielnego bez wierzchołków
izolowanych α(G) = β’(G).
• Dowód
: Z tw. Gallai’a i powyższego
ćwiczenia α’(G) + β’(G) =α(G) + β(G), a
na podstawie Tw. Königa, α’(G) = β(G) .
Skojarzenia ułamkowe
• Skojarzenie ułamkowe
to funkcja w:E
[0,1] taka, że dla każdego wierzchołka v
e
v
e
w
1
)
(
• Suma wszystkich wag w(e) nie
przekracza n/2.
• Jeśli suma wag jest równa n/2, to
mówimy, że w jest
doskonałym
skojarzeniem ułamkowym.
Ilustracja
0.4
0.6
0.3
0.1 0.5
0.2
Suma = 2.1
0.5
0.5
0
0.5
0
1
Suma = 2.5