Parkolási probléma

Abstract

A parkolási probléma a leszámláló kombinatorika körébe tartozik. Az alapfeladat szemléletesen arról szól, hogy néhány autó le akar parkolni egy ugyanannyi parkolóhelyet tartalmazó egyirányú utcában. Mindegyik sofőrnek van a fejében egy elképzelés, hogy hányadik helyre szeretne állni. Ha az a hely szabad, akkor oda áll, ellenkező esetben pedig az azt követő legelső szabad helyre parkol (ha van ilyen). Kérdés, hogy milyen igénysorozatok esetén tud minden autó leparkolni, és adott számú parkolóhely esetén ezekből hány darab van. A dolgozatban ezeket válaszoljuk meg, továbbá kapcsolatot adunk a nemkeresztező osztályozásokból álló Kreweras-láncokkal, illetve a fagráfokkal. Végül röviden bemutatunk négyet a parkolási probléma változatai közül.