k- kant-ansluten graf - k-edge-connected graph
I grafteori , en ansluten graf är k -edge kopplade om det fortfarande är ansluten när färre än k kanter avlägsnas.
Den kant-anslutning av en kurva är den största k för vilken grafen är k -edge-ansluten.
Kantanslutning och uppräkning av k- kant-anslutna grafer studerades av Camille Jordan 1869.
Formell definition
Låt vara ett godtyckligt diagram. Om subgraf är ansluten för alla där , då G säga k -edge-ansluten. Kantanslutningen för är det maximala värdet k så att G är k- kantansluten. Den minsta set X vars borttagning kopplar G är en minimal snitt i G .
Kantanslutningsversionen av Mengers teorem ger en alternativ och likvärdig karaktärisering när det gäller kantseparerade banor i diagrammet. Om och endast om varje två hörn av G bildar ändpunkterna k vägar, inte två av som delar en kant med varandra, då G är k -edge-ansluten. I en riktning är detta enkelt: om ett system med banor som detta existerar, är varje uppsättning X med färre än k- kanter separerad från åtminstone en av banorna, och paret av hörnpunkter förblir anslutna till varandra även efter att X har raderats . I den andra riktningen kan förekomsten av ett system av banor för varje par av hörnpunkter i en graf som inte kan kopplas bort genom borttagning av få kanter bevisas med användning av maxflödet min-cut-satsen från teorin om nätverksflöden .
Relaterade begrepp
Minsta vertexgrad ger en trivial övre gräns för kantanslutning. Det vill säga om en graf är k -edge kopplade då är det nödvändigt att k ≤ δ ( G ), där δ ( G ) är det minimum av något av hörnen v ∈ V . Om du raderar alla kanter som inträffar i ett toppunkt, v , skulle det självklart kopplas bort v från diagrammet.
Kantanslutning är det dubbla konceptet för omkrets , längden på den kortaste cykeln i en graf, i den meningen att omkretsen av en plan graf är kantanslutningen för dess dubbla graf , och vice versa. Dessa begrepp förenas i matroidteorin genom matrodernas omkrets , storleken på den minsta beroende i matroiden. För en grafisk matroid är matroidomkretsen lika med omkretsen för den underliggande grafen, medan det för en samgrafisk matroid är lika med kantanslutningen.
De 2-kantsanslutna graferna kan också karaktäriseras av frånvaron av broar , av förekomsten av en sönderdelning av örat eller av Robbins sats enligt vilken dessa är exakt de grafer som har en stark orientering .
Beräkningsaspekter
Det finns en polynom-tidsalgoritm för att bestämma den största k för vilken en graf G är k- kantansluten. En enkel algoritm skulle för varje par (u, v) bestämma det maximala flödet från u till v med kapaciteten för alla kanter i G inställd på 1 för båda riktningarna. En graf är k- kantansluten om och endast om det maximala flödet från u till v är minst k för ett par (u, v) , så k är det minsta uv- flödet bland alla (u, v) .
Om n är antalet hörn i diagrammet, skulle denna enkla algoritm utföra iterationer av maximalt flödesproblem, vilket kan lösas i tid. Därför är komplexiteten hos den enkla algoritmen som beskrivs ovan totalt.
En förbättrad algoritm löser det maximala flödesproblemet för varje par (u, v) där u är godtyckligt fixerad medan v varierar över alla hörn. Detta minskar komplexiteten till och är ljud eftersom, om en nedskärning av kapacitet är mindre än k existerar, är den skyldig att separera u från någon annan vertex. Det kan förbättras ytterligare med en algoritm från Gabow som körs i värsta fall .
Karger – Stein-varianten av Kargers algoritm ger en snabbare randomiserad algoritm för att bestämma anslutningen med förväntad körtid .
Ett relaterat problem: att hitta det minsta k- kantanslutna spännande underbilden av G (det vill säga: välj så få som möjligt i G som ditt val är k- kantanslutet) är NP-svårt för .
