S-típusú igazmondó-hazug fejtörők gráfelméleti megközelítésben

Nagy, Benedek (2006) S-típusú igazmondó-hazug fejtörők gráfelméleti megközelítésben. ALKALMAZOTT MATEMATIKAI LAPOK, 23. pp. 59-72. ISSN 0133-3399

Preview

Text 03ALKMAT_23.pdf - Published Version Download (770kB) | Preview

Abstract

Olyan igazmondó-hazug fejtörők gráfjait vizsgáljuk részletesen, amikben minden szereplő csak egyszerű mondatokat mondhat valamely szereplő típusáról. A gráf-reprezentációban a tiszta rejtvényekről - amelyekben az elhangzó mondatokon kívül nincs plusz információnk - minden információ benne van. A lehetséges gráfok több érdekes tulajdonságát is bemutatjuk. Megmutatjuk, hogy nincs olyan tiszta egyszerűmondatos igazmondó-hazug fejtörő, aminek egyetlen megoldása van. A gráfban az élek kétféle súlyúak lehetnek, irányításuk viszont nem játszik szerepet. Bevezetjük a maximális és a minimális fejtörők fogalmát, amelyek a teljes gráfokhoz, illetve a feszítőerdőkhöz köthetőek. Mutatunk egy algoritmust, amellyel bármely tiszta rejtvénynek meghatározhatjuk a lehetséges megoldásait a gráf összefüggő komponenseinek vizsgálatával.

Actions (login required)

Edit Item