det minimale nedskæringsproblem

minimumskåret problem er et grundlæggende problem i grafteori og kombinatorisk optimering. Givet en graf (enten rettet eller ikke -rettet) med kapaciteter, der er tildelt dens kanter, og to udpegede vertikater, en kilde (er) og en vask (T), er problemet at finde et sæt kanter, hvis fjernelse afbryder kilden fra vasken og minimerer summen af ​​kapaciteten i disse kanter.

Med andre ord, en klip I en graf er en partition af vertikaterne i to disponible sæt, s og t, således at kilden * s * hører til s og vasken * t * hører til T. kapaciteten i klippet er summen af ​​kapaciteten på kanterne, der går fra et toppunkt i S til et toppunkt i T. Det minimale snitproblem sigter mod at finde udskæringen med den mindste kapacitet.

Formelt:

* input:

* En graf g =(v, e), hvor v er sæt af vertikater, og e er sæt kanter.

* En kapacitetsfunktion C:E -> R+ tildeling af en ikke -negativ kapacitet til hver kant.

* En kilde Vertex s ∈ V.

* En vask af vasken t ∈ V.

* output:

* En partition (s, t) af V, således at s ∈ S, t ∈ T, og kapaciteten af ​​klippet c (s, t) =σ c (u, v) (hvor u ∈ S og v ∈ T) minimeres.

Eksempel:

Forestil dig et vejnet, hvor hver vej har en vis trafikkapacitet. Du vil finde det mindste sæt veje, du har brug for for at lukke (klippet) for fuldstændigt at forhindre trafik i at flyde fra en by 's' til en by 't'. Den samlede kapacitet for disse lukkede veje repræsenterer omkostningerne ved nedskæringen, og du leder efter det billigste (minimumskapacitet) sæt af vejlukninger.

Hvordan minimumsskæring bruges i netværksstrømoptimering (Max-Flow Min-Cut-sætningen)

Forbindelsen mellem det minimale nedskæringsproblem og netværksstrømningsoptimering er dybtgående og fanget af max-flow min-cut teorem . Dette sætning siger, at:

Den maksimale strømningsmængde, der kan sendes fra kilden til vasken i et netværk, er lig med kapaciteten i det minimale nedskæring, der adskiller kilden og vasken.

Sådan spiller det ud:

1. Netværksstrømningsproblem: Netværksstrømningsproblemet sigter mod at finde den maksimale mængde "flow" (f.eks. Data, væske, elektricitet), der kan sendes fra kilden til vasken, underlagt kapacitetsbegrænsningerne i kanterne.

2. Find den maksimale strømning: Algoritmer som Ford-Fulkerson eller Edmonds-Karp bruges til at finde den maksimale strømning i netværket.

3. Max-flow min-cut-sætningen fortæller os, at når vi først har fundet den maksimale strømning, er værdien af ​​denne strømning * kapaciteten i det minimale nedskæring.

4. Find det minimale nedskæring: Selvom vi kan udlede kapaciteten for det minimale nedskæring fra den maksimale strømning, vil vi ofte vide *, hvilke kanter * udgør minimumsskæringen. Dette kan findes ved at se på den resterende graf efter at have kørt en max-flow-algoritme:

* Rest graf: Den resterende graf er en graf, der stammer fra den originale graf, der viser den resterende kapacitet, der er tilgængelig i hver kant (eller evnen til at "fortryde" flow langs en kant).

* Identificering af minimumskåret: Efter at have fundet den maksimale strømning, skal du udføre en rækkeviddeanalyse på den resterende graf, der starter fra kilden. Alle vertikater, der kan nås fra kilden i den resterende graf, hører til sættets 's' af minimumskæring. Alle andre hjørner hører til sættet 'T'. Kanterne, der krydser fra 's' til 't' i * original * -grafen, udgør minimumsskæringen.

Kortfattet:

* Du løser det maksimale strømningsproblem.

* Værdien af ​​den maksimale strømning er lig med kapaciteten på det minimale nedskæring (Max-Flow Min-Cut-sætning).

* Ved at analysere den resterende graf efter beregning af den maksimale strømning kan du identificere de specifikke kanter, der danner minimumskæring.

Hvorfor er dette nyttigt?

* Bestemmelse af flaskehalse: Den minimale nedskæring identificerer flaskehalse i et netværk. Dette er kanterne, der, når de fjernes, mest alvorligt begrænser strømmen fra kilde til synk.

* Ressourcefordeling: At forstå minimumskæringen hjælper med effektiv ressourcetildeling. Du kan fokusere på at forstærke kanterne i minimumsskæringen for at forbedre den samlede netværkskapacitet.

* netværkspartitionering: Det minimale nedskæring kan bruges til at opdele et netværk i to svagt forbundne komponenter. Dette kan være nyttigt i klyngeproblemer eller identificere grupper af noder, der er relativt uafhængige af hinanden.

* Løsning af andre problemer: Det minimale nedskæringsproblem har applikationer inden for forskellige områder, herunder billedsegmentering, datamining og projektplanlægning. Mange af disse problemer kan modelleres som netværksstrømningsproblemer og løst ved hjælp af Max-Flow Min-Cut-sætningen.

Eksempelbrug i et scenarie:

Forestil dig et strømnettet, der distribuerer elektricitet fra et kraftværk (kilde) til en by (Sink). Linjerne har forskellige kapaciteter. Hvis vi beregner minimumsskæringen mellem kraftværket og byen, kan vi:

1.

2. Identificer de mest sårbare linjer (kanterne i min -udskæringen), der, hvis den er beskadiget eller overbelastet, ville have alvorligt indflydelse på elforsyningen til byen.

3.

Afslutningsvis giver det minimale nedskæringsproblem, der er forbundet med Max-Flow Min-Cut-sætningen til netværksstrømningsoptimering, et kraftfuldt værktøj til at analysere og forbedre effektiviteten og robustheden af ​​forskellige netværkssystemer.