Een aangesloten component is een maximaal aangesloten subgraaf van een ongerichte grafiek. Elke vertex behoort tot precies één aangesloten component, net als elke edge. Een grafiek is verbonden als en slechts als hij precies één verbonden component heeft.
De sterk verbonden componenten zijn de maximaal sterk verbonden deelgrafieken van een gerichte grafiek.
Een vertex cut of scheidingsset van een verbonden grafiek G is een verzameling vertices waarvan verwijdering G ontkoppeld maakt. De vertexconnectiviteit κ(G) (waarbij G geen volledige grafiek is) is de grootte van een minimale vertexsnede. Een grafiek heet k-vertex-connected of k-connected als zijn vertex-connectiviteit k of groter is.
Preciezer gezegd, een grafiek G (compleet of niet) wordt k-vertex-connected genoemd als hij minstens k+1 hoekpunten bevat, maar geen verzameling van k – 1 hoekpunten bevat waarvan verwijdering de verbinding met de grafiek verbreekt; en κ(G) is gedefinieerd als de grootste k zodanig dat G k-connected is. In het bijzonder heeft een volledige grafiek met n hoekpunten, Kn genaamd, helemaal geen vertex cuts, maar κ(Kn) = n – 1.
Een vertex cut voor twee vertices u en v is een verzameling vertices waarvan de verwijdering uit de grafiek u en v van elkaar scheidt. De lokale connectiviteit κ(u, v) is de grootte van de kleinste vertex cut die u en v scheidt. De lokale connectiviteit is symmetrisch voor undirected graphs; dat wil zeggen, κ(u, v) = κ(v, u). Bovendien is, behalve voor complete grafen, κ(G) gelijk aan het minimum van κ(u, v) over alle niet-aangrenzende paren hoekpunten u, v.
2-connectiviteit wordt ook biconnectiviteit genoemd en 3-connectiviteit wordt ook triconnectiviteit genoemd. Een grafiek G die wel verbonden is, maar niet 2-verbonden, wordt soms scheidbaar genoemd.
Analoge begrippen kunnen worden gedefinieerd voor kanten. In het eenvoudige geval waarin het knippen van een enkele, specifieke rand de grafiek zou ontkoppelen, wordt die rand een brug genoemd. Meer in het algemeen is een randafsnijding van G een verzameling ribben waarvan de verwijdering tot gevolg heeft dat de verbinding met de grafiek verbroken wordt. De randverbondenheid λ(G) is de grootte van een kleinste randafsnijding, en de lokale randverbondenheid λ(u, v) van twee hoekpunten u, v is de grootte van een kleinste randafsnijding die u losmaakt van v. Ook hier geldt dat de lokale randverbondenheid symmetrisch is. Een grafiek heet k-edge-connectief als de randconnectiviteit k of groter is.
Een grafiek heet maximaal verbonden te zijn als de connectiviteit gelijk is aan de minimale graad. Men zegt dat een grafiek maximaal randverbonden is als de randverbondenheid gelijk is aan de minimale graad.
Super- en hyperverbondenheidEdit
Een grafiek heet super-verbonden of super-κ te zijn als elke minimale vertexsnede een vertex isoleert. Een grafiek is zogezegd hyper-verbonden of hyper-κ als het schrappen van elke minimale vertexcut precies twee componenten oplevert, waarvan er een een geïsoleerd vertex is. Een grafiek is half-hyper-verbonden of half-hyper-κ als elke minimale vertex-snede de grafiek in precies twee componenten verdeelt.
Preciezer: een G-verbonden grafiek heet super-verbonden of super-κ te zijn als alle minimale vertex-sneden bestaan uit de vertices die grenzen aan één (minimum-graad) vertex.Een G-verbonden grafiek heet super-edge-connected of super-λ als alle minimale edge-cuts bestaan uit de edges die aan een of andere (minimum-graad) vertex grenzen.
Een deelverzameling X van G heet een niet-triviale deelverzameling als X niet de buurt N(u) bevat van een vertex u ∉ X. Dan is de superconnectiviteit κ1 van G:
κ1(G) = min{|X| : X is een niet-triviale deelverzameling}.
Een niet-triviale randafsnijding en de rand-superconnectiviteit κ1(G) zijn analoog gedefinieerd.
