5. óra
(2007.10.15.)
Minimális összhosszúságú hálózat, Steiner-fák
A mai órán is egy megoldhatatlan problémával foglalkozunk, pontosabban annak
egy megoldható részével. Adott helyzetű pontokat kell a legrövidebb, egyenes szakaszokból álló, hálózattal összekötnünk. Ez hasonlít a "minimális feszítőfa" feladatra, de most felvehetünk új csomópontokat is.
A feladatot Jacob Steiner svájci geométer tűzte ki a 19. században, az első ismert megoldási algoritmust Z. A. Melzak adta. A megoldást jelentő hálózatot Steiner-fának nevezzük. Azt sejtjük, hogy a Steiner-fa meghatározása NP-teljes probléma, sok város esetén nem remélhető hatékony algoritmus.
A mai órán azt vizsgáljuk, hogy néhány város esetén milyen módszerrel állítható elő az
optimális Steiner-fa.
Feladat
Irodalom
