WYKŁAD 1.

Grafy są wokół nas.

Pojęcia wstępne.

Przykład 1. ZOO

• Budujemy domowe zoo mając do

dyspozycji kozę, lwa, wilka, słonia,
jastrzębia, zająca i mysz.

• Cel: jak najmniej klatek,

zapewniając bezpieczeństwo
wszystkich zwierząt.

k

l

s

w

j

z

m

l

s

w

j

k

z

m

Przykład 2. Podział na

pary

• Dzielimy grupę 10 osób na pary.
• Każdy chce być w parze ze swoim

znajomym.

Graf
Petersena

A

B

C

D

E

F

G

H

I

J

Graf
Petersena

A

B

C

D

E

F

G

H

I

J

A

B

A

B

Przykład 3. Muzeum

• Zwiedzamy muzeum będące

labiryntem korytarzy, w którym
obrazy wiszą po obu stronach.

• Cel: przejść każdy korytarz 2 razy

i wrócić do wyjścia.

PLAN MUZEUM

a

b

c

d

e

a

b

c

d

e

Przykład 4.

Trzy domki i trzy

studnie

• Mieszkańcy trzech domków chcą

korzystać z trzech studni, ale tak
by nigdy nie musieli spotkać się w
drodze do nich.

• Czy jest to możliwe?

D1

D2

D3

S1

S2

S3

?

?

Pojęcie grafu

• Graf to para zbiorów

G=(V,E),

gdzie

• V

to skończony zbiór (

wierzchołków

)

• E

to zbiór 2-elementowych

podzbiorów zbioru V (

krawędzi

).















2

V

E

•Inaczej, graf to relacja symetryczna i antyzwrotna.
•Jeszcze inaczej: symetryczna 0-1 macierz kwadratowa
z zerami na przekątnej.

Grafy puste i pełne.

Dopełnienia grafów.

Graf

pełny

n

V 















2

V

E





























E

V

V

G

2

,

n

n

K

N 

n

K

Dopełnienie

grafu G:

Graf

pusty

Te same czy takie same?

a

b

c

d

G2

a

d

c

b

G3

a

b

c

d

G4

a

b

d

c

G5

a

b

d

e

G6

a

b

c

d

G1

Izomorfizm grafów

• Na przykład G1 jest izomorficzny z G2, bo
• f(a)=a, f(c)=c, f(b)=d, f(d)=b.

2

1

G

G 

2

1

:

V

V

f





2

1

)

(

)

(

E

v

f

u

f

E

uv







• G1=G5, G2=G3, wszystkie grafy mają tę
samą strukturę – są

izomorficzne.

Automorfizmy

• Automorfizm

to izomorfizm grafu w siebie.

a

b

c

d

G1

• Na przykład f(a)=a, f(d)=d, f(c)=b,

f(b)=c to 1 z 8 automorfizmów grafu G1.

Samodopełnianie

• G nazywamy

samodopełniającym

, gdy jest izomorficzny ze

swoim dopełnieniem.

Na
przykład

Stopnie wierzchołków

Zachodzi wzór

)

(

2

)

(

G

e

v

d

V

v

G







Stopniem wierzchołka

v nazywamy liczbę

d

G

(v)=d(v)

krawędzi grafu zawierających

(incydentnych z) v.

gdzie e(G)=|
E|.

Ciąg stopni grafu

Ciąg stopni grafu

Uwaga

:

Nie każdy ciąg liczb

naturalnych jest ciągiem stopni grafu,
np. 4,4,3,2,1 lub 3,3,3,2,2.





V

v

G

v

d



)

(

• Δ(G)= Δ to największy stopień
wierzchołka w grafie,
• δ(G)=δ to najmniejszy stopień.

•

Graf jest

k-regularny

, gdy wszystkie

wierzchołki mają stopień k.

Podgrafy

• Indukowane
• Rozpięte
• Ani takie, ani takie

Podgrafy indukowane

• Podgraf

grafu G=(V,E)

indukowany

przez podzbiór wierzchołków W to
graf G[W]=(W,E’), gdzie E’ składa
się ze

wszystkich

krawędzi grafu G

o

obu

końcach w W.

Podgraf indukowany -

ilustracja

W={a,b,c}, G[W] – kolor

czerwony

a

b

c

Podgrafy rozpięte

• Rozpięty

podgraf grafu G to graf

G’=(

V

,E’), gdzie E’ jest

podzbiorem E.

Podgrafy

• Podgrafem

grafu G=(V,E) nazywamy

graf G’=(V’,E’), gdzie V’ jest
podzbiorem V, a E’ jest podzbiorem E.

Spójność

• Graf jest

spójny,

gdy dla każdego podziału

V na dwa rozłączne i niepuste podzbiory A
i B istnieje krawędź z A do B (graf jest w 1
„kawałku”).

Inaczej









































2

2

:

,

B

A

E

B

A

B

A

V

Grafy niespójne

A

B

B1

B

2

Wierzchołek cięcia

• G-v=G[V-v]
• Wierzchołek v grafu spójnego G

nazywamy

wierzchołkiem cięcia

, gdy G-

v nie jest spójny.

• Inaczej, istnieje podział V na A i B, |A|, |

B|>1 :

 

v

B

A

































2

2

B

A

E

Cykle

• Cykl

to 2-regularny graf spójny.

• Inaczej

: cykl to graf, którego

wierzchołki można ponumerować
v_1,...,v_n, tak, że pary {v_1, v_2},
{v_2,v_3},...,{v_(n-1),v_n}, {v_n,
v_1} są jego jedynymi krawędziami.

• Notacja

C_n,

dla

n=3,4,...

Cykle : ilustracja

C_3=K_3

C_4

C_5

Ścieżki

• Ścieżka

to graf spójny o 2

wierzchołkach stopnia 1, a

pozostałych o stopniu 2.

• Inaczej

: ścieżka to graf, którego

wierzchołki można ponumerować

v_1,...,v_n, tak, że pary {v_1, v_2},

{v_2,v_3},...,{v_(n-1),v_n}, są jego

jedynymi krawędziami.

• Notacja

P_n,

dla

n=1,2,...