A Kibogozó (angolul untangled) készségfejlesztő játék lényege, hogy a felületen lévő pontokat úgy kell átrendezni, hogy egy vonaluk se keresztezze a másikat. Mintha gumiszalagok lennének a pontok között, vagy gráfok lennének.
Változatai[]
- Gyakorló változat, egyre nehezebb feladatokkal, néhány rögzített ponttal: Dont cross the line / ne keresztezd a vonalat
- Testre szabható egyszerű változat, Type: 6-25 mozgatható csomóponttal: Untangle / kibogozó
- Haladó, beállítható a csomópontok száma Jason Davies: Planatary
Gráfelméleti alapok[]
- Egy struktúra lehet összefüggő vagy több egységre bomló
- Ha egy rendszert áttekintéséhez rendezzük, az "kifeszítés"
- Az elemek vagy csomópontok kapcsolati hálózata a topológia
- Ha van egy jól meghatározható alap vagy kiindulópont, amihez minden kapcsolódik, akkor az egy Fa-gráf
- Lehetséges olyan kapcsolat, amely csak egy irányú
- Egy struktúra annál bonyolultabb, minél több elágazással rendelkező csomópontok vannak.
- A kapcsolatokat lehet mélységében feltárni DFS (Depth First Search, magyarulMélységi keresés) vagy BFS (Szélességi keresés)
- Mélységi - gyors: az útvonalat megjegyezve addig haladok előre, amíg lehetséges, ha elakadok, csak az előző elágazásig megyek vissza, akkor próbálok másik utat
- Szélességi - alapos: Amikor a kiindulóponttól minden utat végigpróbálok, és csak akkor megyek tovább, ha az adot pontban mindent felderítettem.
- A DFS algoritmus