Ruciński A Teoria Grafów 1, wyklad5

background image

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.

background image

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

background image

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

background image

Skojarzenia w grafach 2-

dzielnych – tw. Königa

Twierdzenie (König, 1931)

Dla grafów dwudzielnych

α’(G)= β(G).

background image

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

).

background image

Ilustracja dowodu Tw.

Königa

A

B

U

U

background image

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.

background image

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.



background image

Warunek (konieczny) Halla

na istnienie

skojarzenia

zawierającego

(nasycającego) zbiór A

|

|

|

)

(

:|

S

S

N

A

S

A

B

background image

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

background image

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.

background image

Ilustracja 1. dowodu Tw.

Halla

A

B

U

U

background image

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.

background image

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ść.

background image

Ilustracja

S’

N(S’)

G’’

S’’

N(S’’)

background image

3. dowód Tw. Halla

• Prosty wniosek z Tw. Tutte’a (do

samodzielnego zastanowienia się)

? ?

?

?

background image

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)|.

background image

Ilustracja Tw. Gallai’a

3+6=9

background image

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

background image

Ilustracja

U

M

background image

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

|

|

|

|

'

'

background image

Ilustracja

background image

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) . 

background image

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.

background image

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


Document Outline


Wyszukiwarka

Podobne podstrony:
Ruciński A Teoria Grafów 1, wyklad6
Ruciński A Teoria Grafów 1, wyklad1
Ruciński A Teoria Grafów 1, wyklad10
Ruciński A Teoria Grafów 1, wyklad12
Ruciński A Teoria Grafów 1, wyklad4

więcej podobnych podstron