Matematyka dyskretna – dr Marcin Raniszewski

Matematyka Dyskretna – ćw. 11

Teoria grafów

Wprowadzenie, macierze sąsiedztwa, drogi i cykle Eulera

Grafem

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



jest niepustym zbiorem wierzchołków grafu



jest niepustym zbiorem krawędzi grafu



jest funkcją incydencji grafu , przy czym:

o w grafie nieskierowanym:

o w grafie skierowanym (digrafie):

Krawędź

nazywamy krawędzią zwykłą jeżeli łączy dwa różne wierzchołki, w przeciwnym przypadku

nazywamy ją pętlą.

Krawędzie

i

nazywamy krawędziami wielokrotnymi jeśli

.

Graf

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

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

Dalej będziemy rozważać tylko grafy skończone:

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.

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

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

nazywamy cyklem, jeśli wszystkie wierzchołki

są różne.

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 .

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

Zad. 1. Niech dany będzie graf

:

.

Narysuj ten graf. Wskaż w nim:

(a) pętle,
(b) trzy drogi zamknięte o długości 2,
(c) trzy drogi zamknięte o długościach 4, 5 i 8,
(d) trzy drogi proste o długościach 3, 4 i 6,
(e) trzy drogi proste zamknięte o długościach 2, 5 i 9,
(f) trzy cykle

Podaj stopnie wierzchołków oraz wyznacz liczby

.

Matematyka dyskretna – dr Marcin Raniszewski

Zad. 2. Niech dany będzie graf

, w którym:

,

,

,

,

. Ile krawędzi ma ten graf?

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

.

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 .

Zad. 3. Podaj ile jest dróg o długości 3 z wierzchołka

do oraz z do poniższego digrafu:

Graf

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

Graf

nazwiemy podgrafem grafu , jeżeli oraz

.

Spójny podgraf, który nie jest zawarty w większym spójnym podgrafie grafu

, nazywamy składową grafu .

Drogą Eulera w grafie

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

Cyklem Eulera w grafie

nazywamy każdą drogę prostą i zamkniętą, zawierającą wszystkie krawędzie grafu

.

Twierdzenia Eulera:



Graf ma drogę Eulera

jest spójny i ma dokładnie dwa wierzchołki stopnia nieparzystego lub ma

każdy wierzchołek stopnia parzystego



Graf ma cykl Eulera

jest spójny i ma każdy wierzchołek stopnia parzystego

Zad. 4. Podaj:

(a) przykład grafu spójnego, który nie ma cyklu Eulera,
(b) przykład grafu o wierzchołkach parzystego stopnia, który ma cykl Eulera,
(c) przykład grafu o wierzchołkach parzystego stopnia, który nie ma cyklu Eulera.

Matematyka dyskretna – dr Marcin Raniszewski

Zad. 5. Czy jest możliwe, aby owad poruszający się wzdłuż krawędzi sześcianu przeszedł
każdą krawędź dokładnie raz? Odpowiedź poprzyj odpowiednim rysunkiem grafu.

Zad. 6. Które z grafów mają cykle Eulera, a które nie mają i dlaczego? Podaj przykładowy
cykl Eulera dla grafów, które je posiadają.

Zad. 7. Które z grafów mają drogi Eulera, a które nie mają i dlaczego? Podaj taką drogę dla
grafów, które ją posiadają.

Matematyka dyskretna – dr Marcin Raniszewski

Zad. 8. Zbuduj graf mający zbiór wierzchołków

, w którym wierzchołki

i

są połączone krawędzią, jeśli ciągi

i

różnią się na dokładnie dwóch

współrzędnych.

(a) Ile składowych ma ten graf?
(b) Ile wierzchołków danego stopnia ma ten graf?
(c) Czy ten graf ma cykl Eulera? Czy ten graf ma drogę Eulera?

Zad. 9. Czy można tak przejść dany dom aby przez każde drzwi przejść dokładnie raz?
Odpowiedź uzasadnij. Jak zmieni się odpowiedź, jeśli drzwi między dwoma dużymi pokojami
będą zamknięte?