Graf spójny: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m szablon |
dr. |
||
Linia 3:
[[graf (matematyka)|Graf]] nazywamy '''spójnym''', jeśli pomiędzy dowolnymi dwoma jego wierzchołkami istnieje [[droga (teoria grafów)|droga]].
Graf nie posiadający powyższej własności to <strong>''graf niespójny''</strong>.
Maksymalny w sensie inkluzji spójny [[podgraf]] grafu nazywamy [[spójna składowa|spójną składową]]. Ilość spójnych składowych grafu ''G'' oznacza się przez <math>\omega(G)</math>.▼
----
Warunkiem konieczyny na to, by [[graf skierowany]] był spójny, jest spójność jego [[Graf podstawowy|grafu podstawowego]] (tego samego grafu bez kierunków na krawędziach).
----
▲Maksymalny w sensie inkluzji spójny [[podgraf]] grafu nazywamy [[spójna składowa|spójną składową]]. Ilość spójnych składowych grafu ''G'' oznacza się przez <math>\! \omega(G)</math>.
Inaczej ''spójną składową'' grafu G jest jego spójny [[podgraf]] nie zawarty w większym podgrafie spójnym grafu G.
Oczywiście <math>1 <= \omega(G) <= |G(V)|</math>▼
* <math> \omega(G)=1</math> oznacza, że graf G jest spójny,▼
* <math> \omega(G)=|G(V)|</math> oznacza, że ''G'' składa się z <math>|G(V)|</math> [[wierzchołek izolowany|izolowanych wierzchołków]].▼
Nieformalnie ''spójna składowa grafu'' jest to taki [[podgraf]], który można 'wydzielić' z całego grafu bez usuwania [[Krawędź|krawędzi]]. Graf spójny ma jedną ''spójna składową''. Dla przykładu, w [[Las (matematyka)|lesie]] spójnymi składowymi są [[Drzewo (matematyka)|drzewa]].Spójna składowa to fragment grafu, który nie jest połączony z innym fragmentem.
Wierzchołek ''v'' nazywa się '''rozspajającym''' graf ''G'' (albo '''przegubem''' w grafie ''G''), jeżeli usunięcie ''v'' z ''G'' (wraz z przyległymi do niego krawędziami) powoduje zwiększenie <math>\omega(G)</math> (czyli jeśli po usunięciu ''v'' wraz z przyległymi do niego krawędziami, graf ''G'' ma więcej składowych niż wcześniej).▼
▲Oczywiście <math>\! 1 <= \omega(G) <= |G(V)|</math>
▲* <math>\! \omega(G)=1</math> oznacza, że graf G jest spójny,
▲* <math>\! \omega(G)=|G(V)|</math> oznacza, że ''G'' składa się z <math>|G(V)|</math> [[wierzchołek izolowany|izolowanych wierzchołków]].
----
▲Wierzchołek ''v'' nazywa się '''rozspajającym''' graf ''G'' (albo '''przegubem''' w grafie ''G''), jeżeli usunięcie ''v'' z ''G'' (wraz z przyległymi do niego krawędziami) powoduje zwiększenie <math>\! \omega(G)</math> (czyli jeśli po usunięciu ''v'' wraz z przyległymi do niego krawędziami, graf ''G'' ma więcej składowych niż wcześniej).
==Przykład==
[[Grafika:6n-graf.png|center|100px|Graf spójny]]
Graf ten jest spójny, więc zgodnie z definicją ma jedną spójną składową.
[[Grafika:Graf_nie_spojny.png|center|100px|Graf nie spójny]]
Graf ten nie jest spójny, składa się z dwóch oddzielnych zbiorów wierzchołków:
<math>\! V_1 = \{ 1, 2, 5 \}</math><br/>
<math>\! V_2 = \{ 3, 4, 6 \}</math>
Każdy z tych zbiorów jest spójną składową grafu, a więc łącznie cały graf posiada dwie spójne składowe - <math>\! \omega (G)=2</math>.
[[Kategoria:Teoria grafów]]
| |||