En sammanhängande komponent är en maximalt sammanhängande undergraf till en oriktad graf. Varje vertex tillhör exakt en ansluten komponent, liksom varje kant. En graf är ansluten om och endast om den har exakt en ansluten komponent.
De starka komponenterna är de maximalt starkt sammankopplade undergraferna till en riktad graf.
En vertex cut eller separationsmängd av en sammankopplad graf G är en mängd vertexar vars avlägsnande gör att G blir osammanhängande. Vertexkonnektiviteten κ(G) (där G inte är en komplett graf) är storleken på ett minimalt vertexsnitt. En graf kallas k-vertex-connected eller k-connected om dess vertexkonnektivitet är k eller större.
Enklare uttryckt sägs en graf G (fullständig eller inte) vara k-vertex-connected om den innehåller minst k+1 vertices, men inte innehåller en uppsättning av k – 1 vertices vars avlägsnande avbryter grafen, och κ(G) definieras som det största k som gör att G är k-connected. En fullständig graf med n hörn, benämnd Kn, har inga hörnskärningar alls, men κ(Kn) = n – 1.
Ett vertexsnitt för två noder u och v är en uppsättning noder vars avlägsnande från grafen kopplar bort u och v. Den lokala konnektiviteten κ(u, v) är storleken på det minsta vertexsnittet som separerar u och v. Den lokala konnektiviteten är symmetrisk för odirigerade grafer; det vill säga, κ(u, v) = κ(v, u). Dessutom är κ(G), utom för kompletta grafer, lika med minimum av κ(u, v) över alla icke angränsande par av hörn u, v.
2-konnektivitet kallas också bikonnektivitet och 3-konnektivitet kallas också trikonnektivitet. En graf G som är ansluten men inte 2-ansluten kallas ibland separerbar.
Analoga begrepp kan definieras för kanter. I det enkla fallet där det skulle koppla bort grafen genom att skära av en enskild, specifik kant, kallas denna kant för en bro. Mer allmänt är ett kantsnitt av G en uppsättning kanter vars avlägsnande gör grafen osammanhängande. Kantkonnektiviteten λ(G) är storleken på det minsta kantsnittet, och den lokala kantkonnektiviteten λ(u, v) för två hörn u, v är storleken på det minsta kantsnittet som kopplar bort u från v. Återigen är den lokala kantkonnektiviteten symmetrisk. En graf kallas k-kantkopplad om dess kantkopplingsförmåga är k eller större.
En graf sägs vara maximalt kopplad om dess kopplingsförmåga är lika med dess lägsta grad. En graf sägs vara maximalt kantansluten om dess kantanslutning är lika med dess lägsta grad.
Super- och hyperanslutningRedigera
En graf sägs vara superansluten eller super-κ om varje minsta vertexsnitt isolerar en vertex. En graf sägs vara hyperkonnekterad eller hyper-κ om borttagningen av varje minsta vertexsnitt skapar exakt två komponenter, varav en är en isolerad vertex. En graf är halvhyperkopplad eller halvhyper-κ om varje minsta vertexsnitt separerar grafen i exakt två komponenter.
Närmare bestämt: en G-ansluten graf sägs vara superkopplad eller super-κ om alla minsta vertexsnitt består av de vertexar som gränsar till en (av lägsta grad) vertex.En graf med G-anslutning sägs vara super-kantansluten eller super-λ om alla minimala kantskärningar består av de kanter som är intill en (minimigrad) topp.
En skärningsmängd X av G kallas en icke-trivial skärningsmängd om X inte innehåller grannskapet N(u) för någon topp u ∉ X. Då är superanslutningen κ1 av G:
κ1(G) = min{|X| : X är en icke-trivial skärningsmängd}.
En icke-trivial edge-cut och edge-superconnectivity λ1(G) definieras analogt.
