Graf spójny: Różnice pomiędzy wersjami
[wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m robot dodaje: fr:Graphe connexe |
WP:SK, poprawka dwukropka |
||
Linia 1:
{{Teoria grafów}}
[[graf (matematyka)|Graf]] nazywamy '''spójnym''', jeśli dla każdej pary wierzchołków istnieje [[
Graf nie posiadający powyższej własności to <strong>''graf niespójny''</strong>.
Linia 19:
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.svg|center|150px|Graf spójny]]
Graf ten jest spójny, więc zgodnie z definicją ma jedną spójną składową.
Linia 27 ⟶ 26:
Po usunięciu krawędzi 2-3 i 4-5 graf ten nie jest już spójny, składa się wtedy 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>.
=== Zobacz też
* [[Graf k-spójny]]
* [[most (teoria grafów)|
* [[Punkt artykulacji|przegub]]
[[Kategoria:Teoria grafów]]
|