Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

1

Drzewem nazywamy każdy graf spójny
i acykliczny.

Z

acykliczności

wynika

brak

krawędzi

wielokrotnych i pętli w każdym drzewie.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

2

Wierzchołki stopnia 1 w drzewie nazywamy
liśćmi.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

3

Jeśli graf jest drzewem, to:



każde dwa wierzchołki grafu połączone są
dokładnie jedną drogą prostą



graf przestaje być spójny po usunięciu
dowolnej krawędzi



graf przestaje być acykliczny po dodaniu
jakiejkolwiek krawędzi

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

4

Drzewo mające wierzchołków ma dokładnie
krawędzi.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

5

Drzewo binarne to drzewo, w którym
występują wierzchołki co najwyżej 3 stopnia.

Ukorzenione drzewo binarne to drzewo
binarne, w którym został wyróżniony jeden
wierzchołek stopnia 2 (zwany korzeniem).

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

6

Drzewo regularne to ukorzenione drzewo
binarne, w którym wszystkie wierzchołki
(oprócz korzenia) mają stopień 3 lub 1.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

7

Drzewem spinającym (rozpinającym) grafu
nazywamy podgraf grafu , który jest drzewem
i zawiera każdy wierzchołek grafu , czyli
.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

8

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

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

9

Graf

ma

drzew spinających.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

10

Drogę nazywamy drogą Hamiltona, jeśli
przechodzi przez każdy wierzchołek grafu
dokładnie jeden raz.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

11

Drogę zamkniętą, która przechodzi przez każdy
wierzchołek grafu dokładnie jeden raz,
z wyjątkiem ostatniego wierzchołka, którym
ponownie jest pierwszy wierzchołek, nazywamy
cyklem Hamiltona.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

12

Graf mający cykl Hamiltona nazywamy grafem
hamiltonowskim.

Graf hamiltonowski po dodaniu nowych
krawędzi

nie

przestaje

być

grafem

hamiltonowskim.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

13

Każdy graf

dla jest hamiltonowski.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

14

Graf prosty o co najmniej trzech
wierzchołkach jest hamiltonowski, jeśli:

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

15

Graf prosty jest hamiltonowski jeśli:

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

16

Graf nazywamy grafem dwudzielnym, jeśli
zbiór jest sumą dwóch niepustych
zbiorów rozłącznych

i

takich, że każda

krawędź w grafie łączy wierzchołek ze zbioru

z wierzchołkiem ze zbioru

. Jeśli ponadto

każdy wierzchołek zbioru

jest połączony

z każdym wierzchołkiem zbioru

dokładnie

jedną krawędzią, to graf nazywamy pełnym
grafem dwudzielnym.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

17

Symbolem

oznaczamy pełny graf

dwudzielny, w którym

i

.

Grafy

i

są izomorficzne.

Matematyka Dyskretna – wykład 10

dr Marcin Raniszewski

18

Załóżmy, że . Wtedy:



graf

ma cykl Hamiltona



graf

ma drogę Hamiltona