Minimální řez - Minimum cut
v teorie grafů, a minimální řez nebo min. řez a graf je střih (A rozdělit grafů do dvou disjunktních podmnožin), což je v určitém smyslu minimální.
Variace problému s minimálním řezem berou v úvahu vážené grafy, směrované grafy, terminály a rozdělení vrcholů do více než dvou sad.
Vážený problém min-cut umožňující pozitivní i negativní váhy lze triviálně transformovat na vážený maximální řez překlopením cedule ve všech vahách.
Bez koncových uzlů
Minimální problém se snížením v neorientovaný, vážené grafy lze vyřešit v polynomiálním čase pomocí Stoer-Wagnerův algoritmus. Ve zvláštním případě, když je graf nevážený, Kargerův algoritmus poskytuje efektivní randomizovanou metodu pro nalezení řezu. V tomto případě se minimální řez rovná okrajová konektivita grafu.
Zobecněním problému minimálního řezu bez terminálů je minimální k-střih, ve kterém je cílem rozdělit graf alespoň na k připojených komponent odstraněním co nejméně hran. Pro pevnou hodnotu k, tento problém lze vyřešit v polynomiálním čase, ačkoli algoritmus není praktický pro velké k. [2]
S koncovými uzly
Pokud jsou uvedeny dva terminální uzly, obvykle se označují jako zdroj a dřez. V cíleném, váženém toková síť, minimální řez odděluje vrcholy zdroje a dřezu a minimalizuje celkovou váhu okrajů, které jsou směrovány ze zdrojové strany řezu na potápěčskou stranu řezu. Jak je uvedeno v věta o maximálním toku o minimálním řezu, váha tohoto řezu se rovná maximálnímu množství toku, které lze odeslat ze zdroje do jímky v dané síti.
Ve vážené, neorientované síti je možné vypočítat řez, který odděluje určitý pár vrcholů od sebe navzájem a má minimální možnou váhu. Systém řezů, který řeší tento problém pro každou možnou dvojici vrcholů, lze shromáždit do struktury známé jako Gomory tree 滴 u strom grafu.
Zobecněním problému minimálního řezu u terminálů je k-terminální řez nebo multiterminální řez. Tento problém je NP-tvrdé, dokonce pro .[3]
Aplikace
Grafický oddíl problémy jsou rodinou kombinačních optimalizačních problémů, ve kterých má být graf rozdělen na dvě nebo více částí s dalšími omezeními, jako je vyvážení velikostí obou stran řezu. Kategorizace objektů na základě segmentace lze považovat za specifický případ normalizovaného min. řezu spektrální shlukování aplikován na segmentace obrazu.
Kvůli věta o maximálním toku o minimálním řezu, Minimální hodnota řezu 2 uzlů se rovná jejich maxflow hodnota. V tomto případě lze k vyřešení této otázky použít i některé algoritmy použité v problému maxflow.
Počet minimálních řezů
Graf s vrcholy mohou nanejvýš mít výrazné minimální řezy. Tato vazba je těsná v tom smyslu, že a (jednoduchý) cyklus na vrcholy má přesně minimální řezy.
Viz také
- Maximální řez
- Oddělovač vrcholů, analogický koncept minimálních řezů pro vrcholy místo hran
Reference
- ^ „Algoritmy 4minutového řezu“.
- ^ „Polynomiální algoritmus pro problém k-cut pro pevné k“. Citovat deník vyžaduje
| deník =
(Pomoc) - ^ „Složitost multiterminálních řezů“ (PDF). Citovat deník vyžaduje
| deník =
(Pomoc)
Pokud interní odkaz nesprávně vás sem přivedl, možná budete chtít změnit odkaz tak, aby odkazoval přímo na zamýšlený článek. | Tento článek obsahuje seznam souvisejících položek, které mají stejný název (nebo podobné názvy).