Dominókitöltések és önmagukat nem metsző, de egy alaptéglalapot sűrűn bejáró vonalak

Időpont: 
2015. 12. 01. 10:30
Hely: 
H306
Előadó: 
Kaszanyitzky András és Hujter Mihály

Az előadás első részének absztraktja (előadó: Kaszanyitzky András):

Az ortho-⁠tile típusú FASS-⁠görbék* – melyek csúcsátíró Lindenmayer-⁠rendszerben is megadhatók – a térkitöltő rekurzív görbéknek egy olyan típusát képviselik, amelyek szerkezetükből adódóan csak speciálisan irányított rácsgráfon rajzolhatók meg. Ha páros számú mezőt keretez az irányított gráf, akkor mindig lesz 2 kitüntetett fokszámú pontja: egy forrás és egy nyelő. Csak ebben az esetben léteznek a gráfon a rácspontokat teljesen bejáró önelkerülő útvonalak. E Hamilton-⁠utak és a mezőket hézagmentesen kitöltő dominólefedések között kölcsönösen egyértelmű megfeleltetés, bijekció áll fenn.

*FASS = space Filling, self Avoiding, Simple, self Similar = térkitöltő, önelkerülő, egyszerű, önhasonló;

ortho-⁠tile = a kiinduló útvonal és az önhasonló részek kezdő-⁠ és végpontjai is átlós helyzetűek.

Az előadás második részének absztraktja (előadó: Hujter Mihály):

Az előadás első részében említett bijekció lehetővé teszi, hogy a Hamilton-⁠utak darabszámát teljes pontossággal kiszámoljuk. A felmerülő rokon algoritmikus, gráfelméleti, sőt szerkesztéselméleti és számelméleti problémákat is említjük majd. Rámutatunk a mély (és régóta tanulmányozott) lineáris algebrai és fizikai háttérre is.