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