WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 1 / 14
REPETYTORIUM Z GRAFÓW
Graf = para uporządkowana dwóch zbiorów
Graf nieskierowany
Graf skierowany
G = (V, E), wierzchołki i krawędzie,
E
⊆
{
{i, j} : i
≠
j i i, j
∈
V
};
D = (V, A), wierzchołki i łuki,
A
⊆
V
×
V ;
incydencja, sąsiedztwo, zależność
d(v)
−
stopień wierzchołka v
d(v)
= 0 −
wierzchołek izolowany,
d(v)
= 1 −
liść
d(v) = d
+
(v) + d
−
(v)
−
stopień wierzchołka v :
d
+
(v)
−
stopień wyjściowy v ,
d
−
(v)
−
stopień wejściowy v
Pochodny graf G(D) = ( V, E
D
) dla grafu skierowanego D = (V, A):
{ i, j }
∈
E
D
⇔
( i, j )
∈
A
∨
( j, i )
∈
A dla i
≠
j
Graf pełny (dla | V | = n):
E =
{
{i, j} : i
≠
j i i, j
∈
V
};
| E | =
2
)
1
(
2
−
=
n
n
n
; ozn.
n
K
A = V
×
V ;
| A | =
2
n
Dopełnienie grafu:
G
= (
V
, E ) :
E
=
{
{i, j}: i, j
∈
V, i
≠
j, {i, j}
∉
E
}
D
= (V, A) :
A
= V
×
V \ A
Graf krawędziowy:
L
(G) = (E, L(E)) :
{e
1
, e
2
}
∈
L
(E)
⇔
e
1
i e
2
są zależne
L
(D) = (A, L(A)) :
(a
1
, a
2
)
∈
L(A)
⇔
a
1
i a
2
są zależne
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 2 / 14
Związki pomiędzy stopniami wierzch. i liczbą krawędzi (łuków):
E
i
d
V
i
2
)
(
=
∑
∈
A
i
d
V
i
2
)
(
=
∑
∈
,
A
i
d
i
d
V
i
V
i
=
=
∑
∑
∈
+
∈
−
)
(
)
(
Macierzowy opis grafu (dla | V | = n i | E | = m lub | A | = m):
•
Macierz
incydencji
I(G) =
m
j
n
i
ij
s
,...,
1
,...,
1
]
[
=
=
∈
=
przyp.
przec.
w
0
jesli
1
j
ij
e
i
s
I
(D) =
m
j
n
i
ij
s
,...,
1
,...,
1
]
[
=
=
=
=
−
=
przyp.
przec.
w
0
)
,
(
jesli
1
)
,
(
jesli
1
k
i
a
i
k
a
s
j
j
ij
•
Macierz
sąsiedztwa
B
(G) =
n
j
n
i
ij
b
,...,
1
,...,
1
]
[
=
=
∈
=
=
przyp.
przec.
w
0
}
,
{
jesli
1
E
j
i
b
b
ji
ij
B
(D) =
n
j
n
i
ij
b
,...,
1
,...,
1
]
[
=
=
∈
=
przyp.
przec.
w
0
)
,
(
jesli
1
A
j
i
b
ij
Izomorfizm grafów:
G
G
′
≅
∃
V
V
f
′
→
−
1
1
:
taka,
ż
e
∀
i, j
∈
V zachodzi
{i, j}
∈
E
⇔
{ f (i), f (j)}
∈
E
′
D
D
′
≅
∃
V
V
f
′
→
−
1
1
:
taka,
ż
e
∀
i, j
∈
V zachodzi
(i, j)
∈
A
⇔
(
f (i), f (j)
)
∈
A
′
Graf
dwudzielny
:
G = (V
1
∪
V
2
, E), V
1
∩
V
2
=
∅
wierzchołki w ka
ż
dym ze zbiorów V
1
i V
2
s
ą
parami niezale
ż
ne.
Graf
dwudzielny pełny
: oznaczenie
s
r
K
,
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 3 / 14
Graf
planarny
:
graf jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu
homeomorficznego z K
5
lub K
3, 3
(grafami
homeomorficznymi
z danym grafem nazywamy takie grafy,
które mo
ż
na z niego otrzyma
ć
przez podział kraw
ę
dzi dodatkowymi
wierzchołkami stopnia 2)
Droga
w grafie:
naprzemienny ci
ą
g wierzchołków
i kraw
ę
dzi grafu
( v
0
, e
1
, v
1
, e
2
, ..., v
t
−
1
, e
t
, v
t
),
spełniaj
ą
cy warunek
e
i
= {v
i
−
1
, v
i
} dla i = 1, ..., t
naprzemienny ci
ą
g wierzchołków
i łuków grafu
( v
0
, a
1
, v
1
, a
2
, ..., v
t
−
1
, a
t
, v
t
),
spełniaj
ą
cy warunek
a
i
= ( v
i
−
1
, v
i
) dla i = 1, ..., t
Droga
prosta
:
ż
adna kraw
ę
d
ź
si
ę
nie powtarza
ż
aden łuk si
ę
nie powtarza
Droga
elementarna
:
ż
aden wierzchołek si
ę
nie powtarza.
Cykl
w grafie:
droga zamkni
ę
t
ą
, dla której v
0
= v
t
i t
>
0
Istnienie drogi i cyklu
w grafie G o minimalnym stopniu
wierzchołka
δ
(G):
•
w grafie G istnieje droga elementarna o długo
ś
ci co najmniej
δ
(G),
•
dla
δ
(G)
≥
2 istnieje w grafie G cykl elementarny o długo
ś
ci co
najmniej
δ
(G)+1.
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 4 / 14
Graf
spójny
:
dla ka
ż
dej pary wierzchołków u
i v istnieje w nim droga z u do v
pochodny graf nieskierowny
jest spójny
Graf
silnie spójny
:
dla ka
ż
dej pary wierzchołków u
i v istnieje w nim droga z u do v
Składowa spójna
grafu:
podgraf danego grafu, który jest spójny i nie jest podgrafem innego
grafu spójnego.
Związek
liczby kraw
ę
dzi (m), wierzchołków (n) i składowych
spójnych (k) w grafie:
2
)
1
)(
(
)
(
+
−
−
≤
≤
−
k
n
k
n
m
k
n
Warunek
konieczny i dostateczny dwudzielności grafu:
dla n
≥
2 graf jest dwudzielny wtedy i tylko wtedy, kiedy nie zawiera
cyklu o nieparzystej długości.
Związek z liczbą ścian (f ) w grafie planarnym:
n – m + f = k + 1
Warunki
konieczne planarności grafu:
•
jeśli graf jest planarny i n
≥
3, to m
≤
3n – 6 ,
•
jeśli graf dwudzielny jest planarny i n
≥
3, to m
≤
2n – 4 ,
•
jeśli graf jest planarny, to musi zawierać co najmniej jeden
wierzchołek o stopniu mniejszym niż 6.
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 5 / 14
Metody przeszukiwania grafu:
•
przeszukiwanie grafu w głąb z „zamykaniem” wierzchołków,
•
przeszukiwanie grafu wszerz z usuwaniem „nowości”
wierzchołków.
Droga Eulera w grafie:
droga prosta, która zawiera
wszystkie krawędzie grafu
droga prosta, która zawiera
wszystkie łuki grafu
Cykl Eulera w grafie:
zamknięta droga Eulera
Warunek
konieczny i dostateczny istnienia cyklu Eulera:
graf jest spójny i dla każdego
wierzchołka jego stopień d(v) jest
liczbą parzystą
graf jest spójny i dla każdego
wierzchołka zachodzi
d
+
(v) = d
−
(v)
Warunek
konieczny i dostateczny istnienia drogi Eulera:
graf jest spójny i dla nie więcej
niż dwóch wierzchołków ich
stopień jest liczbą nieparzystą
graf jest spójny i albo dla każdego
wierzchołka zachodzi
d
+
(v) = d
−
(v), albo dla dokładnie
dwóch wierzchołków v
1
i v
2
ten
warunek nie zachodzi, ale
spełniona jest dla nich równość
d
+
(v
1
)–d
−
(v
1
)=d
−
(v
2
)–d
+
(v
2
)=1
Mosty są wykorzystywane w algorytmie Fleury’ego.
Droga Hamiltona w grafie:
droga elementarna, która zawiera wszystkie wierzchołki grafu
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 6 / 14
Cykl Hamiltona w grafie:
zamkniętą droga Hamiltona o długości V
Liczba cykli Hamiltona w grafie pełnym dla n
≥
3:
2
)!
1
(
−
n
(n
−
1)!
Warunki
dostateczne istnienia cyklu Hamiltona:
•
jeśli n
≥
3 i dla każdej pary
niezależnych wierzchołków v
i w zachodzi d(v) + d(w)
≥
n,
to graf ma cykl Hamiltona;
•
jeśli n
≥
3 i dla każdego
wierzchołka zachodzi d(v)
≥
2
n
,
to graf ma cykl Hamiltona;
•
jesli n
≥
3 i graf ma co
najmniej
2
2
)
2
)(
1
(
+
−
−
n
n
krawędzi, to ma on cykl
Hamiltona;
•
jeśli n
≥
2, graf jest silnie
spójny i bez pętli oraz dla
każdej pary niezależnych
wierzchołków v i w zachodzi
1
2
)
(
)
(
−
≥
+
n
w
d
v
d
, to graf ma
cykl Hamiltona;
•
je
ś
li n
≥
2, graf jest bez p
ę
tli
i dla ka
ż
dego wierzchołka
zachodzi
2
)
(
n
v
d
≥
+
oraz
2
)
(
n
v
d
≥
−
, to graf ma cykl
Hamiltona;
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 7 / 14
•
je
ś
li istnieje ci
ą
g (a
1
, a
2
, ..., a
n
),
w którym zachodzi
a
i
≤
i
⇒
a
n
−
i
≥
n – i dla i <
2
n
,
i dla którego sekwencja
wst
ę
puj
ą
ca stopni
wierzchołków grafu spełnia
warunek d
i
(G)
≥
a
i
, to graf ma
cykl Hamiltona.
•
je
ś
li graf jest silnie spójnym
turniejem
, to ma cykl
Hamiltona (ka
ż
dy turniej ma
drog
ę
Hamiltona).
Drzewo:
•
graf spójny bez cykli elementarnych,
•
graf o n
−
1 kraw
ę
dziach bez cykli elementarnych,
•
graf spójny o n
−
1 kraw
ę
dziach,
•
graf spójny, którego ka
ż
da kraw
ę
d
ź
jest mostem,
•
graf, którego ka
ż
de dwa wierzchołki s
ą
poł
ą
czone dokładnie jedn
ą
drog
ą
,
•
graf bez cykli elementarnych, w którym doł
ą
czenie nowej kraw
ę
dzi
tworzy dokładnie jeden cykl elementarny.
Las:
•
graf bez cykli elementarnych
Drzewo rozpinające
grafu G = (V, E):
•
drzewo G
T
= (V, T) takie,
ż
e T
⊆
E
Liczba
drzew rozpinaj
ą
cych w grafie pełnym
n
K (dla n
≥
2):
2
−
n
n
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 8 / 14
Kod
Prüfera
.
(Rozpinaj
ą
ce)
drzewa przeglądu
grafu w gł
ą
b i wszerz.
Dla G
T
= (V, T), które jest drzewem rozpinaj
ą
cym grafu G = (V, E):
•
T – zbiór
gałęzi
,
•
E \ T
– zbiór
cięciw
,
•
Ω
= {
e
C : e
∈
E \ T} – zbiór
cykli fundamentalnych
.
Przedstawienie cyklu prostego
w grafie spójnym G = (V, E):
dla dowolnego drzewa rozpinaj
ą
cego G
T
= (V, T) ka
ż
dy cykl prosty C
w grafie G mo
ż
na jednoznacznie przedstawi
ć
jako ró
ż
nic
ę
symetryczn
ą
cykli fundamentalnych:
C =
1
e
C
⊗
2
e
C
⊗
...
⊗
k
e
C
,
gdzie
{
}
k
e
e
...,
,
1
=
C
\
T
jest zbiorem ci
ę
ciw wzgl
ę
dem drzewa
G
T
.
Spójność krawędziowa
λλλλ
(G)
grafu spójnego
G
(dla
n
≥
2) to
najmniejsza moc zbioru rozspajaj
ą
cego ten graf;
graf jest
k-spójny krawędziowo
, je
ś
li
λ
(
G
)
≥
k
.
Spójność wierzchołkowa
κκκκ
(G)
grafu spójnego
G
(dla
n
≥
2) to
najmniejsza moc zbioru rozdzielaj
ą
cego ten graf;
graf jest
k-spójny
(
wierzchołkowo
), je
ś
li
κ
(
G
)
≥
k
.
κ
(
G
)
≤
λ
(
G
)
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 9 / 14
Związki
liczby dróg ł
ą
cz
ą
cych dwa dane wierzchołki grafu z liczb
ą
elementów w zbiorach rozspajaj
ą
cych i rozdzielaj
ą
cych te wierzch.:
•
maksymalna liczba dróg kraw
ę
dziowo rozł
ą
cznych, ł
ą
cz
ą
cych
dwa ró
ż
ne wierzchołki
v
i
w
w grafie spójnym, jest równa
minimalnej liczbie kraw
ę
dzi w zbiorze rozspajaj
ą
cym
v
i
w
,
•
maksymalna liczba dróg wierzchołkowo rozł
ą
cznych, ł
ą
cz
ą
cych
dwa ró
ż
ne wierzchołki nies
ą
siednie
v
i
w
w grafie spójnym, jest
równa minimalnej liczbie wierzchołków w zbiorze
rozdzielaj
ą
cym
v
i
w
.
Związki
liczby dróg ł
ą
cz
ą
cych pary ró
ż
nych wierzchołków w grafie z
odporno
ś
ci
ą
grafu na utrat
ę
spójno
ś
ci:
•
graf jest
k
-spójny kraw
ę
dziowo wtedy i tylko wtedy, gdy ka
ż
da
para ró
ż
nych jego wierzchołków jest poł
ą
czona co najmniej
k
drogami kraw
ę
dziowo rozł
ą
cznymi,
•
graf o co najmniej
k
+
1 wierzchołkach jest
k
-spójny
(wierzchołkowo) wtedy i tylko wtedy, gdy ka
ż
da para ró
ż
nych
jego wierzchołków jest poł
ą
czona co najmniej
k
drogami
wierzchołkowo rozł
ą
cznymi.
Uogólnione związki
liczby dróg ł
ą
cz
ą
cych dwa zbiory wierzchołków
z liczb
ą
wierzchołków rozdzielaj
ą
cych te zbiory:
•
uogólnieniem poj
ę
cia zbioru rozdzielaj
ą
cego jest
S-T
separator,
•
uogólnieniem poj
ę
cia zbioru dróg wierzchołkowo rozł
ą
cznych
jest
S-T
konektor,
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 10 / 14
•
je
ż
eli w grafie skierowanym
D
= (
V
,
A
) wybrano dwa podzbiory
S
,
T
⊆
V
oraz wyznaczono minimaln
ą
moc
S-T
separatora
równ
ą
s
, to istnieje
S-T
konektor
Q
= (
V
Q
,
A
Q
) grafu
D
o mocy
s
.
Związki
liczby dróg ł
ą
cz
ą
cych dwa dane wierzchołki grafu
skierowanego z liczb
ą
elementów w zbiorach rozspajaj
ą
cych i
rozdzielaj
ą
cych te wierzchołki:
•
je
ż
eli w grafie skierowanym
D
= (
V
,
A
) wybrano dwa ró
ż
ne
wierzchołki
v
i
w
, takie
ż
e (
v
,
w
)
∉
A
, to minimalna moc zbioru
rozdzielaj
ą
cego wierzchołki
v
i
w
jest równa maksymalnej
liczbie dróg wierzchołkowo rozł
ą
cznych z
v
do
w
;
•
je
ż
eli w grafie skierowanym
D
= (
V
,
A
) wybrano dwa ró
ż
ne
wierzchołki
v
i
w
, to minimalna moc zbioru rozspajaj
ą
cego
wierzchołki
v
i
w
jest równa maksymalnej liczbie dróg łukowo
rozł
ą
cznych z
v
do
w
.
Związki
liczby dróg ł
ą
cz
ą
cych pary ró
ż
nych wierzchołków w grafie
skierowanym z odporno
ś
ci
ą
grafu na utrat
ę
spójno
ś
ci:
•
graf skierowany jest
k
-spójny wierzchołkowo, je
ś
li dla ka
ż
dych
dwóch ró
ż
nych jego wierzchołków
v
i
w
istnieje co najmniej
k
dróg wierzchołkowo rozł
ą
cznych z
v
do
w
;
•
graf skierowany jest
k
-spójny łukowo, je
ś
li dla ka
ż
dych dwóch
ró
ż
nych jego wierzchołków
v
i
w
istnieje co najmniej
k
dróg
łukowo rozł
ą
cznych z
v
do
w
.
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 11 / 14
Sieć
= graf skierowany z wyró
ż
nionymi dwoma wierzchołkami
(
ź
ródło i uj
ś
cie) + przepustowo
ś
ci wszystkich łuków
Przepływ w sieci
ze
ź
ródła do uj
ś
cia = warto
ś
ci przepływów przez
wszystkie łuki, mieszcz
ą
ce si
ę
w granicach przepustowo
ś
ci i
spełniaj
ą
ce warunek zachowania przepływu we wszystkich
wierzchołkach poza
ź
ródłem i uj
ś
ciem.
Wartość przepływu
przez sie
ć
= bilans wypływu i wpływu do
ź
ródła
= bilans wpływu i wypływu z uj
ś
cia.
Przekrój sieci
= zbiór łuków wychodz
ą
cych z zadanego zbioru
wierzchołków.
Przepływ przez przekrój
= suma przepływów przez łuki przekroju.
Przepustowość przekroju
= suma przepustowo
ś
ci łuków przekroju.
Minimalny przekrój
sieci = przekrój zadany zbiorem wierzchołków
zawieraj
ą
cym
ź
ródło, którego przepustowo
ść
jest minimalna.
Związek
przepustowo
ś
ci minimalnego przekroju z maksymalnym
przepływem przez sie
ć
:
•
w ka
ż
dej sieci maksymalna warto
ść
przepływu ze
ź
ródła do
uj
ś
cia jest równa przepustowo
ś
ci minimalnego przekroju
pomi
ę
dzy
ź
ródłem i uj
ś
ciem.
Podstawa wyznaczania
maksymalnego przepływu:
•
przepływ w sieci jest maksymalny wtedy i tylko wtedy, kiedy
nie istnieje dla niego
ś
cie
ż
ka powi
ę
kszaj
ą
ca ze
ź
ródła do uj
ś
cia.
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 12 / 14
Skojarzenie
w grafie = podzbiór kraw
ę
dzi, które s
ą
parami niezale
ż
ne.
Zbiór wewnętrznie stabilny
wierzchołków = podzbiór
wierzchołków, które s
ą
parami niezale
ż
ne.
Podstawa wyznaczania
skojarzenia maksymalnej mocy:
•
skojarzenie w grafie ma maksymaln
ą
moc wtedy i tylko wtedy,
kiedy ten graf nie zawiera drogi powi
ę
kszaj
ą
cej wzgl
ę
dem tego
skojarzenia.
Pokrycie krawędziowe
grafu = taki podzbiór jego kraw
ę
dzi,
ż
e
ka
ż
dy wierzchołek grafu jest incydentny z co najmniej jedn
ą
kraw
ę
dzi
ą
z tego podzbioru.
Pokrycie wierzchołkowe
grafu = taki podzbiór jego wierzchołków,
ż
e ka
ż
da kraw
ę
d
ź
grafu jest incydentna z co najmniej jednym
wierzchołkiem z tego podzbioru.
Związki
pomi
ę
dzy mocami skojarzenia, zbioru wewn
ę
trznie
stabilnego wierzchołków i mocami pokry
ć
:
•
maksymalna moc zbioru wewn
ę
trznie stabilnego wierzchołków i
minimalna moc pokrycia wierzchołkowego sumuj
ą
si
ę
do liczby
wierzchołków w grafie,
•
maksymalna moc skojarzenia i minimalna moc pokrycia
kraw
ę
dziowego tak
ż
e sumuj
ą
si
ę
do liczby wierzchołków w
grafie,
•
maksymalna moc skojarzenia nie przekracza minimalnej mocy
pokrycia wierzchołkowego,
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 13 / 14
•
maksymalna moc zbioru wewn
ę
trzne stabilnego wierzchołków
nie przekracza minimalnej mocy pokrycia kraw
ę
dziowego,
•
je
ś
li graf jest dwudzielny, to maksymalna moc skojarzenia jest
równa minimalnej mocy pokrycia wierzchołkowego.
Skojarzenie doskonałe
= takie skojarzenie, wzgl
ę
dem którego
wszystkie wierzchołki tego grafu s
ą
nasycone.
Warunek konieczny i dostateczny istnienia
skojarzenia
doskonałego:
•
graf
G
= (
V
,
E
) ma skojarzenie doskonałe wtedy i tylko wtedy,
kiedy liczba składowych spójnych o nieparzystej liczbie
wierzchołków w podgrafie grafu
G
, indukowanym przez
podzbiór wierzchołków
V
\
S
, nie przekracza liczby
wierzchołków w zbiorze
S
dla ka
ż
dego wyboru
S
⊆
V
.
Skojarzenie pełne względem zbioru V
1
(lub
V
2
) w grafie
dwudzielnym
G
= (
V
1
∪
V
2
,
E
) = takie skojarzenie, wzgl
ę
dem którego
wszystkie wierzchołki
v
∈
V
1
(lub
v
∈
V
2
) s
ą
nasycone.
Warunek konieczny i dostateczny istnienia
skojarzenia pełnego
wzgl
ę
dem
V
1
:
•
w grafie dwudzielnym istnieje skojarzenie pełne wzgl
ę
dem
zbioru
V
1
wtedy i tylko wtedy, kiedy zbiór takich wierzchołków
v
2
∈
V
2
, dla których istnieje w zbiorze
S
⊆
V
1
co najmniej jeden
wierzchołek s
ą
siedni, liczy co najmniej tyle samo elementów co
zbiór
S
dla ka
ż
dego wyboru
S
⊆
V
1
.
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
GRAFY i SIECI (8)
J.Sikorski
Strona 14 / 14
Graf jest
k-barwny
, je
ś
li mo
ż
na
prawidłowo
pokolorowa
ć
jego
wierzchołki, tzn. ka
ż
demu wierzchołkowi mo
ż
na przyporz
ą
dkowa
ć
jeden z
k
kolorów w taki sposób,
ż
e wierzchołki s
ą
siednie maj
ą
ró
ż
ne kolory.
Liczba chromatyczna
grafu
χ
(
G
) = najmniejsza liczba naturalna
k
,
dla której graf ten jest
k
-barwny.
Ile barw
potrzeba do prawidłowego pokolorowania grafu?
•
ka
ż
dy graf planarny jest czterobarwny,
•
ka
ż
dy graf planarny, który nie zawiera podgrafu izomorficznego
z K
3
, jest trzybarwny,
•
graf jest dwubarwny wtedy i tylko wtedy, kiedy nie zawiera
cykli o nieparzystej długo
ś
ci,
•
ka
ż
de drzewo jest dwubarwne,
•
ka
ż
dy graf dwudzielny jest dwubarwny,
•
graf pełny
n
K
jest n-barwny.