Kantmæssigt k-forbundet graf

En k -kantforbundet graf er en graf , der forbliver forbundet efter fjernelse ved de fleste kanter. $k-1$

Ofte siger man i stedet for en k -kantforbundet graf en k -forbundet graf.

Formel definition

Lad være en hvilken som helst graf. Hvis forbundet for alle for , så kaldes det k -kant forbundet. $G=(V,E)$ $G^\primtal = (V, E \setminus X)$ $X \subseteq E$ $|X| < k$ $G$

Noter

Hvis en graf er k -kantforbundet , så er den også m -kantforbundet for alle m < k .
En forbundet graf er det samme som en 1-kant-forbundet graf.

Egenskaber

Minimumsgraden af toppunkter for en k -kantforbundet graf er mindst k .
En kritisk graf med kromatisk tal > k er k -kantforbundet .

Beregning

Der er en tidspolynomiel algoritme til at bestemme den største k , for hvilken grafen G er k -kantforbundet. Som en simpel algoritme kan vi bruge følgende: for ethvert par af hjørner (u, v) bestemmer vi det maksimale flow fra u til v med kapaciteten af alle kanter lig med én i begge retninger. En graf er k -kantforbundet, hvis og kun hvis det maksimale flow fra u til v er mindst k for ethvert par (u, v) . K er således det mindste uv - flow blandt alle par (u, v) .

Hvis n er antallet af hjørner i grafen, kører denne simple algoritme i iterationer af den maksimale flowalgoritme, som igen løser problemet med at finde flowet i tid . Således er den overordnede kompleksitet af algoritmen . $O(n^{2})$ $O(n^{3})$ $O(n^5)$

Den forbedrede algoritme løser det maksimale flowproblem for ethvert par (u, v), hvor u er et vilkårligt fast toppunkt, og v løber gennem alle resterende hjørner. Denne algoritme reducerer kompleksiteten til . Hvis der er et snit mindre end k , adskiller det u fra et andet toppunkt. Du kan forbedre algoritmen, hvis du anvender Gabov-algoritmen , der kører i tid [1] . $O(n^{4})$ $O(n^{3})$

Et relateret problem, at finde en minimal k -kant-forbundet undergraf af en graf G (det vil sige at vælge så få kanter som muligt fra G , der danner en k -kant -forbundet undergraf), er NP-svært for [2] . $k\geq 2$

Se også

Noter

↑ Harold N. Gabow. En matroid tilgang til at finde kantforbindelser og pakning af arborescenser. J Comput. Syst. sci. , 50(2):259-273, 1995.
↑ MR Garey og DS Johnson. Computere og intraktabilitet: en guide til teorien om NP-fuldstændighed . Freeman, San Francisco, CA, 1979.