Együttműködés Steiner-fákon

Absztrakt (kivonat)

Dolgozatom első részében a Steiner-fa típusairól olvashatunk. Megkülönböztetjük az euklideszi téren és gráfon értelmezett Steiner-fákat, amikben az a közös, hogy a fogyasztókat szeretnénk összekapcsolni a szolgáltatóval úgy, hogy a költségeket minimalizáljuk, és rendelkezésre állhatnak fogyasztó nélküli, úgynevezett nyilvános csúcsok is. Az első fejezetben részben az euklideszi Steiner-fával foglalkozunk, megmutatjuk, hogy a játék magja lehet üres, amire egy példát is találhatunk. Ezt követően ismertetésre kerül egy gyors algoritmus, amivel jó megoldást találhatunk a minimális költségű Steiner-fa problémára. Ennek ’jóságát’ mutató Steiner-arány legfontosabb értékeit is ismertetjük. A második fejezetben a játékelméleti alapfogalmak felvázolása után a minimális költségű feszítőfa problémát írtam le, hiszen ez egy nyilvános csúcs nélküli Steiner-fa probléma. Ennek a modellnek ismert tulajdonsága, hogy nem üres a magja. A harmadik fejezetben a csúcs súlyozott Steiner-fa problémával (VWST) foglalkoztunk, itt az élekhez kapcsolódó költségeken kívül, a fogyasztók bevételre tesznek szert, amit a csúcsokhoz rendelünk. Belátjuk, hogy egy allokáció akkor van a magban, ha hatékony. Definiáljuk az anti-mag fogalmát, majd megvizsgáljuk a maggal vett kapcsolatát. Ezt követően a játékot gráfra illesztjük és meghatározzuk a Steiner-kiegyensúlyozottság fogalmát, valamint néhány ehhez kapcsolódó tételt. Fontos eredmény, hogy minden ötszereplős VWST játéknak nem üres a magja. A negyedik fejezetben a csúcsokhoz nem rendelünk értéket, csak az élekhez. A modell és néhány gráfelméleti fogalom ismertetése és példán keresztüli szemléltetése után kimondunk egy nagyon fontos tételt, mely szerint a minimális költségű Steiner-fa magja nem üres. A bizonyítást, annak komplexitása miatt a dolgozatban nem tüntetjük fel. Egy saját példában kerestünk egy magbeli elosztást a játék primál és duál megoldását felhasználva. Az ötödig fejezetben egy olyan általános modellel foglalkozunk, amelyben mind a csúcsokhoz, mind az élekhez tartozhat költség vagy bevétel. Megvizsgáljuk a kapcsolatot a redukált feszítő hálózat és a kapcsolódó redukált játék között. Az eredmények nem függnek az optimális hálózat megválasztásától, de végig feltesszük, hogy létezik egy, a nagykoalícióra vonatkozó feszítőfa, amely minden fogyasztót tartalmaz. Ekkor bebizonyítható, hogy az előző kondíció és azon feltétel mellett, hogy nincs két szomszédos nyilvános csúcs, a mag nem üres.