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 : 

krzysztof.lisiecki@p.lodz.pl

  

lub        

krzysztof@lisiecki.org.pl



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.