Dominókitöltések és önmagukat nem metsző, de egy alaptéglalapot sűrűn bejáró vonalak
Helyszín:
Budapesti Műszaki és Gazdaságtudományi Egyetem,
Matematika Intézet, H-épület 306-os terem, keddenként 10:30-kor
Következő előadás: 2015. december 1.
Kaszanyitzky András és Hujter Mihály
Absztrakt
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.
Második rész (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.
link: http://www.math.bme.hu/~belus/Geoszem/Geoszem.htm