Reunasuuntainen k-kytkentäinen graafi

K -reunaan yhdistetty graafi on graafi , joka pysyy yhdistettynä useimpien reunojen poistamisen jälkeen. $k-1$

Usein k -reuna- yhdistetyn graafin sijasta sanotaan k -kytketty graafi.

Muodollinen määritelmä

Olkoon mikä tahansa kaavio. Jos kytketty kaikille , niin sitä kutsutaan k -edge kytkettynä. $G=(V,E)$ $G^\prime = (V, E \setminus X)$ $X \subseteq E$ $|X| < k$ $G$

Muistiinpanot

Jos kuvaaja on k -edge- kytketty, niin se on myös m -edge- kytketty kaikille m < k .
Yhdistetty graafi on sama kuin 1-reunainen graafi.

Ominaisuudet

K - reunaan yhdistetyn graafin pisteiden minimiaste on vähintään k .
Kriittinen graafi , jonka kromaattinen luku > k on k -edge- kytketty.

Laskenta

On olemassa aikapolynomi-algoritmi suurimman k :n määrittämiseksi , jonka graafi G on k -reunakytketty. Yksinkertaisena algoritmina voidaan käyttää seuraavaa: mille tahansa kärkiparille (u, v) määritetään maksimivirtaus u :sta v : hen, jonka kaikkien reunojen kapasiteetti on yhtä suuri molempiin suuntiin. Graafi on k -reunakytketty silloin ja vain, jos maksimivirtaus u :sta v :iin on vähintään k millä tahansa parilla (u, v) . Siten k on pienin uv - virtaus kaikkien parien (u, v) joukossa .

Jos n on graafin kärkien lukumäärä, tämä yksinkertainen algoritmi suoritetaan maksimivirtausalgoritmin iteraatioina, mikä puolestaan ratkaisee ongelman virtauksen löytämisestä ajassa . Siten algoritmin kokonaismonimutkaisuus on . $O(n^{2})$ $O(n^{3})$ $O(n^5)$

Parannettu algoritmi ratkaisee maksimivirtausongelman mille tahansa parille (u, v), jossa u on mielivaltainen kiinteä kärkipiste ja v kulkee kaikkien jäljellä olevien kärkien läpi. Tämä algoritmi vähentää monimutkaisuutta arvoon . Jos leikkaus on pienempi kuin k , se erottaa u :n jostakin toisesta kärjestä. Voit parantaa algoritmia, jos käytät Gabov-algoritmia , ajassa [1] . $O(n^{4})$ $O(n^{3})$

Tähän liittyvä ongelma, graafin G minimaalisen k - reunaan kytketyn aligraafin löytäminen (eli valita G :stä mahdollisimman vähän reunoja, jotka muodostavat k - reunaan yhdistetyn aligraafin) on NP-kova [2] . $k\geq 2$

Katso myös

Muistiinpanot

↑ Harold N. Gabow. Matroidinen lähestymistapa reunaliitettävyyden löytämiseen ja arboresenssien pakkaamiseen. J Comput. Syst. sci. , 50(2):259–273, 1995.
↑ MR Garey ja DS Johnson. Tietokoneet ja hallitsemattomuus: opas NP-täydellisyyden teoriaan . Freeman, San Francisco, CA, 1979.