Graf spójny: Różnice pomiędzy wersjami
[wersja nieprzejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m Wspomagane przez bota ujednoznacznienie (tyle do zrobienia): Krawędź; zmiany kosmetyczne |
int. dr.red |
||
Linia 5:
Graf nie posiadający powyższej własności to '''''graf niespójny'''''.
----
Warunkiem koniecznym
----
Maksymalny, w sensie inkluzji, spójny [[podgraf]] grafu nazywamy 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.
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.
Oczywiście <math>\! 1 \le \omega(G) \le |G(V)|</math>
|