1. fejezet - Bevezetés

A hálózati folyamok témakörben olyan optimalizálási feladatokkal foglalkozunk, amelyek gráfok ill. hálózatok segítségével is megfogalmazhatók, ebből következőleg gráfelméleti eszközökkel is kezelhetők. Bevezetésképpen tekintsük az alábbi egyszerű szállítási feladatot. Három termelőtől (T) akarunk elszállítani bizonyos árut négy fogyasztóhoz (F). Valamilyen oknál fogva a , , viszonylatokban nem lehet szállítani. A termelőktől a fogyasztókhoz rendre 30, 50, 40 teherautónyi elszállítandó mennyiségű árut kell elszállítani. A fogyasztók igénye rendre 40, 20, 50, 30 teherautónyi mennyiségű áru. A fenti adatokat a termelők kínálatának ill. a fogyasztók keresletének szoktuk nevezni. Az alábbi táblázat mutatja, hogy a termelők telephelye és a megrendelőhelyek között egy teherautónyi mennyiségű árut mekkora költséggel szállíthatunk el. A tiltott viszonylatokat a táblázatban „-” jellel jelöltük.

Feladatunk a következő:

Adjuk meg azt a szállítási tervet, amelynél az áruk a termelőktől a fogyasztókhoz történő elszállítása a legkisebb költséggel valósul meg!

A feladat matematikai megfogalmazását az alábbiakban adjuk meg. A matematikai megfogalmazáshoz három dolgot kell meghatároznunk, ezek a következők: döntési változó megállapítása, a döntési változók lehetséges értékeit meghatározó feltételek felírása, végül annak a függvénynek a felírása, amelynek értéke szerint döntünk a lehetséges megoldások közül (ezt a függvényt célfüggvénynek nevezzük).

1. Döntési változó megállapítása:

Legyen a döntési változó az, hogy az egyes telephelyekről az egyes megrendelőhelyekre mennyi teherautónyi árumennyiséget szállítunk. Jelöljük ezeket az kétindexes változókkal, amely a termelőtől az fogyasztóhoz szállított mennyiséget mutatja. A döntési változókat az alábbi táblázatba foglalhatjuk.

2. Feltételek meghatározása:

Természetes feltétel, hogy az összes döntési változó nemnegatív. Először a kínálati feltételeket határozzuk meg. Az egyes termelőktől elszállítandó mennyiséget az egyes sorokban lévő döntési változók összege adja, amelynek egyenlőnek kell lenni a termelők kínálatával. A keresleti feltételek meghatározásánál figyelembe kell venni, hogy a termelők összkínálata kisebb, mint a fogyasztók összkereslete (), így a fogyasztók nem mindegyikének az igényét lehet teljes mértékben kielégíteni. Az egyes fogyasztókhoz szállítandó mennyiséget az egyes oszlopokban lévő döntési változók összege adja, amely kisebbnek vagy egyenlőnek kell lenni a fogyasztók keresletével.

3. Célfüggvény meghatározása:

Tegyük fel, hogy a szállítási költség lineárisan változik a szállítandó mennyiséggel. Jelölje a szállítási egységköltséget a termelőtől az fogyasztóhoz, ekkor a termelőtől az fogyasztóhoz az mennyiségű áru szállítási költsége . Itt vettük figyelembe a linearitási feltételezést. A szállítás összköltsége pedig az egyes viszonylatok szállítási költségének az összege.

A probléma matematikai modellje tehát a következő:

A termelőket, a fogyasztókat egy-egy „ponttal”, az egyes termelők és fogyasztók közötti szállítási kapcsolatot pedig egy-egy nyíllal reprezentálhatjuk a síkon. Ezt mutatja az alábbi ábra.

A fenti alakzatot gráfnak, pontosabban irányított gráfnak nevezzük. Amennyiben a kapcsolatokra ráírjuk a szállítási egységköltségeket, akkor hálózatot kapunk. A fentebb felírt szállítási feladat egy lineáris programozási feladat, így a lineáris programozás ismert módszereinek bármelyikével megoldható. Viszont azt is tudjuk, hogy ez egy rendkívül speciális szerkezetű lineáris programozási feladat, mivel az együtthatómátrixa csupán 0 és 1 értékeket tartalmaz és ezeket is megfelelő szabályossággal. A szállítási feladat tehát speciális szerkezeténél fogva gráfok segítségével is reprezentálható.

Természetesen a gráfok körében nem csupán optimalizálással kapcsolatos kérdéseket tehetünk fel, hanem kombinatorikai jellegűeket is. Szoros értelemben a gráfelmélet a kombinatorikai kérdések megválaszolásával foglalkozik. A gráfelmélet viszonylag fiatal része a matematikának. Születését a königsbergi hidak problémájának felvetődésétől számítják. Ennek története a XVIII. század 30-as éveire nyúlik vissza. A Szentpétervárhoz közeli Königsberg városát a Pregel nevű folyó átszeli és az akkori időben hét híd ívelte át, amelyet az alábbi ábra szemléltet.

A város polgárai szívesen sétálgattak a folyó partján és a hidakon, próbáltak olyan sétákat is tenni, amelynek alkalmával minden hídon pontosan egyszer haladnak át. Soha nem tudtak azonban ilyen sétautat találni. Ez időben a svájci származású matematikus, Leonard EULER (1707-1783) a szentpétervári akadémián dolgozott és Königsberg polgárai hozzá fordultak problémájuk megoldásában. Euler a problémára választ is adott az 1736-ban megjelent dolgozatában [ 3 ]. A matematikai szakirodalomban ezt a művet tekintjük az első gráfelméleti munkának és ezzel megszületett egy új matematikai diszciplína, a gráfelmélet. Euler a fenti ábrát leegyszerűsítve rajzolta le papírra. A két folyópartot (A, B) és a két szigetet (C, D) egy-egy ponttal, ezeket összekötő hidakat (a, b, c, d, e, f, g) egy-egy vonallal szemléltette, amelyet az alábbi ábra mutat. Egy gráf ábráján a gráf pontjait kis karikával szokás jelölni, de szokásos a körrel való jelölés is (a körbe írva a pont megnevezését), ez utóbbi ábrázolású a fejezet elején található digráf.

Euler a gráfban definiálta a gráf-vonalat, amely a gráf összes élének egy olyan egymásra kapcsolódó sorozata, amelyben a gráf élei nem ismétlődnek. Ha a sorozat első élének kezdőpontja megegyezik a sorozat utolsó élének végpontjával, akkor zárt gráf-vonalról, egyébként pedig nyitott gráf-vonalról beszélünk. Később a gráfelméletben a gráf-vonalat Euler-vonalnak, az olyan gráfot, amelynek van Euler-vonala Euler-gráfnak nevezték el. Euler a fent említett dolgozatában a „königsbergi hidak problémájaként” ismertté vált problémafelvetésre választ is adott. Mielőtt azonban a választ megfogalmazzuk, az Euler-vonal mellett még két fontos fogalomra van szükségünk. Egy gráf akkor összefüggő, ha bármely két pontját út köti össze, azaz élek sorozatával el tudunk jutni minden pontból minden pontba. A gráf pontjaihoz fokszámot rendelhetünk. Egy adott gráfpont fokszáma vagy röviden foka alatt a gráfponthoz illeszkedő élek darabszámát értjük.

EULER tétel:

  1. Ha egy gráf összefüggő és a gráf minden pontjának fokszáma páros, akkor létezik a gráfnak zárt Euler-vonala.

  2. Ha egy gráf összefüggő és a gráf két pontjának fokszáma páratlan, a többi pont fokszáma páros, akkor létezik a gráfnak nyitott Euler-vonala.

A második állítás az elsőből könnyen adódik, hiszen ha egy gráf összefüggő és a gráf két pontjának fokszáma páratlan, akkor kössük össze a két páratlan fokszámú pontot egy új éllel. Ekkor a bővített gráf összefüggő marad és minden pontja páros fokszámú, így az EULER tétel (1) része szerint létezik zárt Euler-vonal. Ha most elhagyjuk az új élet a zárt Euler-vonalból, akkor az eredeti gráf egy nyitott Euler-vonalát kapjuk.

Könnyen látható tehát, hogy a königsbergi sétát nem véletlenül nem sikerült megvalósítani a polgároknak, azt is látjuk, hogy bárhová megépítve a nyolcadik hidat, már megvalósítható a séta. A „königsbergi hidak problémája” úgy is felfogható, hogy lerajzolhatjuk-e a gráf éleit egyetlen ceruzavonással, úgy hogy a ceruzát nem emeljük fel a rajzolás során és egy élet csak egyszer rajzolunk le. Példaként az alábbi ábrán látható alakzatot rajzoljuk meg a fentiekben megfogalmazott egyetlen ceruzavonással.

Az alakzat gráfként is felfogható, annak ellenére, hogy a pontokat nem jelöltük be. Az EULER tétel szerint nyitott Euler-vonal van, így valamelyik páratlan fokszámú csúcspontból elindulva a második páratlan fokszámú csúcspontba megérkezve megrajzolható az ábra.

A görög mondából mindenki ismeri Ariadné fonalát, amelynek segítségével sikerült kijutnia Thészeusz athéni királyfinak a labirintusból, miután a labirintusban legyőzte Minótauroszt, a szörnyeteget. A monda szerint Ariadné Minósz krétai király leánya volt, Minótaurosz pedig a király félig bika, félig ember alakú szörnyszülött fia volt. Egy labirintust is kezelhetünk gráffal a következők szerint. A labirintusban az elágazási pontok és a zsákutcákat alkotó folyosók végei legyenek a gráf pontjai, a folyosószakaszok pedig legyenek a gráf élei.

Egy ország közút- vagy vasúthálózata is jellemezhető gráfokkal. A városokat ill. a falvakat a gráf pontjai, az összekötő útszakaszokat pedig a gráf élei reprezentálják. Nem ilyen egyszerű azonban egy város úthálózatának gráffal való azonosítása, mivel egyirányú utak is vannak. Ekkor az útkereszteződéseknek a gráf pontjait, az útszakaszoknak pedig az irányukat jelző ún. irányított éleknek feleltetjük meg. Az ilyen gráfokat irányított gráfoknak nevezzük. A későbbiekben csak irányított gráfokkal fogunk foglalkozni. Amennyiben egy útszakaszon mindkét irányban lehetséges a forgalom, azt két darab, iránnyal ellátott (oda-vissza) éllel fogjuk jellemezni. Az irányok használata valóban kijelöli az úthálózatban való haladási lehetőségeket, de azt nem kezeli, ha egy útkereszteződésben kanyarodási tilalmak is vannak. Ennek megvalósítását mutatjuk be az alábbiakban. Tekintsük az alábbi ábrán látható útkereszteződést, amelyben az a és b útszakaszon haladva balra is és jobbra is kanyarodhatunk, a c és d útszakaszon haladva pedig csak jobbra kanyarodhatunk.

Az útkereszteződés kanyarodási szabályát úgy tudjuk figyelembe venni, hogy az útkereszteződést nem egyetlen gráfponttal, hanem nyolc gráfponttal ábrázoljuk. Ezt mutatja az alábbi ábra.

Megjegyezzük, hogy amennyiben az a és b útszakaszokon haladóknak megengedjük az útkereszteződésben a megfordulást, akkor azt a felső két pontot összekötő jobbra irányuló ill. az alsó két pontot összekötő balra irányuló élek felvételével valósíthatjuk meg.

A gráfelméletet sok szaktudomány is alkalmazza egyszerűsége és könnyen kezelhetősége miatt. A fentebb látott példák mellett megemlítjük, hogy egy több tevékenységből álló feladat résztevékenységeit és a köztük fennálló logikai, technológiai kapcsolatokat is jellemezhetjük irányított gráffal. Ugyanígy egy elektromos hálózat is egy irányított gráf, amely különböző elektromos alkatrészek (ellenállások, tekercsek, kondenzátorok, fogyasztók, stb.) összekapcsolásával jön létre.

Ezen bevezető után a következő fejezetben a gráfokon történő optimalizáláshoz szükséges alapfogalmakat sajátítjuk el. Megismerkedünk egy nagyon fontos számolási eszközzel az ún. címkézési technikával, amely olyan fontos eszköz a gráfok esetében, mint a pivotálás a vektorok esetében. Az ezután következő fejezetekben optimalizálási modelleket tárgyalunk. A témakör kicsúcsosodását a hozzárendelési feladat megoldására 1955-ben H. W. KUHN [ 10 ] amerikai matematikus által kidolgozott „magyar módszer” jelenti. Végezetül megemlítjük, hogy az első összefoglaló mű a gráfokról 1936-ban KŐNIG DÉNES [ 9 ] magyar tudós tollából jelent meg.