O componentă conectată este un subgraf conectat maxim al unui graf nedirecționat. Fiecare vârf aparține exact unei componente conectate, la fel ca și fiecare muchie. Un graf este conectat dacă și numai dacă are exact o componentă conectată.
Componentele puternice sunt subgrafele maxim puternic conectate ale unui graf dirijat.
Un set de tăieturi de vârfuri sau un set de separare al unui graf conectat G este un set de vârfuri a căror îndepărtare face ca G să fie deconectat. Conectivitatea vârfurilor κ(G) (unde G nu este un graf complet) este dimensiunea unei tăieturi minime de vârfuri. Un graf se numește k-vertex-conectat sau k-conectat dacă conectivitatea vârfurilor sale este k sau mai mare.
Mai precis, orice graf G (complet sau nu) se spune că este k-vertex-conectat dacă conține cel puțin k+1 vârfuri, dar nu conține un set de k – 1 vârfuri a căror eliminare deconectează graful; iar κ(G) este definit ca fiind cel mai mare k astfel încât G este k-conectat. În special, un graf complet cu n vârfuri, notat Kn, nu are nici o tăietură de vârfuri, dar κ(Kn) = n – 1.
O tăietură de vertex pentru două vârfuri u și v este un set de vârfuri a căror eliminare din graf le deconectează pe u și v. Conectivitatea locală κ(u, v) este dimensiunea celei mai mici tăieturi de vertex care separă u și v. Conectivitatea locală este simetrică pentru grafurile nedirecționate; adică κ(u, v) = κ(v, u). Mai mult, cu excepția grafurilor complete, κ(G) este egală cu minimul lui κ(u, v) pe toate perechile neadiacente de vârfuri u, v.
Conectivitatea 2 se mai numește și biconectivitate, iar conectivitatea 3 se mai numește și triconectivitate. Un graf G care este conectat, dar care nu este 2-conectat se numește uneori separabil.
Concepte analoge pot fi definite pentru muchii. În cazul simplu în care tăierea unei singure muchii specifice ar deconecta graful, acea muchie se numește punte. Mai general, o tăietură de muchie a lui G este un set de muchii a căror eliminare face ca graful să fie deconectat. Conectivitatea marginilor λ(G) este dimensiunea celei mai mici tăieturi de muchii, iar conectivitatea locală a marginilor λ(u, v) a două vârfuri u, v este dimensiunea celei mai mici tăieturi de muchii care deconectează u de v. Din nou, conectivitatea locală a marginilor este simetrică. Un graf se numește k-conectivitate pe muchii dacă conectivitatea pe muchii este k sau mai mare.
Se spune că un graf este conectat la maxim dacă conectivitatea sa este egală cu gradul său minim. Un graf se spune că este maxim-conectat pe muchii dacă conectivitatea sa pe muchii este egală cu gradul său minim.
Super- și hiper-conectivitateEdit
Un graf se spune că este super-conectat sau super-κ dacă fiecare tăietură minimă de vertex izolează un vertex. Se spune că un graf este hiperconectat sau hiper-κ dacă ștergerea fiecărei tăieturi minime de vertexuri creează exact două componente, dintre care una este un vertex izolat. Un graf este semi-hiper-conectat sau semi-hiper-κ dacă orice tăietură minimă de vertex separă graful în exact două componente.
Mai precis: un graf conex G se spune că este super-conectat sau super-κ dacă toate tăieturile minime de vertex constau din verticele adiacente cu un singur vertex (de grad minim).Un graf conex G se spune că este super-conectat pe muchii sau super-λ dacă toate tăieturile minime pe muchii constau din muchii incidente cu un vertex (de grad minim).
Un set de tăieturi X din G se numește un set de tăieturi netrivial dacă X nu conține vecinătatea N(u) a niciunui vertex u ∉ X. Atunci superconectivitatea κ1 a lui G este:
κ1(G) = min{|X| : X este un set de tăieturi netrivial}.
Un tăietor de muchii non-trivial și superconectivitatea de muchii λ1(G) se definesc în mod analogic.
