Graf spójny: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Liczba to ilość czegoś policzalnego. Nie powinno się traktować tych słów synonimicznie. |
-oczywiście |
||
Linia 1:
{{źródła|data=2012-06}}
{{Teoria grafów}}
'''Graf spójny''' – [[graf (matematyka)|
Graf nie posiadający powyższej własności to '''''graf niespójny'''''.
Warunkiem koniecznym, 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ójną składową. Liczba spójnych składowych grafu ''G'' oznacza się przez <math>\! \omega(G)</math>.
Linia 13 ⟶ 14:
Nieformalnie, ''spójna składowa grafu'' jest to taki [[podgraf]], który można 'wydzielić' z całego grafu bez usuwania [[Krawędź grafu|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.
* <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'' ('''przegubem''' lub '''punktem artykulacji''' 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).
Linia 31 ⟶ 32:
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>.
* [[Graf k-spójny]]
* [[most (teoria grafów)|most]]
|