Składnik połączony to maksymalny połączony podgraf grafu nieskierowanego. Każdy wierzchołek należy do dokładnie jednego połączonego komponentu, podobnie jak każda krawędź. Graf jest połączony wtedy i tylko wtedy, gdy ma dokładnie jedną połączoną składową.
Silne składowe są maksymalnymi silnie połączonymi podgrafami grafu skierowanego.
Cięcie wierzchołkowe lub zbiór rozdzielający grafu połączonego G to zbiór wierzchołków, których usunięcie powoduje, że G jest rozłączny. Łączność wierzchołków κ(G) (gdzie G nie jest grafem pełnym) jest rozmiarem minimalnego odcięcia wierzchołków. Graf nazywamy k-połączonym lub k-połączonym, jeśli jego łączność wierzchołków jest k lub większa.
Precyzując, o dowolnym grafie G (kompletnym lub nie) mówi się, że jest k-połączony, jeśli zawiera co najmniej k+1 wierzchołków, ale nie zawiera zbioru k – 1 wierzchołków, których usunięcie powoduje rozłączenie grafu; a κ(G) definiuje się jako największe k takie, że G jest k-połączony. W szczególności, graf pełny o n wierzchołkach, oznaczany jako Kn, nie ma w ogóle cięć wierzchołków, ale κ(Kn) = n – 1.
Cięcie wierzchołkowe dla dwóch wierzchołków u i v jest zbiorem wierzchołków, których usunięcie z grafu powoduje rozłączenie u i v. Łączność lokalna κ(u, v) jest rozmiarem najmniejszego cięcia wierzchołkowego rozdzielającego u i v. Łączność lokalna jest symetryczna dla grafów nieskierowanych; to znaczy κ(u, v) = κ(v, u). Ponadto, z wyjątkiem grafów zupełnych, κ(G) jest równe minimum κ(u, v) nad wszystkimi niesąsiadującymi parami wierzchołków u, v.
2-połączalność jest również nazywana biconnektywnością, a 3-połączalność jest również nazywana triconnektywnością. Graf G, który jest połączony, ale nie jest 2-połączony, jest czasem nazywany rozłącznym.
Analogiczne pojęcia można zdefiniować dla krawędzi. W prostym przypadku, w którym przecięcie pojedynczej, konkretnej krawędzi spowodowałoby rozłączenie grafu, krawędź tę nazywamy mostem. Ogólniej, cięcie krawędziowe grafu G to zbiór krawędzi, których usunięcie powoduje rozłączenie grafu. Łączność krawędziowa λ(G) jest rozmiarem najmniejszego cięcia krawędziowego, a lokalna łączność krawędziowa λ(u, v) dwóch wierzchołków u, v jest rozmiarem najmniejszego cięcia krawędziowego odłączającego u od v. Również w tym przypadku lokalna łączność krawędziowa jest symetryczna. Graf nazywamy k-połączonym, jeśli jego łączność krawędzi jest k lub większa.
O grafie mówimy, że jest maksymalnie połączony, jeśli jego łączność jest równa jego minimalnemu stopniowi. O grafie mówi się, że jest maksymalnie połączony, jeśli jego połączalność krawędzi jest równa jego minimalnemu stopniowi.
Super- i hiperpołączalnośćEdit
O grafie mówi się, że jest superpołączony lub super-κ, jeśli każde minimalne przecięcie wierzchołka izoluje wierzchołek. O grafie mówi się, że jest hiperpołączony lub hiper-κ, jeśli usunięcie każdego minimalnego cięcia wierzchołka tworzy dokładnie dwie składowe, z których jedna jest wierzchołkiem izolowanym. Graf jest półhiperpołączony lub półhiper-κ, jeśli każde minimalne przecięcie wierzchołka dzieli go na dokładnie dwie składowe.
Precyzyjniej: o grafie połączonym G mówi się, że jest superpołączony lub super-κ, jeśli wszystkie minimalne przecięcia wierzchołków składają się z wierzchołków sąsiadujących z jednym wierzchołkiem (o minimalnym stopniu).O grafie połączonym G mówi się, że jest superpołączony lub super-λ, jeśli wszystkie minimalne cięcia krawędzi składają się z krawędzi padających na jakiś (minimalnego stopnia) wierzchołek.
Zbiór X grafu G nazywamy nietrywialnym zbiorem, jeśli X nie zawiera sąsiedztwa N(u) żadnego wierzchołka u ∉ X. Wtedy superpołączalność κ1 grafu G wynosi:
κ1(G) = min{|X| : X jest nietrywialnym zbiorem}.
Nietrywialny wycinek krawędziowy i superpołączalność krawędziowa λ1(G) są zdefiniowane analogicznie.
