5.05.08

Dr inż. Krzysztof Lisiecki

1

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

2

Reguły gry (1):

Nie używamy
telefonów

Uczymy się
systematycznie

Zaliczamy

w terminie

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

3

Wprowadzenie do teorii grafów

Kontakt:



konsultacje poniedziałek 8.45 – 10.15
(pokój wykładowców)



e-mail :

[e-mail]

lub

[e-mail]



http:

www.lisiecki.org.pl

(materiały dydaktyczne,

terminy, ważne komunikaty)



tel. do pok. 512 (akwarium) (0-42) 631-36-15

5.05.08

Dr inż. Krzysztof Lisiecki

4

Reguły gry:

Sposób zaliczenia przedmiotu:
• Kolokwium wykładowe (30 pytań, każde 1p.)
• Praca domowa max. 6 punktów
• Przeliczanie punktów

na oceny

5

32-36 p.

4,5

30-31 p.

4

27-29 p.

3,5

24-26 p.

3

18-23 p.

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

5

Reguły gry (3):

• Terminy wykładów:

poniedziałki 10.15-12.00

• Termin zaliczenia – przedostatni wykład

2.06.2007r

. (poniedziałek) godz.

10.15

• Termin oddania pracy domowej - 9.06

(ostatni wykład)

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

6

Wprowadzenie do teorii grafów

Czy można przejść przez wszystkie mosty, przez
każdy przechodząc dokładnie jeden raz?

5.05.08

Dr inż. Krzysztof Lisiecki

7

Wprowadzenie do teorii grafów

x

rzeka Pregoła

wyspa

Kneiphof

Czy można przejść przez wszystkie mosty, przez
każdy przechodząc dokładnie jeden raz?

5.05.08

Dr inż. Krzysztof Lisiecki

8

Wprowadzenie do teorii grafów

Odpowiedź na postawione pytanie jest
negatywna i wynika z twierdzenia, które
zapoczątkowało teorię grafów:

W grafie można znaleźć cykl Eulera
wtedy i tylko wtedy, gdy graf jest spójny i
każdy jego wierzchołek ma parzysty
stopień.

5.05.08

Dr inż. Krzysztof Lisiecki

9

Wprowadzenie do teorii grafów

Grafem nazywamy parę

G=(X,G), złożoną

ze skończonego zbioru punktów X oraz
skończonego zbioru linii G.

Punkty ze zbioru X nazywamy
wierzchołkami grafu

G, a linie zbioru G

krawędziami grafu.

5.05.08

Dr inż. Krzysztof Lisiecki

10

Wprowadzenie do teorii grafów

Krawędzie stanowią połączenia pomiędzy
wierzchołkami grafu.

Dopuszczamy przy tym, aby krawędź
łączyła wierzchołek sam ze sobą.
Nazywamy ją wtedy pętlą

.

5.05.08

Dr inż. Krzysztof Lisiecki

11

Wprowadzenie do teorii grafów

Schematycznie graf przedstawiamy w

postaci rysunku.

5.05.08

Dr inż. Krzysztof Lisiecki

12

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

13

Wprowadzenie do teorii grafów

Zagadnienie mostów królewieckich

(L.Euler, 1736)

Zagadnienie najkrótszej drogi

(algorytm Dijkstry)

Problem chińskiego listonosza

(Mei Ku Kwan, 1962)

Problem komiwojażera

(cykl Hamiltona)

5.05.08

Dr inż. Krzysztof Lisiecki

14

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

15

Wprowadzenie do teorii grafów

Inne zastosowania

Analiza wzorów strukturalnych

związków chemicznych
Analiza obwodów elektrycznych
Problemy kolorowania map

(twierdzenie o czterech barwach)
Problem kojarzenia małżeństw

5.05.08

Dr inż. Krzysztof Lisiecki

16

Wprowadzenie do teorii grafów

Krawędź łączącą wierzchołki X

i

oraz X

j

będziemy zapisywać jako parę
nieuporządkowaną {X

i

, X

j

} . Gdy nie da

się stwierdzić, który z wierzchołków jest
początkiem, a który końcem krawędzi to
taki graf nazywamy nieskierowanym.

5.05.08

Dr inż. Krzysztof Lisiecki

17

Wprowadzenie do teorii grafów

Gdy określimy, który z wierzchołków jest
początkiem, a który końcem krawędzi, to
wówczas taką krawędź nazywamy łukiem.
Łuk łączący wierzchołek X

i

z

wierzchołkiem X

j

(od wierzchołka X

i

do

wierzchołka X

j

) będziemy zapisywać jako

parę uporządkowaną (X

i

, X

j

).

5.05.08

Dr inż. Krzysztof Lisiecki

18

Wprowadzenie do teorii grafów

Graf

G=(X,G), nazywamy nieskierowanym

(niezorientowanym) , gdy zbiór G składa się z

samych krawędzi.

5.05.08

Dr inż. Krzysztof Lisiecki

19

Wprowadzenie do teorii grafów

Graf

G=(X,G), nazywamy digrafem

(directed graph) lub grafem skierowanym
(zorientowanym), gdy zbiór G składa się z
samych łuków.

5.05.08

Dr inż. Krzysztof Lisiecki

20

Wprowadzenie do teorii grafów

Grafem pustym nazywamy graf składający
się jedynie z wierzchołków, nie zawierający
żadnych krawędzi.

5.05.08

Dr inż. Krzysztof Lisiecki

21

Wprowadzenie do teorii grafów

Podgrafem grafu

G=(X,G), nazywamy

każdy graf

G’=(X’,G’) taki, że

X’X oraz G’  G .

Dopuszczamy przypadki, gdy

X’=X lub G’=G .

5.05.08

Dr inż. Krzysztof Lisiecki

22

Wprowadzenie do teorii grafów

Przykładem podgrafu danego grafu jest on
sam.
Przykładem podgrafu jest także dowolny
graf powstały z danego grafu przez
usunięcie z niego dowolnej liczby krawędzi
(nawet wszystkich ) lub dowolnej liczby
wierzchołków (nie wszystkich)

5.05.08

Dr inż. Krzysztof Lisiecki

23

Wprowadzenie do teorii grafów

Przykład podgrafu

5.05.08

Dr inż. Krzysztof Lisiecki

24

Wprowadzenie do teorii grafów

Grafem prostym nazywamy graf, który nie
zawiera pętli i, w którym zbiór krawędzi
jest zbiorem bez powtórzeń.

Multigrafem nazywamy graf, w którym
zbiór krawędzi zawiera powtórzenia.

5.05.08

Dr inż. Krzysztof Lisiecki

25

Wprowadzenie do teorii grafów

Grafem

zupełnym

(grafem

pełnym)

nazywamy graf, w którym dla każdej pary
wierzchołków istnieje krawędź łącząca te
wierzchołki.
Graf zupełny o n wierzchołkach oznaczamy
często K

n

5.05.08

Dr inż. Krzysztof Lisiecki

26

Wprowadzenie do teorii grafów

Przykłady grafów zupełnych

5.05.08

Dr inż. Krzysztof Lisiecki

27

Wprowadzenie do teorii grafów

Przykłady grafów zupełnych

5.05.08

Dr inż. Krzysztof Lisiecki

28

Wprowadzenie do teorii grafów

Przykłady grafów zupełnych

5.05.08

Dr inż. Krzysztof Lisiecki

29

Wprowadzenie do teorii grafów

Dopełnieniem grafu

G nazywamy graf

o tym samym zbiorze wierzchołków, który
zawiera te wszystkie krawędzie grafu
zupełnego o zbiorze wierzchołków , które
nie występują w grafie

G.

5.05.08

Dr inż. Krzysztof Lisiecki

30

Wprowadzenie do teorii grafów

Wymiarem grafu

G nazywamy liczbę jego

wierzchołków. Oznaczamy ją dim

G

5.05.08

Dr inż. Krzysztof Lisiecki

31

Wprowadzenie do teorii grafów

 

Grafem rzadkim nazywamy graf, w którym

liczba krawędzi ( łuków) jest dużo mniejsza od
kwadratu liczby wierzchołków

Grafem gęstym nazywamy graf, w którym liczba
krawędzi ( łuków) jest bliska kwadratowi liczby
wierzchołków.

5.05.08

Dr inż. Krzysztof Lisiecki

32

Wprowadzenie do teorii grafów

Jeżeli do wierzchołka X

i

„dochodzi” krawędź g

k

,

to mówimy, że wierzchołek X

i

jest incydentny z

krawędzią g

k

. Dwa wierzchołki incydentne z tą

samą krawędzią nazywamy sąsiednimi lub
zależnymi.
Inaczej mówiąc, dwa wierzchołki sąsiadują ze
sobą, jeżeli istnieje krawędź (łuk) łącząca te
wierzchołki.

5.05.08

Dr inż. Krzysztof Lisiecki

33

Wprowadzenie do teorii grafów

Mówimy, że wierzchołek jest izolowany, jeśli nie
jest incydentny z żadną krawędzią.

5.05.08

Dr inż. Krzysztof Lisiecki

34

Wprowadzenie do teorii grafów

Stopniem wierzchołka w grafie (nieskierowanym)
nazywamy liczbę krawędzi grafu incydentnych z
tym wierzchołkiem. stopień wierzchołka

X

i

oznaczać będziemy deg

X

i

.

Każda pętla w wierzchołku zwiększa jego stopień
o 2.

Wierzchołek izolowany ma stopień zero.

5.05.08

Dr inż. Krzysztof Lisiecki

35

Wprowadzenie do teorii grafów

Przykład

5.05.08

Dr inż. Krzysztof Lisiecki

36

Wprowadzenie do teorii grafów

Jeśli graf posiada m krawędzi oraz

∑

=

=

n

i

i

m

X

1

2

deg

{

}

n

X

X

X

,...,

1

=

to

5.05.08

Dr inż. Krzysztof Lisiecki

37

Wprowadzenie do teorii grafów

Wniosek

W dowolnym grafie jest parzysta ilość
wierzchołków nieparzystego stopnia. 

5.05.08

Dr inż. Krzysztof Lisiecki

38

Wprowadzenie do teorii grafów

Graf nazywamy regularnym, gdy każdy
jego wierzchołek ma ten sam stopień

.

5.05.08

Dr inż. Krzysztof Lisiecki

39

Wprowadzenie do teorii grafów

Drogą w grafie

G (zorientowanym lub nie)

nazywamy każdy ciąg

{

}

X g X

X g X

n

n

n

1

1

2

1

, ,

,...,

,

,

+

taki, że koniec jednej krawędzi (łuku) jest
początkiem innej.

X

X

X g

g

G

n

n

1

1

1

,...,

,

,...,

+

∈

∈

5.05.08

Dr inż. Krzysztof Lisiecki

40

Wprowadzenie do teorii grafów

Drogę w grafie

G nazywamy zamkniętą, gdy

X

X

n

+

=

1

1

5.05.08

Dr inż. Krzysztof Lisiecki

41

Wprowadzenie do teorii grafów

Drogę w grafie nazywamy elementarną, gdy wszystkie jej
wierzchołki są różne.

Drogę w grafie nazywamy prostą, jeżeli wszystkie jej
krawędzie (łuki) są różne.

Drogę prostą zamkniętą nazywamy cyklem (obwodem).

Cykl nazywamy elementarnym, jeżeli jest drogą
elementarną (wszystkie wierzchołki są różne).

5.05.08

Dr inż. Krzysztof Lisiecki

42

Wprowadzenie do teorii grafów

Graf, który nie zawiera cykli nazywamy grafem
acyklicznym.

 Drogą acykliczna nazywamy drogę, dla której
graf składający się z wierzchołków i łuków
tworzących drogę jest acykliczny.

5.05.08

Dr inż. Krzysztof Lisiecki

43

Wprowadzenie do teorii grafów

Twierdzenie

Jeżeli droga zamknięta

{

}

X g X

X g X

n

n

1

1

2

1

, ,

,...,

,

,

jest długości co najmniej 3 i wierzchołki

X

X

n

1

,...,

są różne, to jest cyklem.

5.05.08

Dr inż. Krzysztof Lisiecki

44

Wprowadzenie do teorii grafów

Mówimy, że droga ma długość n jeśli jest postaci

oraz przyporządkowanie łukowi pary wierzchołków

jest funkcją.

{

}

X g X

X g X

n

n

n

1

1

2

1

, ,

,...,

,

,

+

(

,

)

X X

i

i

+

1

Dopuszczamy sytuacje, w których łuk łączy
wierzchołek ze sobą. Taką drogę nazywamy pętlą.

5.05.08

Dr inż. Krzysztof Lisiecki

45

Wprowadzenie do teorii grafów

Odległością między dwoma wierzchołkami w
grafie nazywamy długość najkrótszej drogi
łączącej te wierzchołki.

Średnicą grafu nazywamy maksimum spośród
wszystkich odległości między wierzchołkami
grafu.

5.05.08

Dr inż. Krzysztof Lisiecki

46

Wprowadzenie do teorii grafów

Poniżej widzimy graf o średnicy 4

5.05.08

Dr inż. Krzysztof Lisiecki

47

Wprowadzenie do teorii grafów

Grafem z wagami (grafem ważonym) nazywamy
graf, w którym każdej krawędzi (łukowi)
przypisana jest pewna liczba nieujemna zwana
wagą danej krawędzi. Innymi słowy, na zbiorze
krawędzi (łuków) każdego grafu możemy określić
pewną funkcję, która danej krawędzi (łukowi)
łączącej wierzchołek X

i

z wierzchołkiem X

k

przypisuje pewna liczbę w(i,k).

5.05.08

Dr inż. Krzysztof Lisiecki

48

Wprowadzenie do teorii grafów

Gdy nie istnieje krawędź (łuk) łącząca
wierzchołek z wierzchołkiem X

i

z wierzchołkiem

X

k

wówczas przyjmujemy w(i,k)=



, chociaż w

niektórych przypadkach wygodnie jest przyjąć
w(i,k)=0

.

5.05.08

Dr inż. Krzysztof Lisiecki

49

Wprowadzenie do teorii grafów

Wagą drogi w grafie ważonym nazywamy
sumę wag krawędzi (łuków) tworzących tę
drogę.

5.05.08

Dr inż. Krzysztof Lisiecki

50

Wprowadzenie do teorii grafów

Uwaga:

Każdy graf, w którym nie jest określona funkcja

wagowa możemy traktować jako graf z wagami
przyjmując wagę każdej krawędzi równą jeden.
Wówczas droga o najmniejszej wadze łącząca
dane dwa wierzchołki jest równa odległości tych
wierzchołków.

5.05.08

Dr inż. Krzysztof Lisiecki

51

Wprowadzenie do teorii grafów

Wagą grafu nazywamy sumę wag
wszystkich jego krawędzi

5.05.08

Dr inż. Krzysztof Lisiecki

52

Wprowadzenie do teorii grafów

Waga poniższego grafu wynosi 28.

5.05.08

Dr inż. Krzysztof Lisiecki

53

Wprowadzenie do teorii grafów

Graf nazywamy spójnym, jeżeli dla każdej
pary jego wierzchołków istnieje droga
łącząca te wierzchołki.

5.05.08

Dr inż. Krzysztof Lisiecki

54

Wprowadzenie do teorii grafów

Składową spójną grafu nazywamy każdy
jego spójny podgraf, który nie jest
jednocześnie podgrafem innego grafu
spójnego.

Składową spójną jest też wierzchołek
izolowany.

5.05.08

Dr inż. Krzysztof Lisiecki

55

Wprowadzenie do teorii grafów

Graf o trzech spójnych składowych

5.05.08

Dr inż. Krzysztof Lisiecki

56

Wprowadzenie do teorii grafów

Krawędź grafu, której usunięcie zwiększa
liczbą jego spójnych składowych
nazywamy mostem.

most

most

5.05.08

Dr inż. Krzysztof Lisiecki

57

Wprowadzenie do teorii grafów

Twierdzenie

Jeżeli

G jest grafem prostym wymiaru n, posiada m

krawędzi oraz k spójnych składowych, to
spełniona jest nierówność

(

)(

)

2

1

+

−

−

≤

≤

−

k

n

k

n

m

k

n

5.05.08

Dr inż. Krzysztof Lisiecki

58

Wprowadzenie do teorii grafów

Dla n=8 oraz k=3 mamy

15

5

≤

≤

m

Rys.1

Rys.2

5.05.08

Dr inż. Krzysztof Lisiecki

59

Wprowadzenie do teorii grafów

Wniosek

Jeżeli graf prosty wymiaru ma więcej niż

krawędzi, to jest spójny.

(

)(

)

2

2

1

−

−

n

n

5.05.08

Dr inż. Krzysztof Lisiecki

60

Wprowadzenie do teorii grafów

Wniosek

Jeśli graf prosty jest spójny wymiaru n

posiada m krawędzi, to

(

)

2

1

1

−

⋅

≤

≤

−

n

n

m

n

5.05.08

Dr inż. Krzysztof Lisiecki

61

Wprowadzenie do teorii grafów

Przykład

Dla n=4 mamy

6

3

≤

≤

m

5.05.08

Dr inż. Krzysztof Lisiecki

62

Wprowadzenie do teorii grafów

Dwa grafy

(

)

1

1

1

G

X ,

=

G

oraz

(

)

2

2

2

G

X ,

=

G

nazywamy izomorficznymi, gdy istnieje wzajemnie
jednoznaczne odwzorowanie (bijekcja) zbiorów ich
wierzchołków takie, że liczba krawędzi łączących dane
dwa wierzchołki pierwszego grafu jest równa liczbie
krawędzi łączących odpowiadające im wierzchołki
grafu drugiego.

5.05.08

Dr inż. Krzysztof Lisiecki

63

Wprowadzenie do teorii grafów

Wprost z definicji izomorfizmu grafów wynika, że

grafy izomorficzne mają:



ten sam wymiar (liczbę wierzchołków),



tę samą liczbę krawędzi,



tę samą liczbę pętli,



tę sama liczbę wierzchołków o danym stopniu.

5.05.08

Dr inż. Krzysztof Lisiecki

64

Wprowadzenie do teorii grafów

Przykład

Rys. a

Rys. b

5.05.08

Dr inż. Krzysztof Lisiecki

65

Grafy z rysunków są izomorficzne, a odpowiednie

odwzorowanie zbioru wierzchołków grafu z
rysunku a) na zbiór wierzchołków grafu z rysunku
b) przedstawia poniższa tabelka:

Wierzchołek z

grafu z rys. a)

1

2

3

4

5

Wierzchołek z

grafu z rys. b)

D

A

C

E

B

5.05.08

Dr inż. Krzysztof Lisiecki

66

Wprowadzenie do teorii grafów

UWAGA:

Spełnienie powyższych czterech warunków
dla dwóch grafów nie upoważnia nas
jeszcze do stwierdzenia, że są one
izomorficzne!

5.05.08

Dr inż. Krzysztof Lisiecki

67

Wprowadzenie do teorii grafów

Przykład

Grafy nieizomorficzne spełniające warunki 1-4

5.05.08

Dr inż. Krzysztof Lisiecki

68

Wprowadzenie do teorii grafów

Grafem planarnym nazywamy graf, który możemy

narysować na płaszczyźnie tak, aby jego
krawędzie nie przecinały się.

Uwaga:

Fakt, że rysunek grafu zawiera przecinające się

krawędzie nie oznacza, że graf nie jest planarny.

5.05.08

Dr inż. Krzysztof Lisiecki

69

Wprowadzenie do teorii grafów

Przykładem jest graf (rys. a), który można

narysować w ten sposób, by jego krawędzie nie
przecinały się (rys. b). Jest to zatem graf planarny.

Rys. a

Rys. b

5.05.08

Dr inż. Krzysztof Lisiecki

70

Wprowadzenie do teorii grafów

Twierdzenie

Każdy prosty graf planarny można narysować za

pomocą odcinków.

5.05.08

Dr inż. Krzysztof Lisiecki

71

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

72

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

73

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

74

Wprowadzenie do teorii grafów

Grafy platońskie, to grafy utworzone z wierzchołków

i krawędzi pięciu wielościanów foremnych

5.05.08

Dr inż. Krzysztof Lisiecki

75

Wprowadzenie do teorii grafów

Grafy platońskie – czworościan foremny (tetraedr)

5.05.08

Dr inż. Krzysztof Lisiecki

76

Wprowadzenie do teorii grafów

Grafy platońskie – sześcian (heksaedr)

5.05.08

Dr inż. Krzysztof Lisiecki

77

Wprowadzenie do teorii grafów

Grafy platońskie – ośmiościan foremny (oktaedr)

5.05.08

Dr inż. Krzysztof Lisiecki

78

Wprowadzenie do teorii grafów

Grafy platońskie – dwunastościan foremny (dodekaedr)

5.05.08

Dr inż. Krzysztof Lisiecki

79

Wprowadzenie do teorii grafów

Grafy platońskie – dwudziestościan foremny (ikosaedr)

5.05.08

Dr inż. Krzysztof Lisiecki

80

Wprowadzenie do teorii grafów

Miarą „nieplanarności” grafu jest liczba przecięć.

Liczbą przecięć grafu

G nazywamy najmniejszą

liczbę przecięć, które muszą wystąpić, aby dany
graf narysować na płaszczyźnie. Liczbę przecięć
grafu

G oznaczamy cr(G).

Dla dowolnego grafu planarnego liczba przecięć jest

równa zero.

5.05.08

Dr inż. Krzysztof Lisiecki

81

Wprowadzenie do teorii grafów

cr (

G). =1

5.05.08

Dr inż. Krzysztof Lisiecki

82

Wprowadzenie do teorii grafów

Rysunek grafu planarnego dzieli płaszczyznę na

obszary (ściany), z których jeden jest
nieograniczony (rys. poniżej).

5.05.08

Dr inż. Krzysztof Lisiecki

83

Wprowadzenie do teorii grafów

Twierdzenie Eulera (1750)

Jeżeli G jest grafem planarnym spójnym wymiaru n,

posiadającym m krawędzi oraz f ścian, to

2

=

+

−

f

m

n

5.05.08

Dr inż. Krzysztof Lisiecki

84

Wprowadzenie do teorii grafów

Przykład

n=8, m=11, f=5 n-m+f=8-11+5=2

5.05.08

Dr inż. Krzysztof Lisiecki

85

Wprowadzenie do teorii grafów

Wniosek z tw. Eulera

Jeżeli G jest grafem planarnym wymiaru n,

posiadającym k spójnych składowych,
m krawędzi oraz f ścian, to

1

+

=

+

−

k

f

m

n

5.05.08

Dr inż. Krzysztof Lisiecki

86

Wprowadzenie do teorii grafów

Przykład

n=9, k=2

m=10, f=4

9-10+4=2+1

5.05.08

Dr inż. Krzysztof Lisiecki

87

Wprowadzenie do teorii grafów

Dla danego grafu możemy stworzyć jego opis

macierzowy budując:



macierz sąsiedztwa,



macierz incydencji, lub



macierz cykli (obwodów)

5.05.08

Dr inż. Krzysztof Lisiecki

88

Wprowadzenie do teorii grafów

Niech

G=(X,G)

będzie

dowolnym

grafem

nieskierowanym wymiaru n. Macierzą sąsiedztwa
grafu

G nazywamy macierz kwadratową,

do wierzchołka

n

j

i

ij

a

≤

=

,

]

[

A

której elementy określamy następująco

:

a

ij

jest liczbą krawędzi od wierzchołka

X

j

5.05.08

Dr inż. Krzysztof Lisiecki

89

Wprowadzenie do teorii grafów

Widzimy więc, że elementy macierzy są liczbami

dodatnimi lub zerami, przy czym element

a

ij

=

0

wtedy i tylko wtedy, gdy nie istnieje krawędź od
wierzchołka

X

i

do wierzchołka

X

j

Macierz sąsiedztwa grafu nieskierowanego niesie
wiele informacji na temat grafu.

5.05.08

Dr inż. Krzysztof Lisiecki

90

Wprowadzenie do teorii grafów



wymiar macierzy nn mówi, że graf ma wymiar
n (liczba wierzchołków),



ilość jedynek na głównej przekątnej jest równa
ilości pętli,



Jeśli graf nie ma pętli, to suma wszystkich
elementów macierzy jest równa podwojonej
liczbie krawędzi w grafie,

5.05.08

Dr inż. Krzysztof Lisiecki

91

Wprowadzenie do teorii grafów

macierz sąsiedztwa grafu
nieskierowanego jest macierzą
symetryczną,

Jeżeli graf nie ma pętli, to suma
elementów i-tego wiersza (i-tej kolumny)
jest równa stopniowi wierzchołka

5.05.08

Dr inż. Krzysztof Lisiecki

92

Wprowadzenie do teorii grafów

Niech

G=(X,G)

będzie

dowolnym

grafem

skierowanym wymiaru n. Macierzą sąsiedztwa
grafu

G nazywamy macierz kwadratową,

do wierzchołka

n

j

i

ij

a

≤

=

,

]

[

A

której elementy określamy następująco:

a

ij

jest liczbą łuków od wierzchołka

X

j

X

i

5.05.08

Dr inż. Krzysztof Lisiecki

93

Wprowadzenie do teorii grafów

Macierz sąsiedztwa grafu skierowanego niesie takie

informacje na temat grafu skierowanego jak
macierz grafu nieskierowanego. Wystarczy we
własnościach 1 –5 zamienić słowo krawędź na
słowo łuk.

5.05.08

Dr inż. Krzysztof Lisiecki

94

Wprowadzenie do teorii grafów

Przykład

Graf nieskierowany i jego macierz sąsiedztwa





















1

0

1

0

1

1

1

1

0

5.05.08

Dr inż. Krzysztof Lisiecki

95

Wprowadzenie do teorii grafów

Przykład

Graf skierowany i jego macierz sąsiedztwa





















0

0

1

2

1

0

1

0

0

5.05.08

Dr inż. Krzysztof Lisiecki

96

Wprowadzenie do teorii grafów

Macierzą incydencji grafu wymiaru n bez pętli

posiadającego m krawędzi nazywamy macierz A
wymiaru nm, której elementy określone są
wzorem









−

−

=

razie

przeciwnym

w

iem

wierzcholk

tym

i

z

incydentna

jest

krawędź

ta

jeśli

,

0

1

j

a

ij

5.05.08

Dr inż. Krzysztof Lisiecki

97

Wprowadzenie do teorii grafów

Przykład

Graf i jego macierz incydencji

 

a b c d e f g

1

1 0 0 0 0 0 0

2

1 1 1 0 0 0 0

3

0 1 0 1 1 0 0

4

0 0 1 1 0 1 1

5

0 0 0 0 1 1 1

5.05.08

Dr inż. Krzysztof Lisiecki

98

Wprowadzenie do teorii grafów

Własności macierzy incydencji



Każda kolumna macierzy zawiera
dokładnie dwie jedynki,



Liczba jedynek w każdym wierszu jest
równa stopniowi odpowiadającego mu
wierzchołka,

5.05.08

Dr inż. Krzysztof Lisiecki

99

Wprowadzenie do teorii grafów

Własności macierzy incydencji c.d.

2.

Wiersz złożony z samych zer reprezentuje
wierzchołek izolowany,

3.

Krawędzie równoległe tworzą w macierzy
identyczne kolumny,

5.05.08

Dr inż. Krzysztof Lisiecki

100

Wprowadzenie do teorii grafów

Własności macierzy incydencji c.d.

2.

Jeśli graf ma dwie spójne składowe, to jego
macierz incydencji jest macierzą blokową postaci













2

1

A

0

0

A

gdzie macierze w lewym górnym i
prawym dolnym rogu są,
odpowiednio, macierzami incydencji
każdej składowej spójnej grafu

5.05.08

Dr inż. Krzysztof Lisiecki

101

Wprowadzenie do teorii grafów

Uwaga:

Jeśli składowych spójnych jest k, to macierz

incydencji można zapisać w postaci blokowej

























k

A

0

0

0

0

0

0

0

0

A

0

0

0

0

A

2

1



5.05.08

Dr inż. Krzysztof Lisiecki

102

Wprowadzenie do teorii grafów

Własności macierzy incydencji c.d.

2.

Permutacja dwóch wierszy lub kolumn w
macierzy incydencji odpowiada
przeetykietowaniu wierzchołków i krawędzi
tego samego grafu.

5.05.08

Dr inż. Krzysztof Lisiecki

103

Wprowadzenie do teorii grafów

Wniosek:

Dwa grafy są izomorficzne wtedy i tylko

wtedy i tylko wtedy gdy ich macierze
incydencji różnią się tylko permutacją
wierszy i kolumn.

5.05.08

Dr inż. Krzysztof Lisiecki

104

Wprowadzenie do teorii grafów

Przykład

























1

0

0

0

0

0

1

1

1

0

1

0

1

1

1

0

1

0

0

1

5.05.08

Dr inż. Krzysztof Lisiecki

105

Wprowadzenie do teorii grafów

Twierdzenie

Rząd macierzy incydencji grafu spójnego

wymiaru n jest równy n-1.

5.05.08

Dr inż. Krzysztof Lisiecki

106

Wprowadzenie do teorii grafów

Twierdzenie o rzędzie macierzy grafu

spójnego mówi, że jeden z wierszy jego
macierzy incydencji jest liniowo zależny od
pozostałych. Sugeruje to, że wszystkie
informacje o grafie wymiaru n zawarte są w
n-1 wierszach macierzy incydencji.

5.05.08

Dr inż. Krzysztof Lisiecki

107

Wprowadzenie do teorii grafów

Zredukowaną macierzą incydencji grafu

nazywamy macierz otrzymaną z macierzy
incydencji przez usunięcie dowolnego
wiersza. Macierz ta ma wymiary (n-1)m

5.05.08

Dr inż. Krzysztof Lisiecki

108

Wprowadzenie do teorii grafów

Wprost z definicji wynika

Twierdzenie

Macierz incydencji grafu spójnego wymiaru n

posiadającego n-1 krawędzi jest nieosobliwą
macierzą kwadratową wymiaru n-1

5.05.08

Dr inż. Krzysztof Lisiecki

109

Wprowadzenie do teorii grafów

Macierzą cykli (obwodów) grafu

posiadającego m krawędzi nazywamy
macierz A wymiaru nm, której elementy
określone są wzorem









−

−

=

razie

przeciwnym

w

krawędź

tą

j

zawiera

ty

jeśli

,

0

1

cykl

i

a

ij

5.05.08

Dr inż. Krzysztof Lisiecki

110

Wprowadzenie do teorii grafów

Przykład

Graf i jego cykle

5.05.08

Dr inż. Krzysztof Lisiecki

111

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

112

Wprowadzenie do teorii grafów

























1

0

0

0

0

0

0

1

0

1

0

1

0

1

0

0

1

1

0

0

0

1

1

0

Macierz cykli grafu

5.05.08

Dr inż. Krzysztof Lisiecki

113

Wprowadzenie do teorii grafów

Własności macierzy cykli



Kolumna zer odpowiada krawędzi nie
należącej do żadnego cyklu,



Każdy wiersz zawiera te i tylko te
krawędzie, które tworzą odpowiadający
mu cykl

5.05.08

Dr inż. Krzysztof Lisiecki

114

Wprowadzenie do teorii grafów

Własności macierzy cykli c.d.

2.

Wiersz odpowiadający pętli zawiera tylko
pojedynczą jedynkę,

3.

Liczba jedynek w wierszu jest równa
liczbie krawędzi w odpowiadającym mu
cyklu,

5.05.08

Dr inż. Krzysztof Lisiecki

115

Wprowadzenie do teorii grafów

Własności macierzy cykli c.d.

2.

Przestawienie dowolnych dwóch wierszy
lub kolumn w macierzy cykli odpowiada
przeetykietowaniu cykli i krawędzi,

3.

Grafy o identycznych macierzach cykli
nie muszą być izomorficzne

5.05.08

Dr inż. Krzysztof Lisiecki

116

Wprowadzenie do teorii grafów

Zastosowanie macierzy sąsiedztwa

Problemy:



Ile krawędzi łączy dwa dane wierzchołki
grafu?



Ile dróg długości n łączy dwa dane
wierzchołki grafu?

5.05.08

Dr inż. Krzysztof Lisiecki

117

Wprowadzenie do teorii grafów

Ile jest dróg łączących

wierzchołek 2 z
wierzchołkiem 4 o
długości:

b) 1,

c) 2,

d) 3.

5.05.08

Dr inż. Krzysztof Lisiecki

118

Wprowadzenie do teorii grafów

Twierdzenie

Jeżeli A jest macierzą grafu o wierzchołkach

X

1

, X

2

,…,X

n

, to element a

ij

w macierzy A

m

jest

równy liczbie dróg długości m łączących
wierzchołek X

i

z wierzchołkiem X

j

5.05.08

Dr inż. Krzysztof Lisiecki

119

Wprowadzenie do teorii grafów





















=

1

0

1

0

1

1

1

1

0

A





















=

2

1

1

1

2

1

1

1

2

2

A





















=

3

2

3

2

3

3

3

3

2

3

A

5.05.08

Dr inż. Krzysztof Lisiecki

120

Wprowadzenie do teorii grafów

Drogą Eulera w grafie nazywamy każdą drogę

prostą, która zawiera wszystkie krawędzie
grafu.

5.05.08

Dr inż. Krzysztof Lisiecki

121

Wprowadzenie do teorii grafów

Przykład drogi

Eulera

{

}

6

6

5

5

4

4

3

3

2

1

1

2

3

7

6

8

1

X

g

X

g

X

g

X

g

X

g

X

g

X

g

X

g

X

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

5.05.08

Dr inż. Krzysztof Lisiecki

122

Wprowadzenie do teorii grafów

Przykład grafu, który nie zawiera drogi Eulera

5.05.08

Dr inż. Krzysztof Lisiecki

123

Wprowadzenie do teorii grafów

Cyklem Eulera nazywamy

zamkniętą drogę Eulera.

5.05.08

Dr inż. Krzysztof Lisiecki

124

Wprowadzenie do teorii grafów

Przykład
Cyklem Eulera
jest droga

{

}

X g X g X g X g X g X g X g X

1

1

2

2

3

3

4

4

5

5

6

6

3

7

1

, ,

,

,

,

,

,

,

, ,

,

,

,

,

5.05.08

Dr inż. Krzysztof Lisiecki

125

Wprowadzenie do teorii grafów

Twierdzenie

W grafie spójnym, posiadającym co najwyżej

dwa wierzchołki stopnia nieparzystego
istnieje droga Eulera.

5.05.08

Dr inż. Krzysztof Lisiecki

126

Wprowadzenie do teorii grafów

Twierdzenie (Euler, 1736)

Jeżeli graf

G posiada cykl Eulera, to jest

spójny i każdy jego wierzchołek ma
parzysty stopień.

5.05.08

Dr inż. Krzysztof Lisiecki

127

Wprowadzenie do teorii grafów

Przykład grafu

posiadającego
cykl Eulera

5.05.08

Dr inż. Krzysztof Lisiecki

128

Wprowadzenie do teorii grafów

Prawdziwe jest również twierdzenie odwrotne.

 

Twierdzenie

Jeżeli graf

G jest spójny i stopień każdego

wierzchołka jest parzysty to posiada cykl
Eulera

5.05.08

Dr inż. Krzysztof Lisiecki

129

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

130

Wprowadzenie do teorii grafów

Algorytm wyznaczania drogi Eulera w grafie.



Wybieramy w grafie dowolny wierzchołek
nieparzystego stopnia. Jeśli taki nie istnieje
wybieramy dowolny parzystego stopnia.
Wybrany wierzchołek oznaczamy przez X.

5.05.08

Dr inż. Krzysztof Lisiecki

131

Wprowadzenie do teorii grafów

1.

Dopóki w grafie są krawędzie
incydentne z wierzchołkiem X
wykonujemy jedną z poniższych
czynności

5.05.08

Dr inż. Krzysztof Lisiecki

132

Wprowadzenie do teorii grafów

a) jeżeli z wierzchołkiem X jest incydentna

dokładnie jedna krawędź g, łącząca ten
wierzchołek z wierzchołkiem Y, to
podstawiamy X:=Y, zapisujemy g jako
kolejny wyraz ciągu oraz usuwamy tę
krawędź z grafu.

5.05.08

Dr inż. Krzysztof Lisiecki

133

Wprowadzenie do teorii grafów

b) jeżeli z wierzchołkiem X incydentna jest

więcej niż jedna krawędź, to wybieramy
dowolną, która nie jest mostem o

postępujemy dalej tak jak w punkcie a.

5.05.08

Dr inż. Krzysztof Lisiecki

134

Wprowadzenie do teorii grafów

3. a) jeśli otrzymany przez nas ciąg

zawiera wszystkie krawędzie grafu
oznacza to, że znaleźliśmy drogę
Eulera

5.05.08

Dr inż. Krzysztof Lisiecki

135

Wprowadzenie do teorii grafów

3. b) jeśli otrzymany przez nas ciąg nie

zawiera wszystkich krawędzi grafu
oznacza to, że graf nie jest spójny

5.05.08

Dr inż. Krzysztof Lisiecki

136

Wprowadzenie do teorii grafów

Przykład

{

}

3

2

2

,

,

X

g

X

5.05.08

Dr inż. Krzysztof Lisiecki

137

Wprowadzenie do teorii grafów

{

}

4

3

3

2

2

,

,

,

,

X

g

X

g

X

5.05.08

Dr inż. Krzysztof Lisiecki

138

Wprowadzenie do teorii grafów

{

}

5

4

4

3

3

2

2

,

,

,

,

,

,

X

g

X

g

X

g

X

5.05.08

Dr inż. Krzysztof Lisiecki

139

Wprowadzenie do teorii grafów

{

}

2

5

5

4

4

3

3

2

2

,

,

,

,

,

,

,

,

X

g

X

g

X

g

X

g

X

5.05.08

Dr inż. Krzysztof Lisiecki

140

Wprowadzenie do teorii grafów

{

}

1

1

2

5

5

4

4

3

3

2

2

,

,

,

,

,

,

,

,

,

,

X

g

X

g

X

g

X

g

X

g

X

5.05.08

Dr inż. Krzysztof Lisiecki

141

Wprowadzenie do teorii grafów

{

}

6

9

1

1

2

5

5

4

4

3

3

2

2

,

,

,

,

,

,

,

,

,

,

,

,

X

g

X

g

X

g

X

g

X

g

X

g

X

5.05.08

Dr inż. Krzysztof Lisiecki

142

Wprowadzenie do teorii grafów

{

}

4

8

6

9

1

1

2

5

5

4

4

3

3

2

2

,

,

,

,

,

,

,

,

,

,

,

,

,

,

X

g

X

g

X

g

X

g

X

g

X

g

X

g

X

5.05.08

Dr inż. Krzysztof Lisiecki

143

Wprowadzenie do teorii grafów

{

}

6

7

4

8

6

9

1

1

2

5

5

4

4

3

3

2

2

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

X

g

X

g

X

g

X

g

X

g

X

g

X

g

X

g

X

5.05.08

Dr inż. Krzysztof Lisiecki

144

Wprowadzenie do teorii grafów

{

}

5

6

6

7

4

8

6

9

1

1

2

5

5

4

4

3

3

2

2

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

X

g

X

g

X

g

X

g

X

g

X

g

X

g

X

g

X

g

X

5.05.08

Dr inż. Krzysztof Lisiecki

145

Wprowadzenie do teorii grafów

Animacja 1

Animacja 2

5.05.08

Dr inż. Krzysztof Lisiecki

146

Wprowadzenie do teorii grafów

Definicja

Stopniem wejściowym wierzchołka w
grafie zorientowanym nazywamy ilość
łuków wchodzących do wierzchołka.
Stopień wejściowy wierzchołka X

i

oznaczamy indegX

i

.

5.05.08

Dr inż. Krzysztof Lisiecki

147

Wprowadzenie do teorii grafów

Definicja

Stopniem wyjściowym wierzchołka w
grafie zorientowanym nazywamy ilość
łuków wychodzących z wierzchołka.
Stopień wejściowy wierzchołka X

i

oznaczamy outdegX

i

.

5.05.08

Dr inż. Krzysztof Lisiecki

148

Wprowadzenie do teorii grafów

Wniosek

Dla dowolnego wierzchołka X

i

w grafie

zorientowanym zachodzi równość

in

X

out

X

X

i

i

i

deg

deg

deg

+

=

5.05.08

Dr inż. Krzysztof Lisiecki

149

Wprowadzenie do teorii grafów

Twierdzenie

Załóżmy, że graf skierowany traktowany jako
nieskierowany jest spójny. Wówczas istnieje
w nim cykl Eulera wtedy i tylko wtedy, gdy
stopień wejściowy każdego wierzchołka jest
równy jego stopniowi wyjściowemu.

5.05.08

Dr inż. Krzysztof Lisiecki

150

Wprowadzenie do teorii grafów

Graf, który nie posiada cyklu Eulera

5.05.08

Dr inż. Krzysztof Lisiecki

151

Wprowadzenie do teorii grafów

Graf, który posiada cykl Eulera

5.05.08

Dr inż. Krzysztof Lisiecki

152

Wprowadzenie do teorii grafów

Wcześniej podana była zależność między ilością

krawędzi w grafie niezorientowanym a sumą
stopni

wierzchołków.

Teraz

przytoczymy

udowodnione przez Istvana Reimana twierdzenie
pozwalające oszacować z góry ilość krawędzi w
grafie wymiaru n nie zawierającym cykli o
długości 4.

5.05.08

Dr inż. Krzysztof Lisiecki

153

Wprowadzenie do teorii grafów

 Twierdzenie.

Jeżeli graf

G=(X,G) wymiaru n nie zawiera

cykli długości 4, to ilość krawędzi m spełnia
nierówność













−

+

⋅

≤

)

3

4

1

(

4

n

n

m

5.05.08

Dr inż. Krzysztof Lisiecki

154

Wprowadzenie do teorii grafów

Przykład.

Jeśli graf ma wymiar 6 i nie zawiera cykli o

długości 4, to

37

,

8

)

21

1

(

2

3

)

3

6

4

1

(

4

6

≈

+

⋅

=













−

⋅

+

⋅

≤

m

5.05.08

Dr inż. Krzysztof Lisiecki

155

Wprowadzenie do teorii grafów

Definicja.

Drzewem nazywamy graf spójny bez cykli.

5.05.08

Dr inż. Krzysztof Lisiecki

156

Wprowadzenie do teorii grafów

Definicja.

Lasem nazywamy graf bez cykli

5.05.08

Dr inż. Krzysztof Lisiecki

157

Wprowadzenie do teorii grafów

Twierdzenie

Niech

G będzie grafem wymiaru n. Wówczas

następujące stwierdzenia są równoważne:

3. G jest drzewem

4. G nie zawiera cykli i ma n-1 krawędzi

5. G jest spójny i ma n-1 krawędzi

5.05.08

Dr inż. Krzysztof Lisiecki

158

Wprowadzenie do teorii grafów

• G jest spójny i każda krawędź jest mostem

• dowolne dwa wierzchołki grafu G są

połączone dokładnie jedną droga

• graf G nie zawiera cykli a dołączenie

dowolnej nowej krawędzi do

G tworzy

dokładnie jeden cykl

• G jest grafem acyklicznym mającym n-1

krawędzi

5.05.08

Dr inż. Krzysztof Lisiecki

159

Wprowadzenie do teorii grafów

Wniosek

W drzewie o co najmniej dwóch
wierzchołkach, co najmniej dwa z nich są
stopnia 1.

5.05.08

Dr inż. Krzysztof Lisiecki

160

Wprowadzenie do teorii grafów

Definicja

Drzewem ukorzenionym nazywamy
drzewo z wyróżnionym wierzchołkiem

5.05.08

Dr inż. Krzysztof Lisiecki

161

Wprowadzenie do teorii grafów

Przykład

5.05.08

Dr inż. Krzysztof Lisiecki

162

Wprowadzenie do teorii grafów

Definicja.

Dla grafu spójnego

G=(X,G) każde drzewo

G

T

=(X,T) takie, że

nazywamy drzewem spinającym grafu

G.

G

T

⊆

5.05.08

Dr inż. Krzysztof Lisiecki

163

Wprowadzenie do teorii grafów

Twierdzenie.

Każdy graf skończony spójny ma drzewo
spinające.

5.05.08

Dr inż. Krzysztof Lisiecki

164

Wprowadzenie do teorii grafów

Twierdzenie.

Każdy graf skończony ma las spinający.

5.05.08

Dr inż. Krzysztof Lisiecki

165

Wprowadzenie do teorii grafów

Twierdzenie (Cayley, 1889)

Graf pełny K

n

(dla ) ma n

n-2

różnych drzew spinających.

2

≥

n

5.05.08

Dr inż. Krzysztof Lisiecki

166

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

167

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

168

Wprowadzenie do teorii grafów

Definicja

Wagą drzewa (jako grafu z wagami)
nazywamy sumę wag jego krawędzi
(łuków).

5.05.08

Dr inż. Krzysztof Lisiecki

169

Wprowadzenie do teorii grafów

Przykład

Waga drzewa przedstawionego na rysunku
poniżej wynosi 21.

5.05.08

Dr inż. Krzysztof Lisiecki

170

Wprowadzenie do teorii grafów

Listy sąsiedztwa, to tablica złożona z list,
których liczba jest równa wymiarowi grafu
(liczbie jego wierzchołków).

Dla każdego wierzchołka odpowiadająca mu
lista składa się z tych, i tylko tych,
wierzchołków grafu, które z nim sąsiadują.

5.05.08

Dr inż. Krzysztof Lisiecki

171

Wprowadzenie do teorii grafów

Listy sąsiedztwa najlepiej nadają się do
reprezentowania

grafów

rzadkich,

natomiast dla reprezentacji grafów gęstych
zdecydowanie lepiej wybrać macierz.

5.05.08

Dr inż. Krzysztof Lisiecki

172

Wprowadzenie do teorii grafów

Twierdzenie

Suma długości wszystkich list sąsiedztwa
grafu (nieskierowanego) jest równa
podwojonej liczbie krawędzi tego grafu.

Suma długości wszystkich list sąsiedztwa
digrafu (grafu skierowanego) jest równa
liczbie łuków tego grafu.

5.05.08

Dr inż. Krzysztof Lisiecki

173

Wprowadzenie do teorii grafów

Przykład

5.05.08

Dr inż. Krzysztof Lisiecki

174

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

175

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

176

Wprowadzenie do teorii grafów

Najważniejszymi i najbardziej znanymi
algorytmami grafowymi są:

•przeszukiwanie wszerz oraz 

•przeszukiwanie w głąb.

5.05.08

Dr inż. Krzysztof Lisiecki

177

Wprowadzenie do teorii grafów

W

trakcie

działania

algorytmu

przeszukiwania możemy wyróżnić w
zbiorze wierzchołków grafu dwa
rozłączne podzbiory: wierzchołków już
odwiedzonych i wierzchołków jeszcze
nie odwiedzonych.

5.05.08

Dr inż. Krzysztof Lisiecki

178

Wprowadzenie do teorii grafów

W przypadku drzewa ukorzenionego,
narysowanego tak, że korzeń jest na
górze granica pomiędzy tymi zbiorami
przebiega poziomo dla przeszukiwania
wszerz,

natomiast

pionowo

dla

przeszukiwania w głąb .

5.05.08

Dr inż. Krzysztof Lisiecki

179

Wprowadzenie do teorii grafów

Przeszukiwanie wszerz

5.05.08

Dr inż. Krzysztof Lisiecki

180

Wprowadzenie do teorii grafów

Przeszukiwanie w głąb

5.05.08

Dr inż. Krzysztof Lisiecki

181

Wprowadzenie do teorii grafów

Algorytm przeszukiwania wszerz polega na
kolejnym odwiedzaniu najpierw
wierzchołków, których odległość od korzenia
wynosi 1, następnie 2, potem 3 itd.

Zatem zanim zagłębimy się bardziej w grafie
sprawdzamy wcześniej wszystkie możliwe
wierzchołki „na danym poziomie”.

5.05.08

Dr inż. Krzysztof Lisiecki

182

Wprowadzenie do teorii grafów

Idea algorytmu przeszukiwania w głąb polega
na odwiedzeniu jak największej liczby
wierzchołków przesuwając się możliwie
najdalej w głąb grafu, a dopiero później
przejściu do pozostałych wierzchołków.

5.05.08

Dr inż. Krzysztof Lisiecki

183

Wprowadzenie do teorii grafów

W trakcie przeszukiwania grafów za pomocą
obu algorytmów budowane jest znakowane
drzewo przeszukiwań. Rozpoczynając od
korzenia nadajemy każdemu wierzchołkowi
etykietę ze zbioru liniowo uporządkowanego,
najczęściej ze zbioru

{

}

n

...,

,

,

, 3

2

1

5.05.08

Dr inż. Krzysztof Lisiecki

184

Wprowadzenie do teorii grafów

Algorytm przeszukiwania grafu wszerz

Zakładamy, że przeszukiwany graf jest
reprezentowany przez listy sąsiedztwa.
Przeszukiwanie zaczynamy od wierzchołków
znajdujących się na liście sąsiedztwa korzenia
– przeszukujemy je kolejno dołączając do
drzewa przeszukiwań kolejne wierzchołki z
listy i łączące je z korzeniem krawędzie.

5.05.08

Dr inż. Krzysztof Lisiecki

185

Wprowadzenie do teorii grafów

Następnie przechodzimy do listy sąsiedztwa
wierzchołka, który był pierwszy na liście
sąsiedztwa korzenia i kolejno przeszukujemy
znajdujące się tam wierzchołki dołączając
jednocześnie te wierzchołki do drzewa
przeszukiwań. Analogicznie postępujemy
z listami sąsiedztwa kolejnych wierzchołków
znajdujących się na liście sąsiedztwa korzenia.

5.05.08

Dr inż. Krzysztof Lisiecki

186

Wprowadzenie do teorii grafów

Po wyczerpaniu się wierzchołków na liście
sąsiedztwa korzenia przechodzimy do
przeszukiwania wierzchołków znajdujących
się na listach sąsiedztwa wierzchołków, które
znalazły się na listach sąsiedztwa
wierzchołków z listy sąsiedztwa korzenia,
itd.

5.05.08

Dr inż. Krzysztof Lisiecki

187

Wprowadzenie do teorii grafów

Przykład

Stosując algorytm
przeszukiwania wszerz
zbudować drzewo
przeszukiwań
poniższego grafu
przyjmując, że
korzeniem jest
wierzchołek b.

5.05.08

Dr inż. Krzysztof Lisiecki

188

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

189

Wprowadzenie do teorii grafów

{b}

5.05.08

Dr inż. Krzysztof Lisiecki

190

Wprowadzenie do teorii grafów

{b,a}

5.05.08

Dr inż. Krzysztof Lisiecki

191

Wprowadzenie do teorii grafów

{b,a,e}

5.05.08

Dr inż. Krzysztof Lisiecki

192

Wprowadzenie do teorii grafów

{b,a,e,f}

5.05.08

Dr inż. Krzysztof Lisiecki

193

Wprowadzenie do teorii grafów

{b,a,e,f,c}

5.05.08

Dr inż. Krzysztof Lisiecki

194

Wprowadzenie do teorii grafów

{b,a,e,f,c,d}

5.05.08

Dr inż. Krzysztof Lisiecki

195

Wprowadzenie do teorii grafów

{b,a,e,f,c,d,g}

5.05.08

Dr inż. Krzysztof Lisiecki

196

Wprowadzenie do teorii grafów

{b,a,e,f,c,d,g,h}

Listy puste - stop

5.05.08

Dr inż. Krzysztof Lisiecki

197

Wprowadzenie do teorii grafów

Algorytm przeszukiwania grafów w głąb

Podobnie jak w przypadku algorytmu
przeszukiwania wszerz, do przeszukiwania w
głąb wygodnie jest reprezentować graf za
pomocą list sąsiedztwa.

5.05.08

Dr inż. Krzysztof Lisiecki

198

Wprowadzenie do teorii grafów

Przeszukiwanie zaczynamy od korzenia, ale
w przeciwieństwie do przeszukiwania wszerz,
nie przeszukujemy kolejno wszystkich
wierzchołków z listy sąsiedztwa korzenia, ale
najpierw jeden z nich (pierwszy) a następnie
pierwszy wierzchołek na liście sąsiedztwa
tego wierzchołka.

5.05.08

Dr inż. Krzysztof Lisiecki

199

Wprowadzenie do teorii grafów

Postępujemy tak do momentu, w którym nie
możemy już wejść „głębiej” a dalsze
przeszukiwanie wymaga cofnięcia się do
poprzednio odwiedzonego wierzchołka
i przeszukiwanie kolejnego wierzchołka na
liście sąsiedztwa.

5.05.08

Dr inż. Krzysztof Lisiecki

200

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

201

Wprowadzenie do teorii grafów

{b}

5.05.08

Dr inż. Krzysztof Lisiecki

202

Wprowadzenie do teorii grafów

{b,a}

5.05.08

Dr inż. Krzysztof Lisiecki

203

Wprowadzenie do teorii grafów

{b,a,c}

5.05.08

Dr inż. Krzysztof Lisiecki

204

Wprowadzenie do teorii grafów

{b,a,c,g}

5.05.08

Dr inż. Krzysztof Lisiecki

205

Wprowadzenie do teorii grafów

{b,a,c,g,h}

5.05.08

Dr inż. Krzysztof Lisiecki

206

Wprowadzenie do teorii grafów

{b,a,c,g,h,d}

5.05.08

Dr inż. Krzysztof Lisiecki

207

Wprowadzenie do teorii grafów

{b,a,c,g,h,d,e}

5.05.08

Dr inż. Krzysztof Lisiecki

208

Wprowadzenie do teorii grafów

{b,a,c,g,h,d,e,f}

Listy puste - stop

5.05.08

Dr inż. Krzysztof Lisiecki

209

Wprowadzenie do teorii grafów

Najkrótsze drogi w grafie

Wagę drogi nazywamy czasem długością tej drogi.
Jednak nie zawsze waga musi oznaczać długość.
Często waga krawędzi w grafie oznacza czas
potrzebny na pokonanie jakiegoś odcinka drogi,
czas wykonania jakiejś czynności, koszt wykonania
tej czynności. Stąd waga drogi oznaczać może
łączny czas potrzebny na przebycie tej drogi,
łączny czas wykonania jakiejś czynności lub też
całkowity koszt.

5.05.08

Dr inż. Krzysztof Lisiecki

210

Wprowadzenie do teorii grafów

Problem:

Znaleźć najkrótszą drogę w grafie
ważonym, czyli drogę o najmniejszej
wadze łączącej dane dwa wierzchołki.

5.05.08

Dr inż. Krzysztof Lisiecki

211

Wprowadzenie do teorii grafów

Algorytm Dijkstry

Polega na ustaleniu wierzchołka początkowego,
przeglądaniu

pozostałych

wierzchołków

i wybraniu wierzchołka, dla którego waga drogi
od wierzchołka początkowego jest najmniejsza.
Jednocześnie uaktualniane są najmniejsze wagi
dróg od wierzchołka początkowego do innych
wierzchołków.

5.05.08

Dr inż. Krzysztof Lisiecki

212

Wprowadzenie do teorii grafów

Przykład

Wyznaczyć drogę o najmniejszej wadze
(najkrótszą drogę) łączącą wierzchołki A oraz
D poniższego grafu z wagami używając
algorytmu Dijkstry.

5.05.08

Dr inż. Krzysztof Lisiecki

213

Wprowadzenie do teorii grafów

d(A)=0

5.05.08

Dr inż. Krzysztof Lisiecki

214

Wprowadzenie do teorii grafów

krok 1

d(B)=min{d(B) ; d(A)+5}= min{

∞

; 5}=5

d(F)=min{d(F) ; d(A)+3}= min{

∞

; 3}=3

5.05.08

Dr inż. Krzysztof Lisiecki

215

Wprowadzenie do teorii grafów

krok 2

d(C)=min{d(C) ; d(F)+7}= min{

∞

; 3+7}=10

d(I)=min{d(I) ; d(F)+5}= min{

∞

; 3+5}=8

d(K)=min{d(K) ; d(F)+3}= min{

∞

; 3+3}=6.

5.05.08

Dr inż. Krzysztof Lisiecki

216

Wprowadzenie do teorii grafów

krok 3

d(E)=min{d(E) ; d(B)+2}= min{

∞

; 5+2}=7.

d(G)=min{d(G) ; d(B)+6}= min{

∞

; 5+6}=11.

5.05.08

Dr inż. Krzysztof Lisiecki

217

Wprowadzenie do teorii grafów

krok 4

d(G)=min{d(G) ; d(K)+4}= min{11 ; 6+4}=10

d(J)=min{d(J) ; d(K)+5}= min{

∞

; 6+5}=11

d(L)=min{d(L) ; d(K)+2}= min{

∞

; 6+2}=8

5.05.08

Dr inż. Krzysztof Lisiecki

218

Wprowadzenie do teorii grafów

krok 5

d(I)=min{d(I) ; d(E)+1}= min{8 ; 7+1}=8

d(J)=min{d(J) ; d(E)+2}= min{11 ; 7+2}=9

5.05.08

Dr inż. Krzysztof Lisiecki

219

Wprowadzenie do teorii grafów

krok 6

5.05.08

Dr inż. Krzysztof Lisiecki

220

Wprowadzenie do teorii grafów

krok 7

d(G)=min{d(G) ; d(L)+8}= min{10 ; 8+8}=10

5.05.08

Dr inż. Krzysztof Lisiecki

221

Wprowadzenie do teorii grafów

krok 8

5.05.08

Dr inż. Krzysztof Lisiecki

222

Wprowadzenie do teorii grafów

krok 9

d(D)=min{d(D) ; d(G)+1}= min{

∞

; 10+1}=11

d(H)=min{d(H) ; d(G)+2}= min{

∞

; 10+2}=12

5.05.08

Dr inż. Krzysztof Lisiecki

223

Wprowadzenie do teorii grafów

krok 10

d(D)=min{d(D) ; d(C)+2}= min{11 ; 10+2}=11

d(H)=min{d(H) ; d(G)+2}= min{12 ; 10+5}=12

5.05.08

Dr inż. Krzysztof Lisiecki

224

Wprowadzenie do teorii grafów

krok 11

5.05.08

Dr inż. Krzysztof Lisiecki

225

Wprowadzenie do teorii grafów

krok 12

5.05.08

Dr inż. Krzysztof Lisiecki

226

Wprowadzenie do teorii grafów

W trakcie działania przedstawionego
algorytmu każdemu wierzchołkowi
przypisana została liczba oznaczająca
najmniejszą spośród wag dróg łączących
wierzchołek A z tym wierzchołkiem.

5.05.08

Dr inż. Krzysztof Lisiecki

227

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

228

Wprowadzenie do teorii grafów

Nas interesuje najkrótsza (o najmniejszej
wadze) droga łącząca wierzchołki A oraz D.
W tabeli odczytujemy d(D)=11.

Najkrótsza droga ma zatem wagę 11
i wystarczy ją teraz odczytać z naszej tabeli.

5.05.08

Dr inż. Krzysztof Lisiecki

229

Wprowadzenie do teorii grafów

Widzimy kolejno, że:

wierzchołkiem poprzedzającym wierzchołek D jest
wierzchołek G,

wierzchołkiem, który poprzedza G jest wierzchołek K,

wierzchołkiem poprzedzającym K jest wierzchołek F,

wierzchołkiem poprzedzającym F jest wierzchołek A, czyli
wierzchołek początkowy.

Ostatecznie drogą o najmniejszej wadze łączącą wierzchołki
A oraz D jest droga przebiegająca kolejno przez wierzchołki

A, F, K, G, D

5.05.08

Dr inż. Krzysztof Lisiecki

230

Wprowadzenie do teorii grafów

Najkrótsza droga łącząca wierzchołki A oraz D

5.05.08

Dr inż. Krzysztof Lisiecki

231

Wprowadzenie do teorii grafów

Algorytm Dijkstry daje nam wagi
najkrótszych dróg łączących dany
wierzchołek ze wszystkimi pozostałymi.

Wykonując ten algorytm n*(n-1)/2 razy
otrzymalibyśmy macierz (tablicę) odległości
pomiędzy każdą parą wierzchołków.

5.05.08

Dr inż. Krzysztof Lisiecki

232

Wprowadzenie do teorii grafów

Minimalne drzewa spinające

Jak zauważyliśmy wcześniej każdy graf
spójny posiada drzewo spinające.

Z twierdzenia Cayley’a wiemy też, że graf
pełny wymiaru n posiada n

n-2

drzew

spinających. Wobec tego dowolny graf prosty
wymiaru n posiada co najwyżej n

n-2

drzew

spinających.

5.05.08

Dr inż. Krzysztof Lisiecki

233

Wprowadzenie do teorii grafów

W zagadnieniach, które można przedstawić za
pomocą grafu z wagami istotne jest często
znalezienie minimalnego drzewa spinającego,
czyli drzewa o minimalnej wadze. Najbardziej
znanymi

algorytmami

służącymi

do

rozwiązania tego problemu są:

- algorytm Kruskala, oraz

- algorytm Prima

5.05.08

Dr inż. Krzysztof Lisiecki

234

Wprowadzenie do teorii grafów

Oba algorytmy są algorytmami zachłannymi,
to znaczy takimi algorytmami, które w
każdym kolejnym kroku wykonują tę
operację, która wydaje się w danym
momencie najkorzystniejsza.

Algorytmy te polegają na wybieraniu
krawędzi o najmniejszej wadze tak, aby nie
utworzyć cyklu.

5.05.08

Dr inż. Krzysztof Lisiecki

235

Wprowadzenie do teorii grafów

Algorytmy znajdowania minimalnego
drzewa spinającego nie są jednoznaczne,
gdyż minimalne drzewo spinające nie musi
być dokładnie jedno.

5.05.08

Dr inż. Krzysztof Lisiecki

236

Wprowadzenie do teorii grafów

Inaczej jest w grafach, których krawędzie
mają różne wagi. Dla takich grafów można
udowodnić następujące twierdzenie.

Twierdzenie.

W grafie spójnym ważonym, którego
krawędziom przypisano różne wagi istnieje
dokładnie

jedno

minimalne

drzewo

spinające.

5.05.08

Dr inż. Krzysztof Lisiecki

237

Wprowadzenie do teorii grafów

Algorytm Kruskala

Algorytm ten składa się z dwóch etapów.
W pierwszym dokonujemy sortowania krawędzi
według niemalejących wag, a w drugim dopiero
wyznaczamy minimalne drzewo spinające.
Zachłanność tego algorytmu polega na tym,
że w każdym kolejnym kroku dodajemy do
budowanego grafu krawędź o najmniejszej
możliwej wadze.

5.05.08

Dr inż. Krzysztof Lisiecki

238

Wprowadzenie do teorii grafów

Budowane minimalne drzewo spinające jest
najpierw lasem ponieważ na początku
działania algorytmu tworzymy las złożony z
samych

tylko

wierzchołków

grafu

wyjściowego.

Czasami taki las dopiero w końcowej fazie
działania algorytmu staje się drzewem.

5.05.08

Dr inż. Krzysztof Lisiecki

239

Wprowadzenie do teorii grafów

Teraz z posortowanego zbioru wszystkich
krawędzi wybieramy krawędź o najmniejszej
wadze. Jeśli jest ich kilka, to wybieramy
dowolną. Dołączamy tę krawędź do
budowanego drzewa.

Następnie, spośród pozostałych krawędzi
grafu wybieramy krawędź o najmniejszej
wadze i również ją dołączamy.

5.05.08

Dr inż. Krzysztof Lisiecki

240

Wprowadzenie do teorii grafów

Przy wyborze trzeciej i następnych krawędzi
poza najmniejszą wagą musimy zwracać
uwagę na fakt, czy wybrana krawędź nie
spowoduje utworzenia cyklu.

Krawędź o najmniejszej wadze, której
dołączenie do grafu nie spowoduje utworzenia
w nim cyklu nazywać będziemy krawędzią
bezpieczną.

5.05.08

Dr inż. Krzysztof Lisiecki

241

Wprowadzenie do teorii grafów

Krawędzi bezpiecznych może być w danym
momencie działania algorytmu wiele i zbiór
tych krawędzi zmienia się w trakcie działania
algorytmu.

Powyższe postępowanie kontynuujemy do
momentu, gdy w posortowanym zbiorze
krawędzi nie będzie już krawędzi bezpiecznych.

5.05.08

Dr inż. Krzysztof Lisiecki

242

Wprowadzenie do teorii grafów

Przykład

Znaleść drzewo spinające grafu spójnego
stosując algorytm Kruskala.

5.05.08

Dr inż. Krzysztof Lisiecki

243

Wprowadzenie do teorii grafów

AC AB CD CE AE DE CG EG EF FG DF BF

1

2

2

2

3

3

4

4

5

5

6

7

Na początku porządkujemy krawędzie grafu
według niemalejących wag.

5.05.08

Dr inż. Krzysztof Lisiecki

244

Wprowadzenie do teorii grafów

Oznaczmy budowane minimalne drzewo
spinające przez T.

Oczywiście na początku działania algorytmu T
jest grafem pustym – lasem złożonym z 12.
drzew.

5.05.08

Dr inż. Krzysztof Lisiecki

245

Wprowadzenie do teorii grafów

Działanie algorytmu rozpoczynamy od
dołączenia do zbioru T krawędzi o
najmniejszej wadze, czyli krawędzi AC.

Krok 1.
Zbiór T={AC}

5.05.08

Dr inż. Krzysztof Lisiecki

246

Wprowadzenie do teorii grafów

Krok 2. Zbiór T={AC, CD}

5.05.08

Dr inż. Krzysztof Lisiecki

247

Wprowadzenie do teorii grafów

Krok 3. Zbiór T={AC, CD, CE}.

5.05.08

Dr inż. Krzysztof Lisiecki

248

Wprowadzenie do teorii grafów

Krok 4. Zbiór T={AC, CD, CE, AB}.

5.05.08

Dr inż. Krzysztof Lisiecki

249

Wprowadzenie do teorii grafów

Krok 5. Zbiór T={AC, CD, CE, AB, CG}.

5.05.08

Dr inż. Krzysztof Lisiecki

250

Wprowadzenie do teorii grafów

Krok 6. Zbiór T={AC, CD, CE, AB, CG,
EF}.

5.05.08

Dr inż. Krzysztof Lisiecki

251

Wprowadzenie do teorii grafów

Algorytm Prima

W odróżnieniu od algorytmu Kruskala
algorytm Prima nie wymaga sortowania
krawędzi według wag.

Konieczne jest tylko arbitralne wybranie
wierzchołka startowego.

5.05.08

Dr inż. Krzysztof Lisiecki

252

Wprowadzenie do teorii grafów

Zwykle wybieramy wierzchołek najbardziej
„wysunięty” na lewo i dołączając kolejne
krawędzie przechodzimy na prawo przez
kolejne wierzchołki.

Wierzchołek ten jest „zaczynem”
budowanego minimalnego drzewa
spinającego.

5.05.08

Dr inż. Krzysztof Lisiecki

253

Wprowadzenie do teorii grafów

Działanie algorytmu polega na kolejnym
dołączaniu do budowanego drzewa jednej
z bezpiecznych krawędzi, to znaczy takich,
które sąsiadują z wierzchołkami aktualnego
drzewa i nie tworzą cyklu.

W odróżnieniu od algorytmu Kruskala, w
trakcie działania algorytmu Prima
konstruowane drzewo nigdy nie jest lasem.

5.05.08

Dr inż. Krzysztof Lisiecki

254

Wprowadzenie do teorii grafów

Spośród bezpiecznych krawędzi
sąsiadujących z wierzchołkami dołączonymi
już do drzewa, dołączamy do niego krawędź
o najmniejszej wadze.

Działanie algorytmu kończymy, gdy zbiór
bezpiecznych krawędzi jest pusty.

5.05.08

Dr inż. Krzysztof Lisiecki

255

Wprowadzenie do teorii grafów

Może to oznaczać, że:

1) otrzymane drzewo zawiera wszystkie wierzchołki
grafu wyjściowego i jest minimalnym drzewem
spinającym naszego grafu, lub

2) otrzymane drzewo nie zawiera wszystkich
wierzchołków grafu wyjściowego, co oznacza, że
graf nie jest spójny, a otrzymane drzewo jest
minimalnym drzewem spinającym jednej ze
składowych spójnych grafu wyjściowego.

5.05.08

Dr inż. Krzysztof Lisiecki

256

Wprowadzenie do teorii grafów

Uwaga:

Algorytm Prima można zmodyfikować tak,
aby działał również dla grafów, które nie są
spójne a jego działanie dawało w wyniku
minimalny las spinający grafu.

5.05.08

Dr inż. Krzysztof Lisiecki

257

Wprowadzenie do teorii grafów

Przykład

Znajdziemy drzewo spinające grafu spójnego
stosując algorytm Prima.

5.05.08

Dr inż. Krzysztof Lisiecki

258

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

259

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

260

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

261

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

262

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

263

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

264

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

265

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

266

Wprowadzenie do teorii grafów

Problem kolorowania map pojawił się w roku
1852, gdy niejaki Francis Guthrie próbował
pokolorować mapę przedstawiającą hrabstwa w
Anglii. Zadał on sobie pytanie:

Jaka jest najmniejsza liczba barw wystarczająca
do pokolorowania mapy przedstawiającej wiele
hrabstw tak, aby żadne dwa hrabstwa mające
wspólną granicę nie były oznaczone tą samą
barwą?

5.05.08

Dr inż. Krzysztof Lisiecki

267

Wprowadzenie do teorii grafów

Hipoteza postawiona przez Guthrie

wystarczą cztery kolory

trafiła do de Morgana (tego „od praw de
Morgana”, a następnie do Cayley’a (1878).

5.05.08

Dr inż. Krzysztof Lisiecki

268

Wprowadzenie do teorii grafów

Pierwszy pełny i poprawny dowód pojawił
się dopiero w roku 1977 (Appel i Haken),
czyli 125 lat od postawienia problemu i
sformułowania hipotezy!

5.05.08

Dr inż. Krzysztof Lisiecki

269

Wprowadzenie do teorii grafów

Przykład mapy, której nie da się
pokolorować za pomocą trzech barw

5.05.08

Dr inż. Krzysztof Lisiecki

270

Wprowadzenie do teorii grafów

Definicja

Grafem silnie spójnym nazywamy digraf
(graf skierowany), w którym dla każdej pary
wierzchołków istnieje łącząca je droga.

Wniosek

Każdy graf spójny (nieskierowany) jest
silnie spójny.

5.05.08

Dr inż. Krzysztof Lisiecki

271

Wprowadzenie do teorii grafów

Przykład grafu silnie spójnego

5.05.08

Dr inż. Krzysztof Lisiecki

272

Wprowadzenie do teorii grafów

Definicja

Silnie spójną składową digrafu nazywamy
największy silnie spójny podgraf tego digrafu.

5.05.08

Dr inż. Krzysztof Lisiecki

273

Wprowadzenie do teorii grafów

Graf i jego silnie
spójne składowe

5.05.08

Dr inż. Krzysztof Lisiecki

274

Wprowadzenie do teorii grafów

Rozważmy teraz relację

ℜ

określoną w

zbiorze wierzchołków digrafu w następujący
sposób:

„wierzchołek X w relacji z wierzchołkiem Y,
gdy istnieje droga łącząca X z Y oraz droga
łącząca Y z X.”

5.05.08

Dr inż. Krzysztof Lisiecki

275

Wprowadzenie do teorii grafów

Tak

określona

relacja

jest

relacja

równoważności,

tzn.

jest

zwrotna,

symetryczna i przechodnia.

 

Można udowodnić, że klasy abstrakcji tak
określonej

relacji

ℜ

są

zbiorami

wierzchołków silnie spójnych składowych
digrafu.

5.05.08

Dr inż. Krzysztof Lisiecki

276

Wprowadzenie do teorii grafów

Definicja

Zbiór tych krawędzi grafu, których usunięcie
spowoduje zwiększenie liczby składowych
spójnych nazywamy
zbiorem rozspajającym grafu

G.

Przykładem zbioru rozspajającego grafu jest
każdy most.

5.05.08

Dr inż. Krzysztof Lisiecki

277

Wprowadzenie do teorii grafów

Definicja

Rozcięciem grafu nazywamy każdy zbiór
rozspajający, którego żaden podzbiór
właściwy nie jest zbiorem rozspajającym.

5.05.08

Dr inż. Krzysztof Lisiecki

278

Wprowadzenie do teorii grafów

Przykłady
rozcięć

{a}, {b,c}, {c,d,e}, {e,f,g}, {c,d,f,g}

5.05.08

Dr inż. Krzysztof Lisiecki

279

Wprowadzenie do teorii grafów

Definicja

Spójnością krawędziową grafu spójnego

G

nazywamy liczbę

λ

(

G) równą liczności

najmniej licznego rozcięcia grafu

G.

5.05.08

Dr inż. Krzysztof Lisiecki

280

Wprowadzenie do teorii grafów

Twierdzenie

Spójność krawędziowa grafu spójnego

G nie

może przekroczyć stopnia wierzchołka o
najmniejszym stopniu w grafie.

5.05.08

Dr inż. Krzysztof Lisiecki

281

Wprowadzenie do teorii grafów

Definicja

Graf

G nazywamy k-spójnym krawędziowo,

jeżeli

λ

(

G)

k

≥

5.05.08

Dr inż. Krzysztof Lisiecki

282

Wprowadzenie do teorii grafów

Graf 1-spójny
krawędziowo

Graf 2-spójny
krawędziowo

5.05.08

Dr inż. Krzysztof Lisiecki

283

Wprowadzenie do teorii grafów

Definicja

Zbiorem rozdzielającym grafu spójnego

G

nazywamy zbiór wierzchołków tego grafu,
których usunięcie wraz z krawędziami z nimi
incydentnymi powoduje, że graf przestaje być
spójny.

Zbiór rozdzielający składający się z jednego
tylko wierzchołka nazywamy wierzchołkiem
rozcinającym.

5.05.08

Dr inż. Krzysztof Lisiecki

284

Wprowadzenie do teorii grafów

Graf i jego zbiór rozdzielający (wierzchołki x i y).
Kolorem szarym zaznaczone są krawędzie incydentne z
wierzchołkami zbioru rozdzielającymi.

5.05.08

Dr inż. Krzysztof Lisiecki

285

Wprowadzenie do teorii grafów

Graf i jego wierzchołek rozcinający (x). Kolorem szarym
zaznaczone są krawędzie incydentne z wierzchołkami
rozdzielającym.

5.05.08

Dr inż. Krzysztof Lisiecki

286

Wprowadzenie do teorii grafów

Definicja

Spójnością wierzchołkową grafu spójnego
G, który nie jest pełny, nazywamy liczbę

κ

(

G) równą liczności najmniej licznego

rozcięcia grafu

G.

5.05.08

Dr inż. Krzysztof Lisiecki

287

Wprowadzenie do teorii grafów

Definicja

Graf nazywamy k-spójnym wierzchołkowo,
gdy

κ

(

G)

k

≥

Twierdzenie

W dowolnym grafie spójnym

κ

(

G)

λ

(

G).

≤

5.05.08

Dr inż. Krzysztof Lisiecki

288

Wprowadzenie do teorii grafów

Twierdzenie

Maksymalna spójność wierzchołkowa
w grafie wymiaru n, posiadającym m
krawędzi jest równa całkowitej części liczby

n

m

2

5.05.08

Dr inż. Krzysztof Lisiecki

289

Wprowadzenie do teorii grafów

Dowód:

Niech  oznacza spójność krawędziową grafu

G.

Istnieje zatem

zbiór rozspajający S posiadający 

krawędzi. Niech S dzieli wierzchołki grafu na
podzbiory V

1

oraz V

2

.

Przez usunięcie co najwyżej  wierzchołków
z V

1

(lub V

2

), do których krawędzie

ze zbioru

rozspajającego są incydentne usuniemy cały zbiór S.

c.n.u.

5.05.08

Dr inż. Krzysztof Lisiecki

290

Wprowadzenie do teorii grafów

κ

(

G)

Wniosek

W dowolnym spójnym grafie wymiaru n,
posiadającym m krawędzi prawdziwa jest
nierówność

λ

(

G)

≤

λ

(

G)

≤

n

m

2

5.05.08

Dr inż. Krzysztof Lisiecki

291

Wprowadzenie do teorii grafów

Definicja

Graf nazywamy k-spójnym, jeżeli jego
spójność wierzchołkowa wynosi k.

5.05.08

Dr inż. Krzysztof Lisiecki

292

Wprowadzenie do teorii grafów

Twierdzenie

Graf spójny jest k-spójny wtedy i tylko
wtedy, gdy każda para jego wierzchołków
jest połączona przez k lub więcej wzajemnie
nie przecinających się dróg, a co najmniej
jedna para wierzchołków jest połączona przez
dokładnie k takich dróg.

5.05.08

Dr inż. Krzysztof Lisiecki

293

Wprowadzenie do teorii grafów

Definicja

Dwie drogi w grafie nazywamy rozłącznymi
krawędziowo, jeżeli nie mają wspólnych
krawędzi, choć mogą się przecinać.

5.05.08

Dr inż. Krzysztof Lisiecki

294

Wprowadzenie do teorii grafów

Twierdzenie

Spójność krawędziowa grafu wynosi k
wtedy i tylko wtedy, gdy każda para
wierzchołków w tym grafie połączona jest
przez k lub więcej dróg rozłącznych
krawędziowo, a co najmniej jedna para
wierzchołków jest połączona przez
dokładnie k takich dróg.

5.05.08

Dr inż. Krzysztof Lisiecki

295

Wprowadzenie do teorii grafów

Definicja

Pokolorowaniem

(właściwym)

obszarów

wyznaczonych przez graf nazywamy takie
przyporządkowanie obszarom kolorów, aby
żadne dwa sąsiednie obszary nie miały tej
samej barwy.

5.05.08

Dr inż. Krzysztof Lisiecki

296

Wprowadzenie do teorii grafów

Definicja

Mapą nazywamy każdy 3-spójny graf
planarny.

 

Twierdzenie (o czterech barwach)

Każdą mapę można pokolorować właściwie
używając co najwyżej czterech kolorów.

5.05.08

Dr inż. Krzysztof Lisiecki

297

Wprowadzenie do teorii grafów

Przykład

5.05.08

Dr inż. Krzysztof Lisiecki

298

Wprowadzenie do teorii grafów

Twierdzenie

Mapę można pokolorować dwoma kolorami
wtedy i tylko wtedy, gdy istnieje w niej cykl
Eulera.

5.05.08

Dr inż. Krzysztof Lisiecki

299

Wprowadzenie do teorii grafów

Przykład

5.05.08

Dr inż. Krzysztof Lisiecki

300

Wprowadzenie do teorii grafów

Kolorowanie grafu to także kolorowanie
wierzchołków i krawędzi.

Istnieje szeroka gama zastosowań zarówno
kolorowania wierzchołków jak i krawędzi:

•podział logiki w komputerach

•problem ułożenia planu lekcji w szkole

•teoria kodowania

•logistyce

5.05.08

Dr inż. Krzysztof Lisiecki

301

Wprowadzenie do teorii grafów

Definicja

Graf prosty nazwiemy k-kolorowalnym, gdy
istnieje funkcja przyporządkowująca
każdemu wierzchołkowi jeden z k kolorów
tak, aby każdym dwóm sąsiadującym
wierzchołkom przyporządkowane były różne
kolory.

5.05.08

Dr inż. Krzysztof Lisiecki

302

Wprowadzenie do teorii grafów

Uwaga:

Zajmując się kolorowaniem grafu rozpatrujemy tylko
grafy spójne, gdyż w przypadku grafu, który nie jest
spójny kolory użyte do pokolorowania jednej składowej
spójnej nie mają wpływu na kolory, których użyjemy do
pokolorowania innej składowej.

Oczywiście,

liczba

kolorów

potrzebna

do

pokolorowania całego grafu jest równa maksimum
spośród liczb kolorów użytych do pokolorowania jego
składowych spójnych.

5.05.08

Dr inż. Krzysztof Lisiecki

303

Wprowadzenie do teorii grafów

Definicja

Liczbą chromatyczną grafu nazywamy k,
jeżeli graf jest k-kolorowalny i jednocześnie
nie

jest

(k-1)-kolorowalny.

Liczbę

chromatyczna grafu

G oznaczamy

χ

(

G) .

5.05.08

Dr inż. Krzysztof Lisiecki

304

Wprowadzenie do teorii grafów

Przykład

Liczba chromatyczna poniższego grafu
wynosi 3.

5.05.08

Dr inż. Krzysztof Lisiecki

305

Wprowadzenie do teorii grafów

Przykład

Liczba chromatyczna poniższego grafu
wynosi 4.

5.05.08

Dr inż. Krzysztof Lisiecki

306

Wprowadzenie do teorii grafów

Twierdzenie

Liczba chromatyczna grafu pełnego
wymiaru n jest równa n, zaś grafu pustego
jest równa 1.

5.05.08

Dr inż. Krzysztof Lisiecki

307

Wprowadzenie do teorii grafów

Twierdzenie

Graf wymiaru składający się z jednego tylko

cyklu ma liczbę chromatyczną

 2, gdy n jest liczbą parzysta,

 3, gdy n jest liczą nieparzystą.

5.05.08

Dr inż. Krzysztof Lisiecki

308

Wprowadzenie do teorii grafów

Twierdzenie

Liczba chromatyczna drzewa składającego
się z co najmniej dwóch wierzchołków jest
równa 2.

5.05.08

Dr inż. Krzysztof Lisiecki

309

Wprowadzenie do teorii grafów

Twierdzenie

Liczba chromatyczna dowolnego grafu prostego o
m krawędziach spełnia nierówność

4

1

2

2

1

+

+

≤

m

G)

(

χ

5.05.08

Dr inż. Krzysztof Lisiecki

310

Wprowadzenie do teorii grafów

Przykład

Kolorowanie wierzchołków grafu

5.05.08

Dr inż. Krzysztof Lisiecki

311

Wprowadzenie do teorii grafów

Przykład

(zastosowanie do układania planu zajęć 1)

Mamy 3 przedmioty obowiązkowe a, b, c
oraz 4 przedmioty do wyboru:d, e, f, g

Chcemy ułożyć plan tak, aby w tym samym czasie
nie odbywały się przedmioty, na które powinien
chodzić student

5.05.08

Dr inż. Krzysztof Lisiecki

312

Wprowadzenie do teorii grafów

Przykład

(zastosowanie do układania planu zajęć 1)

Rysujemy graf, w którym wierzchołki oznaczają przedmioty,
a krawędzie łączą wierzchołki odpowiadające przedmiotom,
które nie mogą się odbywać w tym samym czasie

5.05.08

Dr inż. Krzysztof Lisiecki

313

Wprowadzenie do teorii grafów

Przykład

(zastosowanie do układania planu zajęć 1)

Liczba chromatyczna narysowanego grafu jest równa liczbie
różnych terminów zajęć jest koniecznych, aby zajęcie się nie
pokrywały.

4

=

)

(G

χ

5.05.08

Dr inż. Krzysztof Lisiecki

314

Wprowadzenie do teorii grafów

Przykład

(zastosowanie do układania planu zajęć 2)

Mamy 3 przedmioty obowiązkowe a, b, c
oraz 4 przedmioty do wyboru:d, e, f, g, przy czym
każdy student musi wybrać jeden z przedmiotów d
lub e oraz jeden z przedmiotów f lub g.

Chcemy ułożyć plan tak, aby w tym samym czasie
nie odbywały się przedmioty, na które powinien
chodzić student

5.05.08

Dr inż. Krzysztof Lisiecki

315

Wprowadzenie do teorii grafów

Przykład

(zastosowanie do układania planu zajęć 2)

Rysujemy graf, w którym wierzchołki oznaczają przedmioty,
a krawędzie łączą wierzchołki odpowiadające przedmiotom,
które nie mogą się odbywać w tym samym czasie

5.05.08

Dr inż. Krzysztof Lisiecki

316

Wprowadzenie do teorii grafów

Przykład

(zastosowanie do układania planu zajęć 2)

Liczba chromatyczna narysowanego grafu jest równa liczbie
różnych terminów zajęć jest koniecznych, aby zajęcie się nie
pokrywały.

5

=

)

(G

χ

5.05.08

Dr inż. Krzysztof Lisiecki

317

Wprowadzenie do teorii grafów

Przykład

(rozsadzenie gości na przyjęciu 1)

Na przyjęcie przyjdzie ośmioro gości:
Anna, Ewa, Maria, Zofia, Jan, Marcin, Tomek i Stefan.

Wiemy, że :
Ewa nie lubi się ze Stefanem, Zofia z Marią i
Tomkiem, Maria z Janem, Jan z Marcinem, a Marcin
ze Stefanem.

Ile trzeba przygotować stolików, aby nielubiące się
osoby nie siedziały przy tym samym stoliku?

5.05.08

Dr inż. Krzysztof Lisiecki

318

Wprowadzenie do teorii grafów

Przykład

(rozsadzenie gości na przyjęciu 1)

Rysujemy graf, w którym wierzchołki oznaczają gości, a
krawędzie łączą wierzchołki odpowiadające osobom, które się nie
lubią.

5.05.08

Dr inż. Krzysztof Lisiecki

319

Wprowadzenie do teorii grafów

Przykład

(rozsadzenie gości na przyjęciu 1)

Liczba chromatyczna narysowanego grafu jest równa liczbie
potrzebnych stolików.

2

=

)

(G

χ

5.05.08

Dr inż. Krzysztof Lisiecki

320

Wprowadzenie do teorii grafów

Przykład

(rozsadzenie gości na przyjęciu 1)

5.05.08

Dr inż. Krzysztof Lisiecki

321

Wprowadzenie do teorii grafów

Przykład

(rozsadzenie gości na przyjęciu 2)

Na przyjęcie przyjdzie ośmioro gości:
Anna, Ewa, Maria, Zofia, Jan, Marcin, Tomek i Stefan.

Wiemy, że :
Ewa nie lubi się ze Stefanem

i z Marcinem

,

Zofia z Marią i Tomkiem, Maria z Janem, Jan z
Marcinem, a Marcin ze Stefanem.

Ile trzeba przygotować stolików, aby nielubiące się
osoby nie siedziały przy tym samym stoliku?

5.05.08

Dr inż. Krzysztof Lisiecki

322

Wprowadzenie do teorii grafów

Przykład

(rozsadzenie gości na przyjęciu 2)

Rysujemy graf, w którym wierzchołki oznaczają gości, a
krawędzie łączą wierzchołki odpowiadające osobom, które się nie
lubią.

5.05.08

Dr inż. Krzysztof Lisiecki

323

Wprowadzenie do teorii grafów

Przykład

(rozsadzenie gości na przyjęciu 2)

Liczba chromatyczna narysowanego grafu jest równa liczbie
potrzebnych stolików.

3

=

)

(G

χ

5.05.08

Dr inż. Krzysztof Lisiecki

324

Wprowadzenie do teorii grafów

Przykład

(rozsadzenie gości na przyjęciu 2)

5.05.08

Dr inż. Krzysztof Lisiecki

325

Wprowadzenie do teorii grafów

Definicja

Graf nazywamy k-kolorowalnym
krawędziowo, jeśli można pokolorować jego
krawędzie k kolorami tak, aby żadne dwie
sąsiednie krawędzie nie miały tego samego
koloru.

5.05.08

Dr inż. Krzysztof Lisiecki

326

Wprowadzenie do teorii grafów

Definicja

Indeksem chromatycznym grafu nazywamy
liczbę k, jeżeli graf jest k-kolorowalny
krawędziowo i jednocześnie nie jest
(k-1)-kolorowalny krawędziowo.

Indeks chromatyczny grafu

G oznaczamy

χ

’(

G).

5.05.08

Dr inż. Krzysztof Lisiecki

327

Wprowadzenie do teorii grafów

Przykład

Indeks chromatyczny
grafu z rysunku jest
równy 3.

5.05.08

Dr inż. Krzysztof Lisiecki

328

Wprowadzenie do teorii grafów

Twierdzenie Vizinga (1964).

Indeks chromatyczny

χ

’(

G) grafu G , w

którym najwyższy stopień wierzchołka
wynosi p, spełnia nierówność

1

+

≤

p

χ

’(

G)

≤

p

5.05.08

Dr inż. Krzysztof Lisiecki

329

Wprowadzenie do teorii grafów

Drogą Hamiltona nazywamy drogę, który
przechodzi przez każdy wierzchołek grafu
dokładnie jeden raz

Cyklem Hamiltona nazywamy cykl, który
przechodzi przez każdy wierzchołek grafu
dokładnie jeden raz

5.05.08

Dr inż. Krzysztof Lisiecki

330

Wprowadzenie do teorii grafów

Grafem półhamiltonowskim nazywamy graf,
w którym istnieje droga przechodząca przez
każdy wierzchołek grafu.

Grafem hamiltonowskim nazywamy graf, w
którym istnieje cykl Hamiltona.

5.05.08

Dr inż. Krzysztof Lisiecki

331

Wprowadzenie do teorii grafów

Twierdzenie (Ore, 1960)

Jeżeli graf prosty ma n wierzchołków,
oraz

dla każdej pary wierzchołków niesąsiednich,
to jest hamiltonowski.

n

X

X

j

i

≥

+

)

deg(

)

deg(

3

≥

n

5.05.08

Dr inż. Krzysztof Lisiecki

332

Wprowadzenie do teorii grafów

Twierdzenie (Dirac, 19552)

Jeżeli graf prosty ma n,
wierzchołków oraz

dla każdego wierzchołka, to jest
hamiltonowski.

3

≥

n

2

n

X

i

≥

)

deg(

5.05.08

Dr inż. Krzysztof Lisiecki

333

Wprowadzenie do teorii grafów

Twierdzenie

Jeżeli graf prosty ma n wierzchołków,
oraz co najmniej

krawędzi, to jest hamiltonowski.

3

≥

n

2

2

1

2

1

+

−

−

)

)(

(

n

n

5.05.08

Dr inż. Krzysztof Lisiecki

334

Wprowadzenie do teorii grafów

Kod Graya

Kodem Graya długości n nazywamy ciąg
wszystkich różnych ciągów n-wyrazowych,
których wyrazami są liczby 0 lub 1 i które
różnią się od siebie dokładnie jedną cyfrą.

Ciągów takich jest

n

2

5.05.08

Dr inż. Krzysztof Lisiecki

335

Wprowadzenie do teorii grafów

Jeśli każdemu z ciągów Graya długości n,
przypiszemy wierzchołki pewnego grafu
wymiaru i połączymy krawędzią te
ciągi, które różnią się od siebie dokładnie
jedna cyfrą, to otrzymamy cykl Hamiltona.

n

2

5.05.08

Dr inż. Krzysztof Lisiecki

336

Wprowadzenie do teorii grafów

Twierdzenie

Jeżeli w grafie prostym najwyższy stopień

wierzchołka wynosi n, to graf ten jest n+1

kolorowalny wierzchołkowo.

5.05.08

Dr inż. Krzysztof Lisiecki

337

Wprowadzenie do teorii grafów

Grafem dwudzielnym nazywamy graf (G,X),
w którym zbiór wierzchołków X można
podzielić na dwa rozłączne i niepuste
podzbiory X

1

oraz X

2

tak, że każda krawędź

w grafie łączy wierzchołek z jednego
podzbioru z wierzchołkiem drugiego
podzbioru.

5.05.08

Dr inż. Krzysztof Lisiecki

338

Wprowadzenie do teorii grafów

Grafy dwudzielne

5.05.08

Dr inż. Krzysztof Lisiecki

339

Wprowadzenie do teorii grafów

Grafy dwudzielne

5.05.08

Dr inż. Krzysztof Lisiecki

340

Wprowadzenie do teorii grafów

Przykład

Grafe dwudzielnym jest graf kodu Graya
(dzielimy zbiór wierzchołków na dwa
podzbiory, w których wierzchołki mają
parzystą bądź nieparzystą liczbę jedynek.

5.05.08

Dr inż. Krzysztof Lisiecki

341

Wprowadzenie do teorii grafów

Graf dwudzielny nazywamy pełnym grafem
dwudzielnym, jeśli każdy wierzchołek zbioru
X

1

jest połączony dokładnie jedną krawędzią

z każdym wierzchołkiem zbioru X

2

.

5.05.08

Dr inż. Krzysztof Lisiecki

342

Wprowadzenie do teorii grafów

Grafy pełne dwudzielne

5.05.08

Dr inż. Krzysztof Lisiecki

343

Wprowadzenie do teorii grafów

Dla dowolnych liczb naturalnych m i n
wszystkie pełne grafy dwudzielne takie, że |
X

1

|=m oraz |X

2

|=n są izomorficzne.

Grafy takie oznaczamy K

m,n

Łatwo zauważyć, że grafy K

m,n

oraz K

n,m

są

izomorficzne.

5.05.08

Dr inż. Krzysztof Lisiecki

344

Wprowadzenie do teorii grafów

Twierdzenie

Jeżeli graf dwudzielny jest hamiltonowski, to
liczba wierzchołków jednego podzbioru jest
równa liczbie wierzchołków drugiego
podzbioru.

Jeżeli graf jest półhamiltonowski, to liczby te
różnią się co najwyżej o jeden.

5.05.08

Dr inż. Krzysztof Lisiecki

345

Wprowadzenie do teorii grafów

Uwaga:

Dla pełnych grafów dwudzielnych wymiaru
co najmniej 3, prawdziwe jest również
twierdzenie odwrotne.

5.05.08

Dr inż. Krzysztof Lisiecki

346

Wprowadzenie do teorii grafów

Def. Listą nazywamy uporządkowany
ciąg elementów

Przykładem listy jest tablica
jednowymiarowa

5.05.08

Dr inż. Krzysztof Lisiecki

347

Wprowadzenie do teorii grafów

Często wygodniej jest posługiwać się listą
bez konieczności odwoływania się do
indeksów.

Przykładami takich list są kolejki i stosy.

5.05.08

Dr inż. Krzysztof Lisiecki

348

Wprowadzenie do teorii grafów

Def. Kolejką nazywamy listę z trzema

operacjami na jej elementach:

2. dodawania nowego elementu,

3. zdejmowania pierwszego elementu,

4. sprawdzania, czy kolejka jest pusta

(FIFO – first in first out)

5.05.08

Dr inż. Krzysztof Lisiecki

349

Wprowadzenie do teorii grafów

Def. Stosem nazywamy listę z trzema

operacjami na jej elementach:

2. dodawania nowego elementu na wierzch

stosu,

3. zdejmowania elementu z wierzchu

stosu,

4. sprawdzania, czy stos jest pusty

(LIFO – last in first out)

5.05.08

Dr inż. Krzysztof Lisiecki

350

Wprowadzenie do teorii grafów

Implementacja kolejki

Tworzymy tablicę

KOLEJKA[0..max]

oraz

dwie zmienne

PoczątekKolejki

i

KoniecKolejki

.

Zmienna

PoczątekKolejki

wskazuje pierwszy

element kolejki, zaś zmienna

KoniecKolejki

wskazuje pierwsze wolne miejsce poza
kolejką.

5.05.08

Dr inż. Krzysztof Lisiecki

351

Wprowadzenie do teorii grafów

Kolejka jest pusta, jeżeli

KoniecKolejki=PoczątekKolejki

Operacje włożenia nowego elementu x do
kolejki implementujemy za pomocą
instrukcji:

KOLEJKA[KoniecKolejki]:=x

KoniecKolejki:=KoniecKolejki+1

5.05.08

Dr inż. Krzysztof Lisiecki

352

Wprowadzenie do teorii grafów

Operacje zdjęcia elementu z

KOLEJKI

implementujemy za pomocą instrukcji:

x:=KOLEJKA[PoczątekKolejki];

PoczątekKolejki:=PoczątekKolejki+1

Operacja zdejmowania elementu z kolejki
może być wykonana tylko wtedy gdy

KoniecKolejki



PoczątekKolejki

5.05.08

Dr inż. Krzysztof Lisiecki

353

Wprowadzenie do teorii grafów

Implementacja stosu

Tworzymy tablicę

STOS[0..max]

oraz

zmienną

WierzchStosu

Zmienna

WierzchStosu

wskazuje na pierwsze

wolne miejsce w tablicy

STOS

5.05.08

Dr inż. Krzysztof Lisiecki

354

Wprowadzenie do teorii grafów

Operacje włożenia nowego elementu x na

STOS

implementujemy za pomocą instrukcji:

STOS[WierzchStosu]:=x

WierzchStosu:= WierzchStosu+1

Jeżeli wartość zmiennej

WierzchStosu=max+1

to stos jest pełny i nie można na niego
wkładać nowych elementów

5.05.08

Dr inż. Krzysztof Lisiecki

355

Wprowadzenie do teorii grafów

Operacje zdjęcia elementu z wierzchu

STOSU

implementujemy za pomocą

instrukcji:

WierzchStosu:= WierzchStosu-1

x:=STOS[WierzchStosu]

Operację tę można wykonać, jeżeli stos nie
jest pusty, czyli, gdy zmienna

WierzchStosu>0

5.05.08

Dr inż. Krzysztof Lisiecki

356

Wprowadzenie do teorii grafów

Algorytm znajdowania drogi Hamiltona

Poniższy algorytm jest algorytmem z
nawrotami z zastosowaniem stosu jako
struktury danych.

5.05.08

Dr inż. Krzysztof Lisiecki

357

Wprowadzenie do teorii grafów

Dane wejściowe:

2. Graf (X,G), w którym X oznacza zbiór

wierzchołków, a G zbiór krawędzi,

3. Wierzchołek początkowy

Dane wyjściowe:

Droga Hamiltona zaczynająca się od

wierzchołka x lub informacja o jej braku

X

x

∈

5.05.08

Dr inż. Krzysztof Lisiecki

358

Wprowadzenie do teorii grafów

•

Włóż x na stos

•

Dopóki stos nie jest pusty, powtarzaj:
* niech y będzie wierzchołkiem na wierzchu
stosu
* szukamy wierzchołka w o najniższym
numerze, takiego, że
- w jest połączone z y,
- w nie wystepuje na stosie,
- jeżeli w poprzedniej iteracji zdjęto ze stosu
wierzchołek z, to
numer w powinien być większy od
numeru z

5.05.08

Dr inż. Krzysztof Lisiecki

359

Wprowadzenie do teorii grafów

Jeżeli takie w znajdziemy, to

wkładamy w na stos,
jeżeli wierzchołki na stosie tworzą już drogę
Hamiltona, to
koniec algorytmu – znaleziono drogę Hamiltona

Jeżeli takiego w nie znajdziemy, to

zdejmujemy y ze stosu

•

Jeżeli stos jest pusty i nie znaleziono drogi Hamiltona,
to
w grafie nie ma drogi Hamiltona.

5.05.08

Dr inż. Krzysztof Lisiecki

360

Wprowadzenie do teorii grafów

Przykład

Sprawdzić, czy w

podanym grafie
istnieje droga
Hamiltona
rozpoczynająca
się w
wierzchołku a

5.05.08

Dr inż. Krzysztof Lisiecki

361

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

362

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

363

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

364

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

365

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

366

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

367

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

368

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

369

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

370

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

371

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

372

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

373

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

374

Wprowadzenie do teorii grafów

Stos pusty – nie znaleziono drogi Hamiltona

5.05.08

Dr inż. Krzysztof Lisiecki

375

Wprowadzenie do teorii grafów

Przykład

Sprawdzić, czy w

podanym grafie
istnieje droga
Hamiltona
rozpoczynająca się
w wierzchołku a

5.05.08

Dr inż. Krzysztof Lisiecki

376

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

377

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

378

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

379

Wprowadzenie do teorii grafów

Przykład

Sprawdzić, czy w podanym grafie istnieje droga

Hamiltona rozpoczynająca się w wierzchołku a

5.05.08

Dr inż. Krzysztof Lisiecki

380

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

381

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

382

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

383

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

384

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

385

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

386

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

387

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

388

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

389

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

390

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

391

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

392

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

393

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

394

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

395

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

396

Wprowadzenie do teorii grafów

Stos pełny – znaleziono drogę Hamiltona

5.05.08

Dr inż. Krzysztof Lisiecki

397

Notacja asymptotyczna

Do szacowania złożoności czasowej
algorytmów, czyli szacowania czasu pracy
algorytmów używa się notacji
asymptotycznej

Pozwala nam to podzielić problemy na:

•łatwo rozwiązywalne

•trudno rozwiązywalne

5.05.08

Dr inż. Krzysztof Lisiecki

398

Notacja asymptotyczna

Niech f i g będą dwiema funkcjami
określonymi na zbiorze liczb naturalnych o
wartościach w zbiorze liczb rzeczywistych
dodatnich

{

}

0

>

∈

→

x

R

x

N

g

f

:

:

,

5.05.08

Dr inż. Krzysztof Lisiecki

399

Notacja asymptotyczna

Mówimy, że funkcja g jest o duże od f, gdy
istnieje dodatnia taka stała c oraz taka liczba
naturalna N

0

, że dla dowolnego n> N

0

zachodzi nierówność

)

(

)

(

n

f

c

n

g

⋅

≤

Zapisujemy ten fakt

))

(

(

)

(

n

f

O

n

g

=

5.05.08

Dr inż. Krzysztof Lisiecki

400

Notacja asymptotyczna

Przykład

)

(

4

4

3

5

2

n

O

n

n

=

−

+

gdyż dla dowolnego n

4

4

4

4

7

5

2

3

5

2

n

n

n

n

n

=

+

≤

−

+

5.05.08

Dr inż. Krzysztof Lisiecki

401

Notacja asymptotyczna

Mówimy, że funkcja g jest o małe od f, gdy

0

=

+ ∞

→

)

(

)

(

lim

n

f

n

g

n

Zapisujemy ten fakt

))

(

(

)

(

n

f

o

n

g

=

5.05.08

Dr inż. Krzysztof Lisiecki

402

Notacja asymptotyczna

Przykład

)

(

5

4

3

5

2

n

o

n

n

=

−

+

gdyż

0

3

5

2

5

4

=

−

+

+ ∞

→

n

n

n

n

lim

5.05.08

Dr inż. Krzysztof Lisiecki

403

Notacja asymptotyczna

Mówimy, że funkcja g jest omega duże od f,
gdy istnieje dodatnia taka stała c oraz taka
liczba naturalna N

0

, że dla dowolnego n> N

0

zachodzi nierówność

)

(

)

(

n

f

c

n

g

⋅

≥

Zapisujemy ten fakt

))

(

(

)

(

n

f

n

g

Ω

=

5.05.08

Dr inż. Krzysztof Lisiecki

404

Notacja asymptotyczna

...

...

≤

≤

≤

≤

≤

≤

3

2

3

n

n

n

n

n

n

n

n

m

dużych

ie

dostateczn

dla

log

<

2

4

2

≥

<

<

n

n

n

n

n

dla

!

5.05.08

Dr inż. Krzysztof Lisiecki

405

Notacja asymptotyczna

Twierdzenie

Każda z poniższych funkcji jest O od
wszystkich funkcji na prawo od niej:

n

n

n

n

n

n

n

n

n

n

n

n

n

n

,

!

,

...

,

,

,

log

,

,

,

,...,

log

,

2

1

3

2

2

3

2

⋅

5.05.08

Dr inż. Krzysztof Lisiecki

406

Notacja asymptotyczna

Twierdzenie

• Jeżeli f(n)=O(g(n)) i c jest stałą, to

cf(n)=O(g(n)),

• Jeżeli f(n)=O(g(n)) i h(n)=O(g(n)), to

f(n)+h(n)=O(g(n)),

• Jeżeli f(n)=O(a(n)) i g(n)=O(b(n)), to

f(n)g(n)=O(a(n)g(n))),

• Jeżeli f(n)=O(g(n)) i g(n)=O(h(n)), to

f(n)=O(h(n)).

5.05.08

Dr inż. Krzysztof Lisiecki

407

Notacja asymptotyczna

Twierdzenie

Dla dowolnych funkcji f(n) i g(n) mamy:

3. O(f(n))+O(g(n))=O(max{|f(n)|,|g(n)|})

4. O(f(n))O(g(n))=O(f(n)g(n))

5.05.08

Dr inż. Krzysztof Lisiecki

408

Notacja asymptotyczna

Klasa złożoności to zbiór problemów
obliczeniowych o podobnej złożoności
obliczeniowej (problemy do których
rozwiązania potrzebna jest podobna ilość
zasobów) . Podobne określenia stosujemy
do algorytmów.

5.05.08

Dr inż. Krzysztof Lisiecki

409

Notacja asymptotyczna

Problem P (ang. deterministic polynomial -
deterministycznie wielomianowy) to
problem, dla którego rozwiązanie można
znaleźć w czasie wielomianowym.

5.05.08

Dr inż. Krzysztof Lisiecki

410

Notacja asymptotyczna

Przykłady

2. Znajdowanie najkrótszej drogi w

grafie

3. Wyznaczanie minimalnego drzewa

spinającego

4. Znajdowanie drogi Eulera

5. Algorytm sortowania bąbelkowego

5.05.08

Dr inż. Krzysztof Lisiecki

411

Notacja asymptotyczna

Problem NP (niedeterminstycznie
wielomianowy, ang. nondeterministic
polynomial) to problem decyzyjny, dla
którego rozwiązanie można zweryfikować
w czasie wielomianowym

5.05.08

Dr inż. Krzysztof Lisiecki

412

Wprowadzenie do teorii grafów

Oczywiście każdy problem P jest
problemem NP, ale nie odwrotnie.

Jak dotąd nikomu nie udało się
udowodnić, ani zaprzeczyć, że P=NP.
Problem ten został sformułowany w roku
1971 i pozostaje otwarty do dziś

5.05.08

Dr inż. Krzysztof Lisiecki

413

Notacja asymptotyczna

Przykłady

2. Problem kliki

5.05.08

Dr inż. Krzysztof Lisiecki

414

Wprowadzenie do teorii grafów

Problem NP-zupełny (NPC) to problem,
którego status nie jest znany, inaczej jest
NP oraz jest NP-trudny (co najmniej tak
trudny jak problem NP

5.05.08

Dr inż. Krzysztof Lisiecki

415

Wprowadzenie do teorii grafów

Przykłady

2. Znalezienie cyklu Hamiltona

3. Problem maksymalnej kliki

4. Problem izomorfizmu dwóch grafów

5.05.08

Dr inż. Krzysztof Lisiecki

416

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

417

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

418

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

419

Wprowadzenie do teorii grafów

5.05.08

Dr inż. Krzysztof Lisiecki

420

Wprowadzenie do teorii grup

Mówimy, że w zbiorze G określone jest
działanie dwuargumentowe wewnętrzne,
jeżeli określona jest funkcja

G

G

G

f

→

×

:

5.05.08

Dr inż. Krzysztof Lisiecki

421

Wprowadzenie do teorii grup

Uwaga:

Działanie dwuargumentowe wewnętrzne na
parze zwykle oznaczamy ,
, lub

( )

G

b

a

∈

,

b

a 

b

a

+

b

a

∗

5.05.08

Dr inż. Krzysztof Lisiecki

422

Wprowadzenie do teorii grup

Działanie nazywamy

łącznym, gdy dla dowolnych elementów
zachodzi równość

przemiennym, gdy dla dowolnych
elementów zachodzi równość

G

G

G

→

×

:



G

c

b

a

∈

,

,

(

)

(

)

c

b

a

c

b

a









=

G

c

b

a

∈

,

,

a

b

b

a





=

5.05.08

Dr inż. Krzysztof Lisiecki

423

Wprowadzenie do teorii grup

5.05.08

Dr inż. Krzysztof Lisiecki

424

Wprowadzenie do teorii grup

5.05.08

Dr inż. Krzysztof Lisiecki

425

Wprowadzenie do teorii grup

5.05.08

Dr inż. Krzysztof Lisiecki

426

Wprowadzenie do teorii grup

5.05.08

Dr inż. Krzysztof Lisiecki

427

Wprowadzenie do teorii grup

5.05.08

Dr inż. Krzysztof Lisiecki

428

5.05.08

Dr inż. Krzysztof Lisiecki

429

5.05.08

Dr inż. Krzysztof Lisiecki

430

5.05.08

Dr inż. Krzysztof Lisiecki

431

5.05.08

Dr inż. Krzysztof Lisiecki

432

5.05.08

Dr inż. Krzysztof Lisiecki

433

Wprowadzenie do teorii grafów

Twierdzenie (Appel, Haken, 1976)

Każdy graf planarny prosty jest

4-kolorowalny wierzchołkowo.