Klipp ut (grafteori) - Cut (graph theory)
I grafteori är ett snitt en partition av vertikorn på en graf i två sammanhängande delmängder . Varje klipp bestämmer en klippuppsättning , den uppsättning kanter som har ett slutpunkt i varje delmängd av partitionen. Dessa kanter sägs kryssa snittet. I en ansluten graf bestämmer varje klippuppsättning ett unikt snitt, och i vissa fall identifieras klipp med sina klippsatser snarare än med sina toppunktpartitioner.
I ett flödesnätverk är en s – t-klippning ett snitt som kräver att källan och diskbänken är i olika delmängder, och dess snittuppsättning består endast av kanter som går från källans sida till diskbänken. Den kapacitet av en s-t cut definieras som summan av kapaciteten för varje kant i cut-set .
Innehåll
Definition
Ett snitt är en partition av en graf i två delmängder S och T . Den cut-uppsättning av en skuren är den uppsättning av kanter som har en ändpunkt i S och den andra slutpunkten i T . Om s och t är specificerade hörn av grafen G , då en s - t cut är ett snitt, i vilken s hör till mängden S och t hör till mängden T .
I en oviktad, icke riktad graf är storleken eller vikten på ett snitt antalet kanter som korsar snittet. I en viktad graf , det värde eller vikt definieras av summan av vikterna av kanterna korsar snittet.
En bindning är en cut-set som inte har någon annan cut-set som en korrekt delmängd.
Minsta snitt
Ett snitt är minimalt om storleken eller vikten på snittet inte är större än storleken på något annat snitt. Bilden till höger visar ett minsta snitt: storleken på detta snitt är 2, och det finns inget snitt i storlek 1 eftersom grafen är bridgeless .
Den max-flöde, minsta-snitt visar att den maximala nätverksflöde och summan av de utskurna kantvikter av någon minsta snittet som separerar källan och sink är lika. Det finns polynom-tid metoder för att lösa min-cut-problemet, särskilt Edmonds – Karp algoritmen .
Maximal snitt
Ett snitt är maximalt om storleken på snittet inte är mindre än storleken på något annat snitt. Bilden till höger visar ett maximalt snitt: snittets storlek är lika med 5, och det finns inget snitt i storlek 6, eller | E | (antalet kanter), eftersom diagrammet inte är bipartit (det finns en udda cykel ).
Generellt sett är det svårt att hitta en maximal nedskärning. Max-cut-problemet är ett av Karps 21 NP-kompletta problem . Problemet med max-cut är också APX-hårt , vilket innebär att det inte finns något polynom-tid-approximationsschema för det om inte P = NP. Det kan emellertid approximeras till inom ett konstant approximationsförhållande med användning av halvbestämd programmering .
Observera att min-cut och max-cut inte är dubbla problem i linjär programmeringsmässig mening, även om man får från ett problem till ett annat genom att ändra min till max i objektfunktionen . Maxflödesproblemet är det dubbla av min-cut-problemet.
Sparsest snitt
Den glesaste cut Problemet är att bidelning hörn för att minimera förhållandet mellan antalet kanter över den skurna dividerat med antalet hörn i den mindre halv av skiljeväggen. Denna objektiva funktion gynnar lösningar som både är glesa (få kanter som korsar snittet) och balanserade (nära en halva). Problemet är känt för att vara NP-hårt, och den mest kända approximationsalgoritmen är en approximation på grund av Arora, Rao & Vazirani (2009) .
Skär utrymme
Familjen för alla klippuppsättningar i en riktad graf kallas grafens skärningsutrymme . Det bildar ett vektorutrymme över det tvåelementala finitfältet i aritmetisk modulo två, med den symmetriska skillnaden mellan två skurna uppsättningar som vektortillsatsoperation, och är det ortogonala komplementet till cykelutrymmet . Om kanterna på grafen ges positiva vikter, minimivikten basis kan av den skurna utrymmet att beskrivas genom ett träd på samma vertex uppsättning som grafen, kallad Gomory-Hu träd . Varje kant på detta träd är förknippat med en bindning i den ursprungliga grafen, och minsta skärning mellan två noder s och t är den minsta viktbindningen bland de som är associerade med vägen från s till t i trädet.