WYKŁAD 4.

Skojarzenia

• Skojarzenie

w grafie G to niezależny zbiór

krawędzi (rozłączne, bez wspólnych konców).

• Skojarzenie M w G traktujemy jak podgraf G.
• Wierzchołki w V(M) nazywamy

M-nasyconymi.

• α’(G)

– moc największego skojarzenia w G

(tutaj moc = liczba krawędzi).

Graf krawędziowy

• Graf krawędziowy

danego grafu G

to L(G)=(V’,E’), gdzie

V’=E(G), a E’ składa się ze

wszystkich par przecinających się

krawędzi grafu G.

• Zatem α’(G) =α(L(G)).

L(G)

ac

ab

ad

be

de

df

dg

ef

Ilustracja

a

b

c

d

e

f

g

G

Ścieżki powiększające

• Dane jest skojarzenie M w grafie G.
• Ścieżka

powiększająca M w G

ma

końce poza V(M), a co drugą krawędź
w M.

Twierdzenie (Berge, 1957)

Skojarzenie M w grafie G ma moc |M|

= α’(G) (tzn. jest największe) wgdy w G
nie ma ścieżki powiększającej M.

Dowód Tw. Berge’a





M

M

M

,

M’

– skojarzenia w G, |

M

|<|

M’

|; spójrzmy na

M

Δ

M’

ścieżka powiększająca

M

(jej końce nie

należą do

M

)

Skojarzenia doskonałe

• Skojarzenie M w grafie G nazywamy

doskonałym

, gdy |M|=|V(G)|/2.

• Warunek konieczny: n=|V(G)| --

parzyste.

• Składowa (spójności)

– maksymalny

podgraf spójny (każde dwie składowe
grafu G są wierzchołkowo rozłączne).

Graf
Petersena

A

B

C

D

E

F

G

H

I

J

A

B

A

B

Warunek Tutte’a

• |S|=2, 4 składowe

nieparzyste

w G-S –

nie istnieje skojarzenie doskonałe.

• q(G)

– liczba nieparzystych składowych

S

Warunek Tutte’a

• Warunek (konieczny) Tutte’a:





|

|

:

)

(

S

S

G

q

G

V

S









Tw. Tutte’a

Twierdzenie (Tutte, 1947)

G ma skojarzenie doskonałe

wgdy

zachodzi warunek Tutte’a.

Dowód tw. Tutte’a (1)

• Przypuśćmy, że istnieje graf, który

spełnia warunek Tutte’a, ale nie ma

skojarzenia doskonałego.

• Niech G będzie takim grafem o

największej liczbie krawędzi.

• Dodanie dowolnej krawędzi do G nie

narusza warunku Tutte’a (

dlaczego?

),

więc musi prowadzić do pojawienia się

skojarzenia doskonałego.

Dowód tw. Tutte’a (2)

• K – zbiór wierzchołków o stopniu n-1

• G’=G-K

• Pokażemy, że w G’ wszystkie

składowe są grafami pełnymi.

• Wtedy, ponieważ q(G’)

≤

|K|,

G będzie mieć skojarzenie doskonałe

– sprzeczność.

Dowód tw. Tutte’a (3)

• Przypuśćmy, że pewna składowa grafu G’

nie jest pełna, a więc istnieją w niej a,b,c

takie, że ab i bc są krawędziami a ac nie

.

• Ponieważ b nie należy do K, to istnieje

wierzchołek d taki, że bd nie jest

krawędzią

.

• Niech

M_1

będzie skojarzeniem

doskonałym w G+ac, a

M_2

w G+bd.

• Oczywiście, ac jest w

M_1

, a bd w

M_2.

Dowód tw. Tutte’a (4)

•

Poprowadźmy w G maksymalną ścieżkę

P wychodzącą z d i na przemian
zawierającą krawędzie z

M_1

i

M_2

.

• P kończy się w b krawędzią z

M_1

(przypadek 1.)

LUB

w a lub c krawędzią z

M_2

(przypadek 2.)

, bo w przeciwnym

razie można by P kontynuować.

•

W przypadku 1

., C =P+bd jest

parzystym cyklem z co drugą krawędzią w

M_2

, a jedyną krawędzią w C poza G jest

bd (która jest w

M_2)

.

• Zastępując w

M_2

krawędzie z C, tymi z

C-

M_2

, otrzymujemy skojarzenie

doskonałe w G – sprzeczność

.

Ilustracja do 1. przypadku

a

b

c

d

   

2

2

M

C

C

M

M









C

jest skojarzeniem doskonałym w G - sprzeczność

Dowód tw. Tutte’a (5)

• W przypadku 2.,

P kończy się

krawędzią z

M_2.

Przyjmijmy, że jej

ostatnim wierzchołkiem jest a.

• C =P+ab+bd jest parzystym cyklem o

tej samej własności co poprzednio.

• Ponownie, zastępując w

M_2

krawędzie

z C, tymi z C-

M_2

, otrzymujemy

skojarzenie doskonałe w G –
sprzeczność

.

a

b

c

d

C=d...abd

jest skojarzeniem doskonałym w G -
sprzeczność

Ilustracja do 2. przypadku

   

2

2

M

C

C

M

M









Wniosek – Tw. Petersena

• Most (krawędź cięcia)

to taka krawędź e,

że G-e ma więcej składowych niż G. Np.

Petersen (1891)

Każdy 3-regularny

graf bez mostów ma skojarzenie
doskonałe.

(dowód na ćwiczeniach)