3.5. 3.5. Feladatok

  1. Adott az alábbi „honnan-hova” táblázattal egy hálózat. Keressen olyan utat, amely útban az élek hosszúságának összege a legkisebb értékű!

    Megoldás:

    A minimális út: .

    A minimális úthossz:

  2. Határozza meg az alábbi hálózaton az 1-ből a 7-be vezető legrövidebb utat és a potenciálrendszert!

  3. Legyen adott egy városi úthálózat. Hogyan kell közlekednünk két útkereszteződés (s és t) között, hogy minél kevesebb útkereszteződést érintsünk útunk során?

    Útmutató a megoldáshoz:

    Ha az úthálózatot (amelyet digráffal reprezentáltunk) hálózattá alakítjuk úgy, hogy minden élre egységnyi értéket írunk, akkor ezzel a feladatot minimális út feladatra vezettük vissza. Nyilvánvaló, hogy a hálózat minimális útja a legkevesebb csomópontból álló útvonalat fogja kijelölni.

  4. Adott egy elektromos hálózat. Minden csomópontban van egy kapcsoló (K). A legkevesebb kapcsoló beiktatásával szeretnénk az s és a t jelű pontok között kapcsolatot teremteni. Mely kapcsolókat kell üzembe helyezni?

  5. Adott egy vállalat úthálózata, távolságokkal. Az 1 jelű munkahelytől kell eljutni az 5 jelű munkahely érintésével a 8 jelű raktárba úgy, hogy legkevesebb utat tegyünk meg. Milyen úton lehet ezt megvalósítani?

    Útmutató a megoldáshoz:

    Két minimális utat kell keresni, egyiket 1-ből 5-be, másikat 5-ből 8-ba!

  6. Legyen adott egy hírközlési há1ózat. Jelölje az i és a j pont közötti összeköttetés működőképességének valószínűségét. Feladatunk, hogy egy kijelölt pontból egy másikba olyan összeköttetéseket hozzunk létre, hogy a hírt a két csomópont között legmegbízhatóbban továbbíthassuk, azaz a két pont közötti összeköttetés működőképességének valószínűsége minél nagyobb legyen!

    Útmutató a megoldáshoz:

    Egy összeköttetés egy utat jelöl ki a hálózatban, mely összeköttetés működőképességének va1ószínűségét az egyes pontok közötti összeköttetési va1ószínűségek szorzata adja. Ezt a szorzatot kell tehát maximalizálni. Ez a feladat akkor válik a megismert minimális út problémává, ha minden va1ószínűséget a „hosszúsággal” helyettesítünk, ugyanis ekkor az útbeli

    célfüggvény helyett a

    célfüggvény használható. Ismert tény, hogy az összeg logaritmusa egyenlő a logaritmusok összegével, azaz

    Felhasználva a logaritmus függvény monoton növekedését és azt a tény, hogy egy függvény ott veszi fel minimumát, ahol a (-1)-szerese a maximumát, könnyen látható a két célfüggvény kapcsolata.