Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

1

Grafem nazywamy uporządkowaną trójkę
, gdzie:



jest niepustym zbiorem wierzchołków
grafu



jest niepustym zbiorem krawędzi
grafu



jest funkcją incydencji grafu

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

2

Funkcja

incydencji

w

grafach

nieskierowanych:

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

3

Funkcja incydencji w grafach skierowanych:

Grafy

skierowane

będziemy

nazywać

digrafami.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

4

Krawędź nazywamy krawędzią zwykłą jeżeli
łączy dwa różne wierzchołki, w przeciwnym
przypadku nazywamy ją pętlą.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

5

Krawędzie

i

nazywamy krawędziami

wielokrotnymi jeśli

.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

6

Graf nazywamy prostym jeśli nie posiada
pętli i krawędzi wielokrotnych.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

7

Grafem pełnym nazywamy graf prosty,
w którym każde dwa wierzchołki są połączone
krawędzią.

Graf pełny o wierzchołkach oznaczamy
symbolem

.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

8

Wierzchołkiem

izolowanym

nazywamy

wierzchołek, który nie jest końcem żadnej
krawędzi.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

9

Grafem

skończonym

nazywamy

graf

o skończonym zbiorze wierzchołków i krawędzi.

W dalszej części wykładu będziemy zajmować
się jedynie grafami skończonymi.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

10

Drogą grafu nazywamy dowolny ciąg
krawędzi

spełniający zależność:

. Mówimy, że droga ta ma

długość .

Jeśli

, to droga ta jest zamknięta.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

11

Drogę nazywamy drogą prostą, jeśli wszystkie
krawędzie ją tworzące są różne.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

12

Zamkniętą drogę prostą o ciągu wierzchołków

nazywamy cyklem, jeśli

wszystkie wierzchołki

są różne.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

13

Graf nie zawierający cykli nazywamy grafem
acyklicznym.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

14

Każdy graf acykliczny jest grafem prostym.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

15

Stopniem wierzchołka ( ) grafu
nazywamy liczbę krawędzi z jako jednym
z wierzchołków, przy czym pętle zliczamy
podwójnie.

Liczbą

oznaczamy liczbę wierzchołków

grafu stopnia .

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

16

Suma stopni wierzchołków grafu jest dwa
razy większa od liczby jego krawędzi, czyli:

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

17

Grafem regularnym stopnia nazywamy graf,
w którym wszystkie wierzchołki są stopnia .

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

18

Każdy graf

jest grafem regularnym stopnia

.

Graf

ma

krawędzi.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

19

Jeśli krawędź łączy dwa wierzchołki, to
nazywamy je wierzchołkami sąsiednimi.

Macierzą

sąsiedztwa

digrafu

o

wierzchołkach

nazwiemy macierz

wymiaru , której każdy wyraz

jest

liczbą krawędzi od wierzchołka

do

wierzchołka

.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

20

Dla dowolnego digrafu o wierzchołkach

liczba dróg o długości

z wierzchołka

do wierzchołka

jest równa

elementowi

macierzy

, gdzie jest

macierzą sąsiedztwa digrafu .

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

21

Graf nazywamy spójnym, jeśli każda para
różnych wierzchołków jest połączona drogą
w tym grafie.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

22

Graf nazwiemy podgrafem grafu , jeżeli
oraz

.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

23

Spójny podgraf, który nie jest zawarty
w większym spójnym podgrafie grafu ,
nazywamy składową grafu .

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

24

Drogą Eulera w grafie nazywamy każdą
drogę prostą, zawierającą wszystkie krawędzie
grafu .

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

25

Cyklem Eulera w grafie nazywamy każdą
drogę prostą i zamkniętą, zawierającą wszystkie
krawędzie grafu .

Każdy cykl Eulera jest również drogą Eulera.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

26

Twierdzenie (Eulera) o istnieniu drogi Eulera
w grafie:

Graf ma drogę Eulera jest spójny i ma
dokładnie

dwa

wierzchołki

stopnia

nieparzystego lub ma każdy wierzchołek
stopnia parzystego.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

27

Twierdzenie (Eulera) o istnieniu cyklu Eulera
w grafie:

Graf ma cykl Eulera jest spójny i ma każdy
wierzchołek stopnia parzystego.

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

28

Izomorfizm grafów:

Grafy

i

) są izomorficzne, jeśli

istnieją bijekcje

i

takie, że:

Matematyka Dyskretna – wykład 9

dr Marcin Raniszewski

29

Izomorfizm

grafów

zachowuje

wszystkie

własności

grafu

(na

przykład:

liczbę

wierzchołków, liczbę krawędzi, liczbę krawędzi
wielokrotnych,

liczbę

pętli,

stopnie

wierzchołków).