Leírás
Absztrakt:
Egy síkbarajzolható gráf éleinek meghatározott kapacitású robotokkal való bejárása a lehető legrövidebb idő alatt, a gyakorlatban fontos, úgynevezett CARP (capacitated arc routing) problémakörbe tartozik, amelyet Golden és Wong ismertetett az 1980-as években. Szorosan kapcsolódik ezen NP-nehéz élútvonal tervezési problémához az a gráfelméleti probléma, amely azt vizsgálja, hogy felbontható-e él-diszjunkt Euler-körökre egy gráf oly módon, hogy a felbontásban szereplő Euler-körök élszáma előre adott. Mivel utcahálózatok és épületek belső alaprajzát sokszor négyzethálós gráfok szolgáltatják, természetes ezen problémát négyzethálós gráfok minimális Euler-kiterjesztésére vizsgálni. Az előadásban egy konstruktív gyors algoritmust mutatunk be, amely egy tetszőleges méretű négyzethálós gráf éleinek bejárását adja meg meghatározott kapacitású robotokkal a legrövidebb idő alatt.
Aki szeretne csatlakozni, kérem, hogy e-mailben jelezze Varga Anitánál (vanita@math.bme.hu).