Okrajově k-souvislý graf

K -edge -connected graf je graf , který zůstane souvislý i po odstranění většiny hran. $k-1$

Často se místo k -spojeného grafu říká k -souvislý graf.

Formální definice

Nechť je libovolný graf. Pokud je připojeno pro všechny pro , pak se nazývá k -edge spojené. $G=(V,E)$ $G^\prime = (V, E \setminus X)$ $X \subseteq E$ $|X| <k$ $G$

Poznámky

Pokud je graf k -hranně- souvislý, pak je také m -hranně- souvislý pro všechna m < k .
Souvislý graf je stejný jako graf s 1 hranou.

Vlastnosti

Minimální stupeň vrcholů k -hranně spojeného grafu je alespoň k .
Kritický graf s chromatickým číslem > k je k -hranně souvislý.

Výpočet

Existuje časově-polynomiální algoritmus pro určení největšího k , pro který je graf G k -hranně spojen. Jako jednoduchý algoritmus můžeme použít následující: pro libovolnou dvojici vrcholů (u, v) určíme maximální tok z u do v s kapacitou všech hran rovnou jedné v obou směrech. Graf je k -hranně propojený právě tehdy, když maximální tok z u do v je alespoň k pro libovolný pár (u, v) . K je tedy nejmenší tok UV ze všech párů (u, v) .

Jestliže n je počet vrcholů v grafu, tento jednoduchý algoritmus běží v iteracích algoritmu maximálního toku, což zase řeší problém nalezení toku v čase . Celková složitost algoritmu je tedy . $O(n^{2})$ $O(n^{3})$ $O(n^5)$

Vylepšený algoritmus řeší problém maximálního toku pro jakýkoli pár (u, v), kde u je libovolný pevný vrchol a v prochází všemi zbývajícími vrcholy. Tento algoritmus snižuje složitost na . Pokud existuje řez menší než k , odděluje u od nějakého jiného vrcholu. Algoritmus můžete vylepšit, pokud použijete Gabovův algoritmus , běžící v čase [1] . $O(n^{4})$ $O(n^{3})$

Související problém, nalezení minimálního k -hranově spojeného podgrafu grafu G (tj. výběr co nejméně hran z G , které tvoří k -hranem spojený podgraf) je NP-těžký pro [2] . $k\geq 2$

Viz také

Poznámky

↑ Harold N. Gabow. Matroidní přístup k nalezení okrajové konektivity a balení stromořadí. J Výpočet. Syst. sci. , 50(2):259-273,1995.
↑ MR Garey a DS Johnson. Počítače a neovladatelnost: Průvodce teorií NP-úplnosti . Freeman, San Francisco, CA, 1979.