Nejmenší řez

Nejmenší řez grafu je řez , který je v určitém smyslu minimální ( rozdělení vrcholů grafu na dvě neprotínající se spojené množiny).

Variace

Nejmenší varianty střihu:

• Řez s minimálním počtem hran mezi všemi řezy daného rozdělení grafu na dvě spojené komponenty. Takové řezy generují vektorový prostor řezů grafu .
• Řez s minimálním počtem hran ze všech řezů v neorientovaném grafu . Takový řez určuje okrajovou konektivitu grafu. Kargerův algoritmus poskytuje účinnou randomizovanou metodu pro nalezení takového řezu.
• Nejmenší problém v neorientovaných vážených grafech lze vyřešit Stöhr-Wagnerovým algoritmem .
• Zobecnění neváženého a neřízeného nejmenšího řezu, nejmenšího k -řezu , jehož cílem je rozdělit graf na alespoň k spojených komponent odstraněním co nejméně hran.
• Rozdělení grafu , rodina kombinatorických optimalizačních problémů, ve kterých je graf rozdělen na dvě nebo více částí, s další podmínkou vyvážení rozměrů řezu.
• Průtokový řez , který odděluje zdroj od dřezu a minimalizuje celkovou hmotnost oblouků směřujících z části obsahující zdroj k části obsahující dřez. Jak ukazuje Ford-Fulkersonův teorém , váha takového řezu se rovná maximálnímu průtoku, který může projít od zdroje k jímce danou sítí. Alternativně lze tuto variaci problému vyřešit pomocí Kargerova algoritmu .
• Řez vážené neorientované sítě, která odděluje vybranou dvojici vrcholů a má minimální váhu. Řezný systém, který řeší problém pro libovolný pár vrcholů, lze sestavit do struktury známé jako Gomory-Hu strom .

Počet nejmenších řezů

Graf s n vrcholy může mít nanejvýš zřetelné nejmenší řezy.

Viz také

• Řez (teorie grafů) .
• Maximální řez grafu , který obsahuje maximální možný počet hran
• Oddělovač vrcholů , podobný koncept, ale odstraňují se vrcholy, nikoli hrany

Poznámky

1. ↑ 4 Min-Cut Algoritmy . Získáno 19. června 2017. Archivováno z originálu 5. srpna 2016. (neurčitý)

Literatura