Matematyka dyskretna – dr Marcin Raniszewski

Matematyka Dyskretna – ćw. 12

Teoria grafów

Drzewa, drzewa spinające, drogi i cykle Hamiltona, grafy dwudzielne

Drzewem

nazywamy każdy graf spójny i acykliczny. Z acykliczności wynika brak krawędzi wielokrotnych

i pętli w każdym drzewie.

Liśćmi w drzewie nazywamy wierzchołki stopnia 1.

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).

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

Zad. 1. Narysuj wszystkie drzewa mające siedem wierzchołków z dokładnością do
izomorfizmu. Które z nich są drzewami binarnymi? Które z nich są drzewami regularnymi?

Drzewem spinającym

grafu nazywamy taki podgraf grafu , który jest drzewem zawierającym każdy

wierzchołek grafu

, czyli .

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

Graf

ma

drzew spinających.

Zad. 2. Podaj liczbę drzew spinających dla grafów przedstawionych na rysunkach:

Zad. 3. Ile drzew spinających ma graf

? Narysuj je wszystkie.

Matematyka dyskretna – dr Marcin Raniszewski

Drzewo mające

wierzchołków ma dokładnie krawędzi.

Zad. 4. Pewne drzewo ma dwa wierzchołki stopnia 4, jeden wierzchołek stopnia 3 i jeden
wierzchołek stopnia 2. Jeśli pozostałe wierzchołki to liście, to ile wierzchołków jest w tym
grafie?

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

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.

Graf mający cykl Hamiltona nazywamy grafem hamiltonowskim.

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

. Graf

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

jest połączony z każdym

wierzchołkiem zbioru

dokładnie jedną krawędzią.

Symbolem

oznaczamy pełny graf dwudzielny, w którym

i

.

Załóżmy, że

. Wtedy:



graf

ma cykl Hamiltona



graf

ma drogę Hamiltona

Zad. 5. Narysuj:

(a) graf dwudzielny o sześciu wierzchołkach, który nie jest grafem pełnym dwudzielnym,

(b) graf

,

(c) graf o sześciu wierzchołkach, który nie jest dwudzielny.

Zad. 6. Narysuj:

(a) graf dwudzielny o sześciu wierzchołkach, który nie ma drogi Hamiltona,
(b) graf dwudzielny o siedmiu wierzchołkach, który ma drogę Hamiltona, ale nie ma

cyklu Hamiltona,

(c) graf dwudzielny o sześciu wierzchołkach, który ma cykl Hamiltona.

W podpunktach (b) i (c) wyznacz odpowiednio jedną drogę i jeden cykl Hamiltona.