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ędz
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ędz
łą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ędz
dokładnie raz? Odpowiedz
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?
Odpowiedz
uzasadnij. Jak zmieni siÄ™ odpowiedz
, jeśli drzwi między dwoma dużymi pokojami
będą zamknięte?
Matematyka dyskretna  dr Marcin Raniszewski