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.