kolorowanie krawędzi

1

Kolorowanie krawędzi grafu

Przyporządkowanie krawędziom grafu liczb naturalnych,
symbolizujących kolory. E(G)

→ C, C – zbiór kolorów

Kolorowanie krawędzi nazywamy właściwym (prawidłowym,
legalnym), gdy żadne dwie sąsiednie krawędzie nie mają tego samego
koloru.

Krawędzie sąsiednie to krawędzie mające wspólny wierzchołek.

Optymalne kolorowanie krawędzi – kolorowanie legalne przy użyciu
najmniejszej liczby kolorów.

Indeks chromatyczny

χ’(G) – minimalna liczba kolorów niezbędna do

legalnego kolorowania krawędzi grafu G.

Graf G jest k-krawędziowo-kolorowalny, gdy

χ’(G) ≤ k

Podobnie jak dla kolorowania wierzchołków, zadanie kolorowania
krawędzi jest problemem NP-trudnym.

Twierdzenie Vizinga

Każdy graf o maksymalnym stopniu wierzchołków

∆ można

pokolorować krawędziowo

∆+1 kolorami.

χ’(G) ≤ ∆+1

Kolorowanie krawędzi można sprowadzić do kolorowania
wierzchołków.

W tym celu dla grafu G tworzymy graf krawędziowy L(G).
Kolorowanie krawędzi grafu G jest równoważne kolorowaniu
wierzchołków grafu krawędziowego L(G).

kolorowanie krawędzi

2

Graf krawędziowy.

Graf krawędziowy (ang. line graph) grafu G to

graf F = L(G) którego:

• zbiorem wierzchołków jest zbiór krawędzi grafu G:

V(F) = E(G), natomiast

• zbiorem krawędzi E(F) jest zbiór par elementów zbioru E(G)

(zbioru krawędzi grafu G). Przy czym:

- W grafach nieskierowanych:

jest to zbiór par krawędzi przecinających się - wierzchołki {v

1

,v

2

},

{v

3

,v

4

} grafu F są połączone wtedy i tylko wtedy gdy v

1

=v

3

lub

v

1

=v

4

lub v

2

=v

3

lub v

2

=v

4

.

- W grafach skierowanych:

bierzemy tylko te pary krawędzi, gdy koniec jednej jest
początkiem drugiej - od wierzchołka (v

1

,v

2

) do wierzchołka

(v

3

,v

4

) grafu F prowadzi krawędź wtedy i tylko wtedy gdy

v

2

=v

3

.

Można to rozumieć tak, że krawędzie grafu G traktujemy jako
wierzchołki tworząc graf F, a wierzchołki grafu F łączymy
krawędziami wtedy, gdy "istnieje przejście" pomiędzy krawędziami
grafu G odpowiadającym odpowiednim wierzchołkom grafu F.

kolorowanie krawędzi

3

Kolorowanie krawędzi grafu - graf krawędziowy

Przykład 1

macierz incydencji

macierz sąsiedztwa grafu krawędziowego.

ab

bc

bd

be

ab

bc

bd

be

a

1

ab

1

1

1

b

1

1

1

1

bc

1

1

1

c

1

bd

1

1

1

d

1

be

1

1

1

e

1

j

a

b

c

d

e

f

h

a

e

b

d

c

ab

be

bd

bc

kolorowanie krawędzi

4

macierz incydencji

macierz sąsiedztwa grafu kraw.

ab ad bc bd be ce de df eh fh f j

ab ad bc bd be ce de df eh fh f j

a

1

1

ab

1

1

1

1

b

1

1

1

1

ad

1

1

1

1

c

1

1

bc

1

1

1

1

d

1

1

1

1

bd

1

1

1

1

1

1

e

1

1

1

1

be

1

1

1

1

1

1

f

1

1 1

ce

1

1

1

1

g

de

1

1

1

1

1

1

h

1

1

df

1

1

1

1 1

j

1

eh

1

1

1

1

fh

1

1

1

f j

1

1

ab

ad

bc

bd

be

ce

de

df

eh

f

h

f

j

j

a

b

c

d

e

f

h

kolorowanie krawędzi

5

Kolorowanie otrzymanego grafu krawędziowego

etap 1

etap 2











etap 3











4 kolory

ab

3

ad

2

bc

2

bd

1

be

4

ce

de

3

df

4

eh

f h

f j

start

ab3

ad2

bc2

bd1

be4

ce

1

de3

df4

eh

2

f h

f j

start

ab3

ad2

bc2

bd1

be4

ce1

de3

df4

eh2

f h

1

f j

2

start

kolorowanie krawędzi

6

kliki 4 wierzch

1

2

3

4

bd ad ab be
ce bc de df
fh eh

fj

a

b

c

d

e

f

h

j

ab

3

ad

2

bc

2

bd

1

be4

ce

1

de

3

df

4

eh

2

f h

1

f j

2

ab

3

ad

2

bc

2

bd

1

be4

ce

1

de

3

df

4

eh

2

f h

1

f j

2

ab

3

ad

2

bc

2

bd

1

be

4

ce

1

de

3

df

4

eh

2

f h

1

f j

2

start

kolorowanie krawędzi

7

Przykład 2
macierz sąsiedztwa

a

b

c

d

e

f

a

x

1

1

1

1

0

b

1

x

0

1

1

0

c

1

0

x

1

0

1

d

1

1

1

x

0

1

e

1

1

0

0

x

0

f

0

0

1

1

0

x

macierz incydencji

ab

ac

ad

ae

be

bd

cd cf df

a

1

1

1

1

0

0

0

0

0

b

1

0

0

0

1

1

0

0

0

c

0

1

0

0

0

0

1

1

0

d

0

0

1

0

0

1

1

0

1

e

0

0

0

1

1

0

0

0

0

f

0

0

0

0

0

0

0

1

1

graf krawędziowy - macierz sąsiedztwa

ab ac ad ae be bd cd cf

.

df

.

ab x 1 1 1 1 1 0 0 0

ac 1 x 1 1 0 0 1 1 0

ad 1 1 x 1 0 1 1 0 1
ae 1 1 1 x 1 0 0 0 0
be 1 0 0 1 x 1 0 0 0
bd 1 0 1 0 1 x 1 0 1

cd 0 1 1 0 0 1 x 1 1

cf 0 1 0 0 0 0 1 x 1

df 0 0 1 0 0 1 1 1 x

f

a

e

b

c

d

f

a

e

b

c

d

ab

ac

bd

ad

be

cf

ae

df

cd

kolorowanie krawędzi

8

kolorowanie grafu krawędziowego (alg. sekwencyjny)

v ab ac ad ae be bd cd cf df

macierz sąsiedztwa

v \

kol

1

2

3

4

2

4

1

3

2

ab ac ad ae be bd cd cf df

ab 1

ab x 1 1 1 1 1 0 0 0

ac 2

1

ac 1 x 1 1 0 0 1 1 0

ad 3

1

2

ad 1 1 x 1 0 1 1 0 1

ae 4

1

2

3

ae 1 1 1 x 1 0 0 0 0

be 2

1

4

be 1 0 0 1 x 1 0 0 0

bd 4

1

3

2

bd 1 0 1 0 1 x 1 0 1

cd 1

2

3

4

cd 0 1 1 0 0 1 x 1 1

cf

3

2

1

cf 0 1 0 0 0 0 1 x 1

df 2

3

4

1

3

df 0 0 1 0 0 1 1 1 x

nr koloru

1

2

3

4

kolor

wierzchołki

ab, cd

ac, be, df

ad, cf

ae, bd

ab

ac

bd

ad

be

cf

ae

df

cd

f

a

e

b

c

d

ab

ac

bd

ad

be

cf

ae

df

cd

kolorowanie krawędzi

9

a

e

b

c

d

f

g

Przykład 3

graf -











macierz sąsiedztwa

macierz incydencji

a b c d e f g

ab ac ad be de df dg ef

a x 1 1 1 0 0 0

a 1 1 1

b 1 x 1 0 0 0 0

b 1

1

c 1 0 x 0 0 0 0

c

1

d 1 0 0 x 1 1 1

d

1

1 1 1

e 0 1 0 1 x 0 1

e

1 1

1

f

0 0 0 1 0 x 1

f

1

1

g 0 0 0 0 0 0 x

g

1

graf krawędziowy - macierz sąsiedztwa

kolorowanie (sekwencyjne)

2 3 1 1 2 3 4 4

kol

1 2 3 2 1 2 4 3

ab ac ad be de df dg ef

v ab ac ad be de df dg ef

ab x 1 1 1 0 0 0 0 1 ab

ac 1 x 1 0 0 0 0 0 2 ac 1

ad 1 1 x 0 1 1 1 0 3 ad 1 2

be 1 0 0 x 1 0 0 1 2 be 1

de 0 0 1 1 x 1 1 1 1 de

3 2

df 0 0 1 0 1 x 1 1 2 df

3 1

dg 0 0 1 0 1 1 x 0 4 dg

3 1 2

ef 0 0 0 1 1 1 0 x 3 ef

2 1 2

kolorowanie krawędzi

10

1

2

3

4

wierzchołki

ab

1

ac

2

ad

3

be

4

de

5

df

6

dg

7

ef

8

kolory

1

2

3

2

1 2

4 3

graf krawędziowy - macierz sąsiedztwa i kolorowanie LF

2

3

1

1

2

3

4

4

kolor uporz st

ab ac ad be de df dg ef

2

4 3 ab x 1 1 1 0 0 0 0

3

8 2 ac 1 x 1 0 0 0 0 0

1

1 5 ad 1 1 x 0 1 1 1 0

1

5 3 be 1 0 0 x 1 0 0 1

2

2 5 de 0 0 1 1 x 1 1 1

3

3 4 df 0 0 1 0 1 x 1 1

4

6 3 dg 0 0 1 0 1 1 x 0

4

7 3 ef 0 0 0 1 1 1 0 x

Też 4 kolory - mniej nie będzie, bo graf zawiera klikę 4 wierzchołków
(ad, de, dg, df ) .

ab

ef

ac

ad

be

dg

de

df

a

e

b

c

d

f

g