Legkisebb vágás
Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. július 18-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .A gráf legkisebb vágása az a vágás , amely bizonyos értelemben minimális ( a gráf csúcsainak felosztása két nem metsző összefüggő halmazra).
Változatok
A legkisebb vágási változatok:
- A gráf adott partíciójának két összefüggő komponensre vágott vágása a minimális számú éllel. Az ilyen vágások a gráfvágások vektorterét generálják .
- Az irányítatlan gráf összes vágása között a minimális élszámú vágás . Egy ilyen vágás határozza meg a gráf élösszeköthetőségét. A Karger-algoritmus hatékony véletlenszerű módszert biztosít egy ilyen vágás megtalálására.
- Az irányítatlan súlyozott gráfok legkevésbé vágott problémája a Stöhr-Wagner algoritmussal oldható meg .
- A súlyozatlan és irányítatlan legkisebb vágás, a legkisebb k -vágás általánosítása , amelynek célja a gráf legalább k összefüggő komponensre történő felosztása a lehető legkevesebb él eltávolításával.
- Grafikonparticionálás , kombinatorikus optimalizálási problémák családja, amelyben a gráf két vagy több részre van felosztva, azzal a további feltétellel, hogy kiegyensúlyozza a vágás méreteit.
- Az áramlási vágás , amely elválasztja a forrást a mosogatótól, és minimalizálja a forrást tartalmazó részről a mosogatót tartalmazó részre irányított ívek össztömegét. Amint a Ford-Fulkerson-tétel mutatja , egy ilyen vágás súlya megegyezik azzal a maximális áramlással, amely egy adott hálózaton keresztül a forrástól a nyelőig továbbítható. Alternatív megoldásként a probléma ezen változata a Karger algoritmussal is megoldható .
- Súlyozott irányítatlan hálózat vágása, amely elválaszt egy kiválasztott csúcspárt és rendelkezik a minimális súllyal. Egy vágási rendszer, amely bármely csúcspárra megoldja a problémát, összeállítható gráf Gomory-Hu fájaként ismert szerkezetté .
A legkisebb vágások száma
Egy n csúcsú gráfnak legfeljebb különálló legkisebb vágásai lehetnek.
Lásd még
- Vágás (gráfelmélet) .
- Egy gráf maximális vágása, amely a lehető legtöbb élt tartalmazza
- Vertex szeparátor , hasonló fogalom, de a csúcsokat távolítják el, nem az éleket
Jegyzetek
- ↑ 4 Min-Cut algoritmus . Letöltve: 2017. június 19. Az eredetiből archiválva : 2016. augusztus 5..