Cederbaumova věta o maximálním toku - Cederbaums maximum flow theorem - Wikipedia

Cederbaumova věta^[1] definuje hypotetické analogové elektrické sítě, které automaticky vytvoří řešení minimální problém s řezem. Alternativně, simulace takové sítě také vyprodukuje řešení problému minimálního střihu. Tento článek poskytuje základní definice, tvrzení věty a důkaz věty. Prezentace v tomto článku úzce navazuje na prezentaci věty v původní publikaci.

Definice

Definice v tomto článku jsou ve všech ohledech konzistentní s definicemi uvedenými v diskusi o věta o maximálním průtoku o minimálním řezu.

Vývojový graf

Cederbaumova věta platí pro konkrétní typ řízeného grafu: $G = (PROTI, E)$ . PROTI je sada uzlů. ${ displaystyle E}$ je sada směrovaných hran: ${ displaystyle E = (a, b) v V krát V}$ Kladná váha je spojena s každou hranou: $w ab : E \to R +$ . Dva z uzlů musí být s a t: ${ displaystyle s ve V}$ a ${ displaystyle t ve V}$ .

Tok

Tok, $F : E \to R +$ , je kladná veličina spojená s každou hranou v grafu. Tok je omezen váhou přidružené hrany a ochranou toku v každém vrcholu, jak je popsáno tady.

Proud

Hrana pár.

Aktuální je definováno jako mapa pro každý pár hran k reálná čísla, $i ab : E p \to R$ . Aktuální mapy od napětí po rozsah, který je určen váhami příslušných předních a zpětných hran. Každý pár hran je n-tice skládající se z přední a zadní hrany pro danou dvojici vrcholů. Proud v dopředném a zpětném směru mezi dvojicí uzlů jsou aditivní inverze navzájem: $i ab = - i ba$ . Proud je zachován v každém vnitřním uzlu v síti. Čistý proud na ${ displaystyle s}$ a ${ displaystyle t}$ uzly je nenulová. Čistý proud na ${ displaystyle s}$ uzel je definován jako vstupní proud. Pro množinu sousedů uzlu ${ displaystyle s}$ , ${ displaystyle N_ {s}}$ :

{ displaystyle I_ {in} = součet _ {b v N_ {s}} i_ {sb}}

Napětí

Napětí je definováno jako mapování ze sady párů hran na reálná čísla, $proti ab : E p \to R$ . Napětí je přímo analogické s elektrickým napětím v elektrické síti. Napětí v dopředném a zpětném směru mezi dvojicí uzlů jsou aditivní inverze navzájem: $proti ab = - proti ba$ . Vstupní napětí je součet napětí na množině hran, ${ displaystyle P_ {ab}}$ , které tvoří cestu mezi ${ displaystyle s}$ a ${ displaystyle t}$ uzly.

{ displaystyle V_ {in} = součet _ {(a, b) v P_ {ab}} v_ {ab}}

s–t střih

Minimální řez s – t pro směrovaný graf. Všechny hrany mají stejnou hmotnost.

An s – t řez je rozdělení grafu na dvě části, z nichž každá obsahuje jednu z nich ${ displaystyle s}$ nebo ${ displaystyle t}$ . Kde ${ displaystyle S cup T = V}$ , ${ displaystyle ; ; s v S}$ , ${ displaystyle ; ; t v T}$ , s – t řez je ${ displaystyle (S, T)}$ . Sada s – t cut je sada hran, které začínají v ${ displaystyle S}$ a končí v ${ displaystyle T}$ . Minimální řez s – t je řez s – t, jehož sada řezů má minimální hmotnost. Formálně je sada řezů definována jako:

{ displaystyle X_ {C} = {(a, b) v E mid a v S, b v T }}

Elektrická síť

Elektrická síť je model, který je odvozen z vývojového grafu. Každý odporový prvek v elektrické síti odpovídá dvojici hran v průtokovém grafu. Kladné a záporné vývody elektrické sítě jsou uzly odpovídající ${ displaystyle s}$ a ${ displaystyle t}$ terminály grafu. Stav napětí modelu se stává binárním v limitu, jak se blíží rozdíl vstupního napětí ${ displaystyle infty}$ . Chování elektrické sítě je definováno Kirchhoffovými zákony o napětí a proudu. Napětí se zvyšuje na nulu kolem všech uzavřených smyček a proudy se zvyšují na nulu na všech uzlech.

Odporový prvek

Odporový prvek v kontextu této věty je složka elektrické sítě, která odpovídá dvojici hran v průtokovém grafu.

iv charakteristický

{ displaystyle iv}

charakteristický.

The ${ displaystyle iv}$ charakteristika je vztah mezi proudem a napětím. Požadavky jsou:

(i) Proud a napětí jsou navzájem spojitou funkcí.
(ii) Proud a napětí jsou navzájem neklesající funkce.
(iii) Rozsah proudu je omezen váhami přední a zadní hrany odpovídající odporovému prvku. Aktuální rozsah může zahrnovat nebo vylučovat koncové body. Doména napětí nezahrnuje maximální a minimální proudy:

i ab : R \to [- w ab, w ba] nebo (- w ab, w ba] nebo [- w ab, w ba) nebo (- w ab, w ba)

proti ab : (- w ab, w ba) \to R

Výrok věty

Limit proudu $Já v$ mezi vstupními svorkami elektrické sítě jako vstupní napětí, $PROTI v$ přístupy ${ displaystyle infty}$ , se rovná hmotnosti minimální sady řezu $X C$ .

{ displaystyle lim _ {V_ {in} rightarrow infty} (I_ {in}) = min _ {X_ {C}} součet _ {(a, b) v X_ {C}} w_ { ab}.}

Důkaz

Nárok 1 Proud v kterémkoli odporovém prvku v elektrické síti v obou směrech je vždy menší nebo roven maximálnímu průtoku na odpovídající hraně v grafu. Proto je maximální proud elektrickou sítí menší než váha minimálního řezu grafu průtoku:

{ displaystyle lim _ {V_ {in} rightarrow infty} (I_ {in}) leq min _ {X_ {C}} sum _ {(a, b) v X_ {C}} w_ {ab}.}

2. nárok Jako vstupní napětí ${ displaystyle V_ {in}}$ blíží nekonečnu, existuje alespoň jedna sada řezů ${ displaystyle X '_ {C}}$ tak, že napětí napříč sadou řezů se blíží nekonečnu.

{ displaystyle existuje X '_ {C} ; ; forall ; (a, b) v X' _ {C} ; ; lim _ {V_ {in} rightarrow infty} ( v_ {ab}) = infty}

To znamená, že:

{ displaystyle lim _ {V_ {in} rightarrow infty} (I_ {in}) = sum _ {(a, b) v X '_ {C}} w_ {ab} ; geq ; min _ {X_ {C}} sum _ {(a, b) v X_ {C}} w_ {ab}.}

Vzhledem k výše uvedeným nárokům 1 a 2:

{ displaystyle lim _ {V_ {in} rightarrow infty} (I_ {in}) = min _ {X_ {C}} součet _ {(a, b) v X_ {C}} w_ { ab}.}

Související témata

Existenci a jedinečnost řešení rovnic elektrické sítě složené z monotónních odporových prvků prokázal Duffin.^[2]

aplikace

Cederbaumova věta o maximálním toku je základem pro algoritmus Simcut.^[3] ^[4]

Reference

^ Cederbaum, I. (srpen 1962). "O optimálním provozu komunikačních sítí". Journal of the Franklin Institute. 274: 130–141.
^ Duffin, R. J. (1947). "Nelineární sítě. IIa". Býk. Amer. Matematika. Soc. 10: 963--971.
^ Yim, P.J .: "Metoda a systém pro segmentaci obrazu „Patent Spojených států amerických US8929636, 6. ledna 2016
^ Yim, P.J .: "Metoda a systém pro segmentaci obrazu pomocí směrovaného grafu „Patent USA US9984311, 29. května 2018

Tento kombinatorika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[1] Cederbaum, I. (srpen 1962). "O optimálním provozu komunikačních sítí". Journal of the Franklin Institute. 274: 130–141.

[2] Duffin, R. J. (1947). "Nelineární sítě. IIa". Býk. Amer. Matematika. Soc. 10: 963--971.

[3] Yim, P.J .: "Metoda a systém pro segmentaci obrazu „Patent Spojených států amerických US8929636, 6. ledna 2016

[4] Yim, P.J .: "Metoda a systém pro segmentaci obrazu pomocí směrovaného grafu „Patent USA US9984311, 29. května 2018

[1]

[2]

[3]

[4]