- Konigsberg_bridges.png (32.18 KiB) Przejrzano 3197 razy
Definicja 1:
Grafem nazywamy parę \(\displaystyle{ G=(V,E)}\), gdzie \(\displaystyle{ V}\) jest niepustym i skończonym zbiorem wierzchołków grafu, a \(\displaystyle{ E}\) -pewnym podzbiorem zbioru wszystkich dwuelementowych podzbiorów \(\displaystyle{ V}\) (w szczególności pustym lub pełnym ) nazywanym zbiorem krawędzi grafu \(\displaystyle{ G}\).
Zauważmy, że graf nie jest obiektem geometrycznym, lecz kombinatorycznym.
Przykład1:
- graf spojny.png (9.85 KiB) Przejrzano 3195 razy
1) \(\displaystyle{ \{ u,v \}}\)-krawędź łącząca wierzchołki \(\displaystyle{ u}\) i \(\displaystyle{ v}\)
2)\(\displaystyle{ \left|A \right|}\)- liczność zbioru \(\displaystyle{ A}\)
Definicja 2:
Mamy dany graf \(\displaystyle{ G=(V, E)}\). Weźmy sobie dowolny wierzchołek \(\displaystyle{ v \in V}\) grafu \(\displaystyle{ G}\) . Stopniem wierzchołka \(\displaystyle{ v}\) będziemy nazywać liczbę:
\(\displaystyle{ d(v)= \left| \{ u \in V : \{ u,v \} \in E \} \right|}\)
(liczność tych krawędzi ze zbioru \(\displaystyle{ E}\), do których należy wierzchołek \(\displaystyle{ v}\))
Spójrzmy się na przykład 1 i określmy stopnie wszystkich wierzchołków tego grafu:
wierzchołek nr 1 \(\displaystyle{ \rightarrow}\) 2
wierzchołek nr 2 \(\displaystyle{ \rightarrow}\) 3
wierzchołek nr 3 \(\displaystyle{ \rightarrow}\) 2
wierzchołek nr 4 \(\displaystyle{ \rightarrow}\) 3
wierzchołek nr 5 \(\displaystyle{ \rightarrow}\) 3
wierzchołek nr 6 \(\displaystyle{ \rightarrow}\) 1
Definicja 3:
Drogą w grafie \(\displaystyle{ G=(V, E)}\) nazywamy ciąg wierzchołków \(\displaystyle{ ( v_{1}, v_{2},..., v_{k} )}\) taki, że:
1) \(\displaystyle{ \forall _ {i=1,.., k-1 } \{ v_{i}, v_{i+1} \} \in E}\)
2)\(\displaystyle{ \forall _ {i,j=1,.., k-1 } i \neq j \Rightarrow \{ v_{i}, v_{i+1} \} \neq \{ v_{j}, v_{j+1} \}}\)
Spójrzmy się na przykład 1 i wskażmy kilka dróg tego grafu:
\(\displaystyle{ (1,2 )}\)-jest drogą
\(\displaystyle{ ( 1,2,3 )}\)-jest drogą
\(\displaystyle{ ( 4,1,2 )}\)-już drogą nie jest
Definicja 4 :
Graf \(\displaystyle{ G=(V, E)}\) nazywamy spójnym wtedy i tylko wtedy, gdy dla każdego \(\displaystyle{ v,u \in V}\) istnieje droga \(\displaystyle{ ( x_{1}, x_{2},..., x_{n} )}\) taka, że
\(\displaystyle{ x_{1}=u}\), \(\displaystyle{ x_{n}=v}\)
Przykład2:
Graf niespójny:
- graf niespójny.png (10.5 KiB) Przejrzano 3191 razy
Graf spójny:
- graf spójny 2.png (12.07 KiB) Przejrzano 3191 razy
Definicja 5 :
Cyklem nazywamy drogę \(\displaystyle{ ( x_{0}, x_{1},..., x_{k} )}\) taką, że \(\displaystyle{ x_{0}= x_{k}}\) i \(\displaystyle{ k>1}\).
Możemy teraz sformułować twierdzenie Eulera
Twierdzenie Eulera (1736):
W grafie \(\displaystyle{ G=(V, E)}\) istnieje cykl przechodzący przez wszystkie krawędzie i wierzchołki \(\displaystyle{ \Leftrightarrow}\) \(\displaystyle{ G}\) jest spójny i dla każdego \(\displaystyle{ v \in V}\)
\(\displaystyle{ 2| d(v)}\).
\(\displaystyle{ a|b}\) - ten symbol oznacza a dzieli b
Wniosek:
Graf ma drogę Eulera (drogę przechodzącą przez wszystkie wierzchołki i krawędzie ) wtedy i tylko wtedy, gdy jest spójny i ma, co najwyżej dwa wierzchołki stopni nieparzystych.
Spójrzmy teraz na kolejną zagadkę, którą można rozwiązać za pomocą tego samego twierdzenia.
- prostokąt.jpg (16.04 KiB) Przejrzano 3187 razy
Zatem, jak połączyć wszystkie ściany tego rysunku tak aby nie przeciąć 2 razy jednej ściany?
Odpowiedź brzmi: nie można tego zrobić. Znów korzystamy z wniosku z twierdzenia Eulera.
(dokładniejszą analizę tej zagadki pozostawiam czytelnikowi)
Rysunki pochodzą ze stron:
Kod: Zaznacz cały
http://pl.wikipedia.org/wiki/Zagadnienie_most%C3%B3w_kr%C3%B3lewieckich Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/Spójna_składowa_grafuKod: Zaznacz cały
https://pl.wikipedia.org/wiki/Graf_(matematyka)Kod: Zaznacz cały
https://osswiata.pl/stojda/2015/06/30/konigsberg-czyli-krotki-wyklad-o-teorii-grafow/