2.5. 2.5. A hálózat fogalma

Tekintsünk egy digráfot, az éleihez rendeljünk hozzá egész számokat. A digráfot az éleire rendelt nemnegatív egész számokkal együtt hálózatnak nevezzük és -val jelöljük. A érték az él valamilyen számszerűsíthető tulajdonságát jelenti, általában időt, távolságot, költséget, kapacitást stb. jelent. A hálózatot a digráfhoz hasonlóan lehet megadni. A értékeket „honnan-hova” táblázat esetén egy harmadik sorban, struktúramátrix esetén pedig a mátrix elemeiként adjuk meg. Az alábbiakban az út és a vágás fogalmával kapcsolatban két optimalizálási feladatot fogalmazunk meg:

a) Minimális út feladat:

Legyen az hálózatnak két kitüntetett pontja .

Meghatározandó azon -ből -be vezető P út, amely mentén az élekre írt értékek összege, azaz a

mennyiség minimális.

A mennyiséget általánosan úthossznak szoktuk nevezzük. A minimális út a értékektől függően jelenthet legkisebb távolságú, legrövidebb idejű, legkisebb költségű, legkisebb kapacitású stb. utat.

b) Minimális vágás feladat:

Legyen az hálózatnak két kitüntetett pontja: .

Meghatározandó az -et a -től elválasztó vágások közül az, amelynél a vágásbeli élekre írt értékek összege, azaz a

mennyiség minimális.

A k(S,T) mennyiséget általánosan az (S,T) vágás kapacitásának szoktuk nevezni.

A jegyzetben két irányban indulunk el, a fentebb definiált két optimalizálási feladatnak megfelelően. Az első irány, a minimális út témakör sok érdekes feladathoz vezet, mi a minimális út problémával és az időtervezési feladatokkal (CPM/time, PERT) foglalkozunk. A második irány a minimális vágás feladat témaköre, erre fűzzük fel a további optimalizálási feladatainkat, így többek között a hozzárendelési és a szállítási feladatot is, amelyek megoldására a „magyar módszer”-t mutatjuk be.