Minsta snittet
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 18 juli 2022; verifiering kräver 1 redigering .Det minsta snittet i en graf är ett snitt som är minimalt i någon mening ( en uppdelning av en grafs hörn i två sammankopplade uppsättningar som inte skär varandra).
Variationer
Minsta snittvariationer:
- Ett snitt med det minsta antalet kanter bland alla snitt av en given partition av grafen i två sammankopplade komponenter. Sådana snitt genererar ett vektorutrymme av grafsnitt .
- Ett snitt med det minsta antalet kanter bland alla snitt i en oriktad graf . Ett sådant snitt bestämmer grafens kantanslutningar . Kargers algoritm tillhandahåller en effektiv randomiserad metod för att hitta ett sådant snitt.
- Det minst skurna problemet i oriktade viktade grafer kan lösas med Stöhr-Wagner-algoritmen .
- En generalisering av det oviktade och oriktade minsta snittet, det minsta k -snittet , vars mål är att dela upp grafen i minst k anslutna komponenter genom att ta bort så få kanter som möjligt.
- Grafpartitionering , en familj av kombinatoriska optimeringsproblem där grafen är uppdelad i två eller flera delar, med det ytterligare villkoret att balansera snittets dimensioner.
- Flödesavsnittet , som skiljer källan från diskhon och minimerar den totala vikten av bågarna riktade från den del som innehåller källan till den del som innehåller diskhon. Som Ford-Fulkerson-satsen visar är vikten av ett sådant snitt lika med det maximala flödet som kan passeras från källan till sänkan genom ett givet nätverk. Alternativt kan denna variant av problemet lösas med hjälp av Karger-algoritmen .
- Ett snitt av ett vägt oriktat nätverk som separerar ett utvalt par av hörn och har den minsta vikten. Ett skärsystem som löser problemet för vilket par av hörn som helst kan sättas ihop till en struktur som kallas Gomory-Hu-trädet en graf.
Antal minsta snitt
En graf med n hörn kan ha högst distinkta minsta snitt.
Se även
- Klipp (grafteori) .
- Det maximala snittet av en graf som innehåller så många kanter som möjligt
- Vertex separator , ett liknande koncept, men hörn tas bort, inte kanter
Anteckningar
- ↑ 4 Min-Cut-algoritmer . Hämtad 19 juni 2017. Arkiverad från originalet 5 augusti 2016.