Wstęp do Teorii Grafów

10.12.2009 - Kacper Król
Trudność

Rodzaje grafów


Multigrafem (często mówiąc ‘graf’ mamy na myśli właśnie ten rodzaj grafów) nazywamy graf, w którym występują pętle i krawędzie wielokrotne. Multigrafy możemy dostrzec patrząc na jakąś mapę samochodową: zazwyczaj jest więcej niż jedna droga pomiędzy dwoma miastami, a i nikt nie zabroni nam wyjechać kawałek za miasto, a potem do niego zawrócić (nie odwiedzając przy tym innego miasta).

Z kolei gdybyśmy chcieli przedstawić na rysunku, którzy z pośród członków naszych rodzin są rodzeństwem, to narysowalibyśmy graf prosty. Ja nie mógłbym być swoim rodzeństwem, ani też nie mógłbym być rodzeństwem swojej siostry więcej niż jeden raz :). Zatem w grafie prostym NIE ma pętli ani krawędzi wielokrotnych.


 Zad1. Czy potrafisz powiedzieć ile jest grafów prostych o n wierzchołkach?

 

Tu można zobaczyć odpowiedź

W grafie prostym nie ma pętli ani krawędzi wielokrotnych, zatem z każdego z $ n $ wierzchołków możemy poprowadzić krawędź do każdego z $ (n-1)  $wierzchołków. Pamiętajmy jednak, że jeśli połączymy krawędzią wierzchołek $ A $ z $ B $, to nie możemy połączyć już $ B $ z $ A $. Mamy zatem $ \frac{n\left(n-1\right)}{2} $ krawędzi. Narysujmy na kartce $ n $ wierzchołków i weźmy wszystkie krawędzie w garść. Teraz dla każdej krawędzi decydujemy czy ją rysujemy, czy wyrzucamy. Mamy zatem $ 2^{\frac{n\left(n-1\right)}{2}} $ możliwości narysowania krawędzi co jest równe liczbie grafów prostych na n wierzchołkach.

Podgrafem grafu G, nazywamy taki graf H, którego wszystkie wierzchołki należą do V(G), a krawędzie do E(G). Wracając do zagadki z meczami: gdybyśmy narysowali graf rozgrywek, to przykładem podgrafu, mógłby być kawałek pokazujący wszystkie mecze drużyny A oraz mecze, które rozegrały jej przeciwnicy (tj. wierzchołkami byłyby te drużyny, z którymi A zagrała, a krawędziami wszystkie mecze jakie odbyły się między nimi).




Czy z Wrocławia do Poznania prowadzi ścieżka, czy droga?


No właśnie, do tej pory używaliśmy słowo ‘droga’ mając na myśli drogę samochodową, ale patrząc na mapę jak na graf moglibyśmy powiedzieć, że z Wrocławia do Poznania istnieje zarówno ścieżka, jak i droga.

Ścieżką w grafie nazywamy skończony ciąg krawędzi $ v_{0} v_{1}, v_{1}v_{2}, ..., v_{m-1}v_{m} $, w której wszystkie krawędzie są różne (gdyby nie były różne, to mielibyśmy do czynienia z trasą). Często stosuje się zapis postaci: $ v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow ... \rightarrow v_{n} $
Ścieżkę możemy kojarzyć ze szlakiem turystycznym – możemy zatrzymywać się kilka razy w jednym schronisku, ale nie chcemy chodzić po tych samych szlakach.

Jeżeli dodatkowo nałożymy ograniczenie, że wszystkie wierzchołki w ścieżce są różne, to taka ścieżka będzie nazywana drogą. Jeżeli każda para wierzchołków, jest połączona drogą, to graf jest spójny ( to jest: jeśli z każdego wierzchołka da się przejść do każdego innego).

Drogę (tę w grafie) możemy kojarzyć z drogą (jezdnią) z miasta $ A $ do miasta $ B $: jeśli w trakcie jazdy odwiedzimy jakieś miasto $ C $ więcej niż jeden raz, to znaczy że źle skręciliśmy na którejś obwodnicy i nadłożyliśmy kilometrów, podobnie jeżeli przez jakiś fragment drogi jechaliśmy więcej niż raz, tzn. że zabłądziliśmy i niepotrzebnie pokonaliśmy kilka kilometrów.

Jeżeli pierwszy wierzchołek ścieżki jest równy ostatniemu, to taką ścieżkę nazywamy cyklem.

Przerwa na łamigłówkę: Czy potrafisz narysować poniższy rysunek nie odrywając ołówka od kartki i nie rysując po już narysowanych krawędziach?

 
Owszem, zagadka jest ‘ze szkolnej ławy’, ale tak na prawdę taką łamigłówkę trzeba rozwiązać w większości film transportowych czy komunikacji miejskiej! Wyobraźmy sobie sytuację, w której jesteśmy w zarządzie komunikacji miejskiej i zamiast kreślić taki rysunek ołówkiem, jeździmy po mapie autobusem (lubimy się bawić samochodzikami:)). Chcielibyśmy aby autobus spalił jak najmniej paliwa i jednocześnie przejechał jak najwięcej tras (najlepiej wszystkie!). Jeżeli będzie jeździł kilka razy tym samym odcinkiem, to z pewnością nie zaoszczędzimy na paliwie. Zatem najfajniejsza byłaby trasa, która przebiega przez wszystkie ulice i w dodatku przez każdą dokładnie raz – czyli szukamy tu odpowiedzi na to samo pytanie co w naszej łamigłówce.


Obie sytuacje możemy opisać grafami, zatem sformułujmy to pytanie w języku grafów: 
Czy w danym grafie istnieje cykl przechodzący przez każdą krawędź dokładnie jeden raz?

Okazuje się, że jest to ważny problem, czego może dowodzić fakt, że ktoś się juz nim zajął i go rozwiązał. Taki cykl nazywamy cyklem Eulera, bo tak się nazywał matematyk, który rozwiązał ten problem – wspomniany we wstępie artykułu. Dzięki niemu możemy zapisać następujące twierdzenie:
W grafie spójnym $ G $ istnieje cykl Eulera wtedy i tylko wtedy, gdy stopień każdego wierzchołka grafu $ G $ jest liczbą parzystą.

Graf w którym istnieje cykl Eulera nazywam grafem eulerowskim, a graf w którym istnieje ścieżka zawierająca każdą krawędź (ale kończąca się w innym od początkowego punkcie) jest grafem półeulerowskim.

4.333335
Twoja ocena: Brak Ocena: 4.3 (6 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com