En forbundet komponent er en maksimalt forbundet undergraf af en ubestrøget graf. Hvert toppunkt tilhører præcis én forbundet komponent, og det samme gør hver kant. En graf er forbundet, hvis og kun hvis den har præcis én forbundet komponent.
De stærke komponenter er de maksimalt stærkt forbundne undergrafer af en rettet graf.
En vertex cut eller separationsmængde af en forbundet graf G er et sæt af vertices, hvis fjernelse gør G usammenhængende. Vertex-connectivity κ(G) (hvor G ikke er en komplet graf) er størrelsen af et minimalt vertex cut. En graf kaldes k-vertex-connected eller k-connected, hvis dens vertex-connectivity er k eller større.
Nærmere bestemt siges en graf G (komplet eller ej) at være k-vertex-connected, hvis den indeholder mindst k+1 vertices, men ikke indeholder et sæt af k – 1 vertices, hvis fjernelse af dem afbryder forbindelsen til grafen; og κ(G) er defineret som det største k, således at G er k-connected. En komplet graf med n toppunkter, benævnt Kn, har ingen toppunktsafsnit overhovedet, men κ(Kn) = n – 1.
En vertex cut for to vertices u og v er et sæt vertices, hvis fjernelse fra grafen afbryder forbindelsen mellem u og v. Den lokale konnektivitet κ(u, v) er størrelsen af den mindste vertex cut, der adskiller u og v. Den lokale konnektivitet er symmetrisk for udirigerede grafer, dvs. κ(u, v) = κ(v, u). Desuden er κ(G), undtagen for fuldstændige grafer, lig med minimum af κ(u, v) over alle ikke-tilstødende par af toppunkter u, v.
2-konnektivitet kaldes også bikonnektivitet og 3-konnektivitet kaldes også triconnektivitet. En graf G, der er forbundet, men ikke 2-tilsluttet, kaldes undertiden separabel.
Analoge begreber kan defineres for kanter. I det enkle tilfælde, hvor en enkelt, specifik kant, som skæres over, vil afbryde grafen, kaldes denne kant en bro. Mere generelt er en kantskæring af G et sæt af kanter, hvis fjernelse gør grafen usammenhængende. Kantforbindelsesgraden λ(G) er størrelsen af den mindste kantskæring, og den lokale kantforbindelsesgrad λ(u, v) for to hjørner u, v er størrelsen af den mindste kantskæring, der afbryder forbindelsen mellem u og v. Igen er den lokale kantforbindelsesgrad symmetrisk. En graf kaldes k-kantforbundet, hvis dens kantkonnektivitet er k eller større.
En graf siges at være maksimalt forbundet, hvis dens konnektivitet er lig med dens mindste grad. En graf siges at være maksimalt kantforbundet, hvis dens kantforbindelse er lig med dens minimumsgrad.
Super- og hyperforbindelseRediger
En graf siges at være superforbundet eller super-κ, hvis hvert minimumsvertikal snit isolerer et vertekst. En graf siges at være hyperkonnekteret eller hyper-κ, hvis sletningen af hvert minimum vertex cut skaber præcis to komponenter, hvoraf den ene er et isoleret vertex. En graf er semi-hyper-connected eller semi-hyper-κ, hvis ethvert minimum vertex-cut adskiller grafen i præcis to komponenter.
Mere præcist: En graf med G-forbindelser siges at være super-connected eller super-κ, hvis alle minimum vertex-cuts består af de vertices, der støder op til et (minimum-grad) vertex.En G-tilsluttet graf siges at være super-edge-connected eller super-λ, hvis alle minimum edge-cuts består af de kanter, der falder på et eller andet (minimum-grad) vertex.
En cutset X af G kaldes en ikke-triviel cutset, hvis X ikke indeholder naboskabet N(u) til et vertex u ∉ X. Så er superconnectivity κ1 af G:
κ1(G) = min{|X| : X er en ikke-triviel cutset}.
Et ikke-trivielt kant-snit og kant-superconnectivity λ1(G) defineres analogt.
