Klipp (grafteori)
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 11 augusti 2021; kontroller kräver 2 redigeringar .Ett grafklipp i flödesproblem är ett par vertexuppsättningar (S,T) sådana att
- , var är uppsättningen av grafens hörn
- , var är källan, är avloppet.
Storleken på snittet är summan av kapaciteten hos sådana kanter som .
Andra definitioner av ett snitt (sektion) av en graf
- En grafklippning är en uppsättning kanter som bildar en tvådelad subgraf , vars borttagning delar upp grafen i två eller flera komponenter, som i synnerhet kan vara isolerade noder. Samt en linje som går genom alla kanter av grafens snitt.
Egenskaper
- Sektionslinjer kan korsa ett godtyckligt antal kanter och ackord.
- För att erhålla huvudsektionen av grafen är det nödvändigt att rita sektionslinjen i grafen på ett sådant sätt att den endast skär en gren av grafen vid en godtycklig skärningspunkt av ackord.