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