WYKŁAD 6.

Kolorowanie krawędzi

Przykład:

W turnieju szachowym, w

którym biorą udział szachistki
A,B,C,D,E,F, pozostały do
rozegrania mecze pomiędzy
parami AE, AF, BC, BD, BF, CD,
DE, EF. W ilu rundach można
zakończyć ten turniej?

Ilustracja

A

B

C

D

E

F

Indeks chromatyczny

• Zbiór niezależny  skojarzenie
• Liczba chromatyczna χ 

indeks

chromatyczny χ’

• Indeks chromatyczny

to najmniejsza

liczba kolorów, którymi można
pomalować krawędzie grafu tak, by
krawędzie o wspólnym końcu miały
różne kolory.

Inaczej

• χ’(G)

to minimalna liczba skojarzeń,

którymi można pokryć zbiór E(G).

• χ’(G)= χ(L(G))

χ’=3

)

(

)

(

'

G

G







χ’=4

Tw. Vizinga

Tw. (Vizing,1964)

Dla każdego grafu G

1

)

(

)

(

'

)

(











G

G

G



Mówimy, że G jest

k-krawędziowo-

kolorowalny,

gdy

k

G 

)

(

'



Lemat

Lemat.

Dane są: liczba naturalna k, graf G i

wierzchołek v tego grafu. Jeśli

(i) wierzchołek v oraz wszyscy jego
sąsiedzi mają stopień nie większy niż k,

(ii) co najwyżej jeden sąsiad v ma stopień

równy k, oraz

(iii) graf G-v jest k-krawędziowo-
kolorowalny,

to G jest k-krawędziowo-kolorowalny.

Dowód Tw. Vizinga

• Indukcja względem n=|V(G)|.
• Prawda dla n=1.
• Załóżmy, że to prawda dla n i weźmy

dowolny graf G na n+1 wierzchołkach.

• Niech v będzie dowolnym wierzchołkiem G.

• Na podstawie zał. ind. G-v jest (Δ+1)-

krawędziowo-kolorowalny

.

•

Na podstawie Lematu z k= Δ+1, G jest

(Δ+1)-krawędziowo-kolorowalny

. 

Dowód Lematu

• Indukcja względem k; k=0,1 –

trywialne.

• Załóżmy prawdziwość dla k-1.

• Dodając, jeśli trzeba, wierzchołki

wiszące, można założyć, że jeden
sąsiad v ma stopień k, a pozostali
stopień k-1.

Ilustracja k=4

v

Dowód Lematu – c.d.

• c: E(G-v)



{1,...,k}

• N_i – zbiór sąsiadów v bez koloru i, i=1,...,k

FAKT

:

Istnieje c takie, że |N_l|=1 dla

pewnego l.

• Przyjmijmy b.s.o., że |N_k|=1, N_k={u}.

• G’=G bez krawędzi uv i bez krawędzi koloru

k

• G’ spełnia założenia Lematu z v i k-1, więc z

zał. ind. jest (k-1)-krawędziowo-kolorowalny.

• G=G’ plus skojarzenie, więc jest

k-krawędziowo-kolorowalny.



Ilustracja k=4

v

u

Ilustracja k=4 – c.d.

v

u

Dowód Faktu

FAKT

:

Istnieje c takie, że |N_l|=1 dla pewnego l.

Dowód:

Wybierzmy c tak, by zminimalizować

2

1

|

|

i

k

i

N





Zauważmy, że

1

2

1

)

(

2

|

|

1













k

v

d

N

k

i

i

Stąd, istnieją i i j: |N_i|<2, |N_j| --

nieparzyste.

Dowód Faktu – c.d.

• Przypuśćmy, że żadne |N_l| nie jest równe 1.

• Wtedy |N_i|=0, a |N_j|>2.

• Spójrzmy na maksymalną ścieżkę

naprzemienną P w kolorach i i j, zaczynającą

się w N_j.

• Jeśli P kończy się sąsiadem v, to musi on

należeć do N_j.

• Tak czy owak, zamieniając kolory i i j na P,

otrzymujemy kolorowanie c’, w którym 1 lub

2 wierzchołki ,,przeszły” z N_j do N_i; zatem







2

2

|

|

|'

|

i

i

N

N

--

sprzeczność.

Ilustracja dowodu Faktu

v

N_j

N_i=pusty

P

|

N’_i

|=2, |

N’_j

|=1: 4+1<0+9

Dwa typy grafów

Typ I :

χ’(G) =Δ(G):

np.

P_n, C_{2n}, K_{2n}

Typ I I:

χ’(G) =Δ(G)+1:

np.

C_{2n+1},

K_{2n+1}

Grafy dwudzielne? Graf Petersena ???

II

Grafy dwudzielne są typu

I (König 1916)

• Każdy dwudzielny graf G jest podgrafem

Δ(G)-regularnego dwudzielnego grafu H

(ćwiczenia).

• H posiada, zgodnie z Wnioskiem z Tw.

Halla, Δ(G) rozłącznych skojarzeń

doskonałych, które pokrywają cały zbiór

E(H)

(ćwiczenia).

• Zatem zbiór E(G) jest pokryty przez Δ(G)

rozłącznych skojarzeń, tzn. χ’(G) =Δ(G).

Faktoryzacja

• Jeśli regularny graf G jest typu I, tzn.

χ’(G)

=Δ(G),

to mówimy, że ma

faktoryzację,

zwaną też

1-faktoryzacją.

• Krawędzie tego samego koloru tworzą

skojarzenia doskonałe, zwane

1-faktorami

.

• Dwudzielne grafy regularne są

faktoryzowalne, grafy pełne K_{2n} też.

• Grafy pełne K_{2n+1} nie mogą mieć

faktoryzacji.

• Graf Petersena???

Faktoryzacja -- ilustracja

K_6

2-faktoryzacja

• 2-faktor

w grafie G to jego 2-

regularny, rozpięty podgraf H,
tzn. H jest sumą cykli i V(H)=V(G).

• 2-faktoryzacją

grafu 2k-

regularnego G nazywamy podział
E(G) na k rozłącznych 2-faktorów.

• 2-faktoryzacja ZAWSZE istnieje !!!

2-faktoryzacja -- ilustracja

Tw. Petersena o 2-

faktoryzacji

Tw

. Każdy 2k-regularny graf ma 2-

faktoryzację.

Lemat.

Jeśli wszystkie stopnie

wierzchołków w G są parzyste, to
krawędzie w G można zorientować
(skierować, ,,ostrzałkować”) tak, by do
każdego wierzchołka wchodziło tyle samo
strzałek co wychodziło.

Dowód Tw. Petersena

Dowód Tw.:

Rozważmy pomocniczy

graf 2-dzielny D z A=V(G) do

B=V(G), gdzie krawędź biegnie z a

do b wgdy gdy ab jest krawędzią w G

skierowaną od a do b.

• Graf D jest k-regularny, więc ma
1-faktoryzację.

• Każdy 1-faktor w D odpowiada 2-

faktorowi w G.

Ilustracja dowodu Tw.

Petersena

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

Dowód Lematu

Lemat.

Jeśli wszystkie stopnie wierzchołków w G są

parzyste, to krawędzie w G można zorientować

(skierować, ,,ostrzałkować”) tak, by do każdego

wierzchołka wchodziło tyle samo strzałek co

wychodziło.

Dowód:

Indukcja względem e(G) (e=0

prawda).

Dla e>0, G musi zawierać cykl C.

Zastosujmy

założenie indukcyjne do G’=(V,E-C)

i

dodajmy cykl C skierowany cyklicznie. 