Áram (gráfelmélet)

Legyen ${\displaystyle D=(V,A)}$ irányított gráf, és legyen ${\displaystyle x:A\rightarrow \mathbb {R} }$ függvény. Minden ${\displaystyle S\subset V}$ halmazra jelölje ${\displaystyle \rho _{x}(S)}$ az x függvény értékeinek összegét az S halmazba lépő éleken, és jelölje ${\displaystyle \delta _{x}(S)}$ az x függvény értékeinek összegét az S halmazból kilépő éleken.

Az ${\displaystyle x:A\rightarrow \mathbb {R} }$ függvény áram vagy áramlás, ha ${\displaystyle \rho _{x}(\{v\})=\delta _{x}(\{v\})}$ minden ${\displaystyle v\in V}$ csúcsra, magyarul, ha teljesíti a megmaradási szabályt.

Megengedett áram

Legyenek adva a D gráf élein rendre az f,g felső és alsó korlátok (kapacitások). Ekkor, ha minden élen az x áram értékei az f és a g értékei közé esnek, akkor x megengedett áram:

${\displaystyle f(a)\leq x(a)\leq g(a)}$ minden ${\displaystyle a\in A.}$

A Hoffman-tétel szerint a D=(V,A) irányított gráfban akkor és csak akkor van megengedett áram, ha ${\displaystyle \rho _{f}(X)\leq \delta _{g}(X)}$ minden ${\displaystyle X\subset V}$ halmazra.

Ha emellett a korlátok még egész értékűek is, akkor van egész értékű megengedett áram.

Rokon fogalmak

Folyam

A folyam fogalma hasonlóan definiálható. Adva legyen az s forrás, és a t nyelő, ${\displaystyle s,t\in V.}$ Az ${\displaystyle x:A\rightarrow \mathbb {R} }$ függvény folyam, ha ${\displaystyle \rho _{x}(v)=\delta _{x}(v)}$ minden ${\displaystyle v\in V}$ ${\displaystyle v\neq s,t}$ csúcsra, vagyis a megmaradási szabály a forrás és a nyelő kivételével mindenütt teljesül.

Legyen x áram, és S olyan halmaz, ami tartalmazza az s forrást, de a t nyelőt nem. Ekkor a ${\displaystyle \delta _{x}(S)-\rho _{x}(S)}$ nem függ S választásától.

Ha x áram, akkor teljesül a maximális folyam - minimális vágás tétele:

a megengedett s-t folyamok nagysága egyenlő a δ_g(S) értékek minimumával, ahol ${\displaystyle s\in S,t\not \in S}$.

Ha még g egész értékű is, akkor akkor a maximális folyam is választható egész értékűnek.

Az áram egy általánosítása

Adva legyenek a D irányított gráf csúcsain a b és a p ${\displaystyle p\leq b}$ korlátozó függvények, és ${\displaystyle p(v)\leq \rho _{x}(v)-\delta _{x}(v)\leq b(v).}$

Ez az általánosítás könnyen visszavezethető az áram feladatra:

Vegyünk hozzá a D irányított gráfhoz egy új s pontot, és vezessünk D minden pontjából egy élt az s pontba. Terjesszük ki a kapacitásfüggvényt: legyen f(vs)=p(v) és g(vs)=b(v). Terjesszük ki az x függvényt is: legyen ${\displaystyle x^{1}(vs)=\rho _{x}(v)-\delta _{x}(v)}$

Az x függvény akkor és csak akkor teljesíti a feltételeket, ha x¹ megengedett áram a kiterjesztett kapacitásokra.

Moduláris áram

A moduláris áram az áram és a folyam közös általánosítása. Adva legyen a D=(V,A) irányított gráf csúcsainak ${\displaystyle z\subset V}$ részhalmazain az m függvény. Legyen ${\displaystyle \lambda _{x}(Z)=\rho _{x}(Z)-\delta _{x}(Z)}$ moduláris függvény. Az x függvény moduláris áram, röviden m-áram, ha ${\displaystyle \lambda _{x}(v)=m(v)}$ minden ${\displaystyle v\in V}$-re.

Alkalmazások

Az áramokat és a folyamokat több probléma megoldásához is felhasználják.

Tesztfeladat

Adva van egy áramkör, ami n különböző állapotban lehet. Minden állapotból át lehet menni más állapotokba, és minden átmenethez adott hosszúságú idő kell.

A feladat: az áramkör ellenőrzése minél gyorsabban, azaz minél rövidebb idő alatt.

A feladat megoldható a következő módon: tekintsük a D(V,A) irányított gráfot, ahol V az állapotok, A az átmenetek halmaza, és egy él költségfüggvénye az adott átmenet ideje. Ekkor a tesztfeladat megfelel annak, hogy minimális költségű bejárást keressünk D-ben.

Ha a gráf minden pontjába ugyanannyi él megy be, mint amennyi ki, akkor a minimális költségű bejárás egy Euler-bejárás lesz. Különben a feladat áram feladatként fogalmazható át: keressünk egy minimális költségű, egész értékű megengedett áramot az ${\displaystyle f\equiv 1}$ ${\displaystyle g\equiv \infty }$ kapacitásfüggvényekre vonatkozóan.

Szállítási feladat

Adott k üzem, ami ugyanazt a terméket állítja elő, és adott l fogyasztóhely. Ismerjük a termelőkapacitásokat és az igényeket, és tudjuk, honnan hová milyen kapacitással és költséggel lehet szállítani. A feladat: döntsük el, hogy van- e minden igényt kielégítő szállítási terv, és ha van, akkor elégítsük ki az igényeket a legolcsóbban!

Legyen G(V,E) páros gráf, ahol S jelöli az üzemeket, és T a fogyasztókat. Jelölje q(v) S pontjainak kibocsátóképességét, és jelölje h(v) T pontjainak igényeit. Irányítsuk meg G éleit S-től T felé. Adjunk hozzá G-hez egy s és egy t pontot. Vezessünk s-ből S minden v pontjába egy q(v) kapacitású élt, és vezessünk T minden v pontjából h(v) kapacitású élt t-be. Az S és a T között vezető élek kapacitásai legyenek az adott utak kapacitásai.

A feladatnak akkor és csak akkor létezik megoldása, ha az így kapott gráfban van ${\displaystyle M=\sum {v\in T}h(v)}$ kapacitású folyam. A költséges változat egy minimális költségű M folyam meghatározását célozza.

Egyéb alkalmazások

A folyamok és a folyamalgoritmusok segítségével bebizonyítható a Menger-tétel, vagy megoldható a PERT feladat.

Források

Frank András: Operációkutatás