« poprzedni punkt   następny punkt »


3.3. Spójność i acykliczność


Definicja 3.3.1
Powiemy, że graf niezorientowany jest spójny wttw  dowolne dwa wierzchołki grafu są połączone drogą.

Oczywiście graf pełny jest grafem spójnym. Jest to dość oczywiste, bo mamy w takim grafie bardzo dużo krawędzi. A ile?

Lemat 3.3.1

Jeżeli  G = <V, E> jest grafem niezorientowanym, spójnym, o n wierzchołkach, to ma co najmniej n-1 krawędzi.


Grafy na rysunkach 3.1.1(b) jest spójny: z każdego z  miast można wytyczyć drogę do dowolnego innego miasta. Graf na rysunku  3.1.2, jeśli zapomnimy o orientacji krawędzi, też stanie się grafem spójnym. Natomiast graf  niezorientowany, o siedmiu wierzchołkach, przedstawiony na rysunku 3.3.1 nie jest grafem spójnym. Nie istnieje żadna droga łącząca, np. wierzchołek 1 i wierzchołek 7. 

 

Spójny podgraf grafu, który nie jest zawarty w żadnym większym spójnym podgrafie nazywa się spójną składową grafu.  Graf na rysunku 3.3.1 ma dwie spójne skadowe. Oczywiście do jednej składowej należy wierzchołek 1 i wszystkie wierzchołki osiągalne z 1 (tzn. 2, 3), a do drugiej składowej należy wierzchołek 7 i wszystkie wierzchołki z niego osiągalne (tzn. 4, 5, 6).

Dowód lematu 3.3.1.  Wyobraźmy sobie n punktów  na płaszczyźnie, odpowiadających wierzchołkom grafu G. Jeśli w grafie nie ma żadnych krawędzi, to taki graf ma n spójnych składowych. Dołączenie nowej krawędzi może spowodować zmniejszenie liczby spójnych składowych o 1, o ile dołączana krawędź łączy wierzchołki należące do różnych spójnych składowych grafu.  Po dołączeniu co najmniej n-1 krawędzi otrzymamy jedną spójną składową, a więc spójny graf.


Definicja 3.3.2
Powiemy, że graf jest acykliczny wttw  nie istnieje cykl w tym grafie.


Graf na rysunku 3.3.1 ma kilka cykli, nie jest więc acykliczny. Graf na rysunku 3.1.2 jest grafem acyklicznym. Im więcej krawędzi w grafie tym większa szansa, że stworzymy cykl.

Uwaga. Zauważmy, że jeżeli graf jest spójny, to dołączenie dowolnej nowej krawędzi do tego grafu powoduje powstanie cyklu. Rzeczywiście, niech G będzie spójnym grafem i niech u i v będą dwoma różnymi wierzchołkami, które nie są połączone krawędzią. Ponieważ graf jest spójny, zatem istnieje droga łącząca te wierzchołki. Jeśli dołączymy krawędź (u,v), to razem z istniejącą już drogą, utworzymy w grafie cykl.  

Lemat 3.3.2

Niech G = <V, E> będzie grafem niezorientowanym, acyklicznym, o n wierzchołkach, to G ma co najwyżej n-1 krawędzi.

Dowód. Rozważmy n punktów na płaszczyźnie odpowiadającyh wierzchołkom grafu G. Będziemy konstruowali graf G dołączając kolejno krawędzie. Liczba spójnyh składowych grafu, w którym nie ma żadych krawędzi wynosi n. Dołączenie krawędzi albo zmniejsza liczbę składowych spójnych, gdy dołączana krawędź łączy wierzchołki należące do różnych spójnych składowych, albo powoduje powstanie cyklu, gdy jest to krawędź łącząca wierzchołki należące do tej samej spójnej składowej grafu.  Jeżeli jakiś podgraf grafu G ma cykl, to oczywiście graf G też ma cykl. Zatem możemy dołączyć co najwyżej n-1 krawędzi, aby utworzony graf był acykliczny.

Pytanie 3.3.1 Czy graf, w którym występują 3 wierzchołki rzędu 2 i 2 wierzchołki rzędu 3 jest spójny i acykliczny?


« poprzedni punkt   następny punkt »