Un componente connesso è un massimo sottografo connesso di un grafo indiretto. Ogni vertice appartiene esattamente a una componente connessa, così come ogni bordo. Un grafo è connesso se e solo se ha esattamente una componente connessa.
Le componenti forti sono i massimi sottografi fortemente connessi di un grafo diretto.
Un taglio di vertice o insieme di separazione di un grafo connesso G è un insieme di vertici la cui rimozione rende G disconnesso. La connettività dei vertici κ(G) (dove G non è un grafo completo) è la dimensione di un taglio minimo dei vertici. Un grafo è detto k-vertex-connected o k-connesso se la sua connettività dei vertici è k o maggiore.
Più precisamente, qualsiasi grafo G (completo o no) si dice k-vertex-connected se contiene almeno k+1 vertici, ma non contiene un insieme di k – 1 vertici la cui rimozione disconnette il grafico; e κ(G) è definito come il più grande k tale che G è k-connesso. In particolare, un grafo completo con n vertici, denotato Kn, non ha tagli di vertici, ma κ(Kn) = n – 1.
Un taglio di vertice per due vertici u e v è un insieme di vertici la cui rimozione dal grafo disconnette u e v. La connettività locale κ(u, v) è la dimensione del più piccolo taglio di vertice che separa u e v. La connettività locale è simmetrica per i grafi indiretti; cioè, κ(u, v) = κ(v, u). Inoltre, tranne che per i grafi completi, κ(G) è uguale al minimo di κ(u, v) su tutte le coppie non adiacenti di vertici u, v.
La connettività 2 è detta anche biconnettività e la connettività 3 è detta anche triconnettività. Un grafo G che è connesso ma non è 2-connesso è talvolta chiamato separabile.
Concetti analoghi possono essere definiti per i bordi. Nel caso semplice in cui il taglio di un singolo e specifico bordo disconnetterebbe il grafo, quel bordo è chiamato ponte. Più in generale, un bordo tagliato di G è un insieme di bordi la cui rimozione rende il grafico disconnesso. La connettività dei bordi λ(G) è la dimensione di un taglio di bordo più piccolo, e la connettività locale dei bordi λ(u, v) di due vertici u, v è la dimensione di un taglio di bordo più piccolo che disconnette u da v. Di nuovo, la connettività locale dei bordi è simmetrica. Un grafico è detto k-edge-connected se la sua connettività dei bordi è k o maggiore.
Un grafico si dice massimamente connesso se la sua connettività è uguale al suo grado minimo. Un grafico si dice massimamente connesso se la sua connettività ai bordi è uguale al suo grado minimo.
Super- e iper-connettivitàModifica
Un grafico si dice super-connesso o super-κ se ogni taglio minimo dei vertici isola un vertice. Un grafo si dice iperconnesso o iper-κ se la cancellazione di ogni taglio minimo di vertice crea esattamente due componenti, uno dei quali è un vertice isolato. Un grafo è semi-iperconnesso o semi-iper-κ se ogni taglio di vertice minimo separa il grafo esattamente in due componenti.
Più precisamente: un grafo connesso G si dice superconnesso o super-κ se tutti i tagli di vertice minimi sono costituiti dai vertici adiacenti con un vertice (di grado minimo).Un grafo connesso G si dice super-connesso o super-λ se tutti i tagli di bordo minimi consistono nei bordi incidenti su qualche vertice (di grado minimo).
Un insieme di tagli X di G è detto un insieme di tagli non banale se X non contiene il quartiere N(u) di qualsiasi vertice u ∉ X. Allora la superconnettività κ1 di G è:
κ1(G) = min{|X| : X è un insieme di tagli non banale}.
Un taglio di bordo non banale e la superconnettività di bordo λ1(G) sono definiti in modo analogo.
