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