Áram (gráfelmélet)

A Wikipédiából, a szabad enciklopédiából

Legyen irányított gráf, és legyen függvény. Minden halmazra jelölje az x függvény értékeinek összegét az S halmazba lépő éleken, és jelölje az x függvény értékeinek összegét az S halmazból kilépő éleken.

Az függvény áram, ha minden csúcsra, magyarul, ha teljesíti a megmaradási szabályt.

Megengedett áram[szerkesztés]

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:

minden

A Hoffman-tétel szerint a D=(V,A) irányított gráfban akkor és csak akkor van megengedett áram, ha minden halmazra.

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

Rokon fogalmak[szerkesztés]

Folyam[szerkesztés]

A folyam fogalma hasonlóan definiálható. Adva legyen az s forrás, és a t nyelő, Az függvény folyam, ha minden 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 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 .

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[szerkesztés]

Adva legyenek a D irányított gráf csúcsain a b és a p korlátozó függvények, és

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

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

Moduláris áram[szerkesztés]

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 részhalmazain az m függvény. Legyen moduláris függvény. Az x függvény moduláris áram, röviden m-áram, ha minden -re.

Alkalmazások[szerkesztés]

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

Tesztfeladat[szerkesztés]

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 kapacitásfüggvényekre vonatkozóan.

Szállítási feladat[szerkesztés]

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 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[szerkesztés]

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

Forrás[szerkesztés]

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