Áram (gráfelmélet)

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

Az $x:A\rightarrow \mathbb {R}$ függvény áram vagy áramlás, ha $\rho _{x}(\{v\})=\delta _{x}(\{v\})$ minden $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:

$f(a)\leq x(a)\leq g(a)$ minden $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 $\rho _{f}(X)\leq \delta _{g}(X)$ minden $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ő, $s,t\in V.$ Az $x:A\rightarrow \mathbb {R}$ függvény folyam, ha $\rho _{x}(v)=\delta _{x}(v)$ minden $v\in V$ $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 $\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 $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 $p\leq b$ korlátozó függvények, és $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 $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 $z\subset V$ részhalmazain az m függvény. Legyen $\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 $\lambda _{x}(v)=m(v)$ minden $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 $f\equiv 1$ $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 $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