Kantmässigt k-ansluten graf

En k -kantsansluten graf är en graf som förblir ansluten efter att de flesta kanterna tagits bort. $k-1$

Ofta säger man istället för en k -kantsansluten graf en k -ansluten graf.

Formell definition

Låt vara vilken graf som helst. Om det är anslutet för alla för , så kallas det k - kant ansluten. $G=(V,E)$ $G^\prime = (V, E \setminus X)$ $X \subseteq E$ $|X| <k$ $G$

Anteckningar

Om en graf är k -kantsansluten så är den också m -kantansluten för alla m < k .
En ansluten graf är samma som en 1-kants ansluten graf.

Egenskaper

Den minsta graden av hörn för en k -kantsbunden graf är minst k .
En kritisk graf med kromatiskt tal > k är k -kantansluten .

Beräkning

Det finns en tidspolynomalgoritm för att bestämma den största k för vilken grafen G är k -kantansluten. Som en enkel algoritm kan vi använda följande: för vilket par av hörn som helst (u, v) bestämmer vi det maximala flödet från u till v med kapaciteten för alla kanter lika med en i båda riktningarna. En graf är k -kantkopplad om och endast om det maximala flödet från u till v är minst k för något par (u, v) . K är alltså det minsta uv- flödet bland alla par (u, v) .

Om n är antalet hörn i grafen, körs denna enkla algoritm i iterationer av maximiflödesalgoritmen, vilket i sin tur löser problemet med att hitta flödet i tid . Sålunda är den övergripande komplexiteten för algoritmen . $O(n^{2})$ $O(n^{3})$ $O(n^5)$

Den förbättrade algoritmen löser det maximala flödesproblemet för vilket par som helst (u, v) där u är en godtycklig fast vertex och v går genom alla återstående hörn. Denna algoritm reducerar komplexiteten till . Om det finns ett snitt som är mindre än k skiljer det u från någon annan vertex. Du kan förbättra algoritmen om du använder Gabov-algoritmen , som körs i tid [1] . $O(n^{4})$ $O(n^{3})$

Ett relaterat problem, att hitta en minimal k -kantsbunden subgraf av en graf G (det vill säga att välja så få kanter som möjligt från G som bildar en k -kantsansluten subgraf) är NP-svårt för [2] . $k\geq 2$

Se även

Anteckningar

↑ Harold N. Gabow. En matroid metod för att hitta kantanslutningar och packa arborescenser. J Comput. Syst. sci. 50(2):259-273, 1995.
↑ MR Garey och DS Johnson. Datorer och svårhanterlighet: en guide till teorin om NP-fullständighet . Freeman, San Francisco, CA, 1979.