Ubogi geograf

Kakšno zvezo ima sestavljanje urnikov z reševanjem sudokuja bomo izvedeli, ko bomo pobarvali nekaj zemljevidov.

Namen

Otroci spoznajo znani problem barvanja grafov.

Vidijo, kako je mogoče probleme, ki navidezno nimajo nobene povezave z barvanjem grafov, prevesti na barvanje grafov.

V splošnem, vidijo, da se za navidez različnimi problemi lahko skriva (strukturno) isti problem, zato so lahko algoritmi za njihovo reševanje uporabni v najrazličnejših situacijah.

Otroci se tudi ponovno srečajo z grafi. Doslej smo z njimi predstavili ladijske povezave med otoki in povezave med hišami v Blatnem dolu. Tu povezave v grafih ne prikazujejo fizičnih povezav temveč relacijo “nezdružljivosti”, kar je nekoliko abstraktneje od prejšnjih rab grafov.

Potrebščine

Vsak otrok potrebuje

• kopije zemljevidov, ki jih bo barval (13A, 13B in 13C; na 13C so grafi za štiri učence),
• vsaj štiri barvice (lahko tudi flomastre ipd.),

Dodatna navodila

Aktivnost je zasnovana tako, da se otroci najprej srečajo s problemom, ki ga ni težko razumeti, ne morejo pa poiskati njegove rešitve (če že, pa bo iskanje nesistematično in nepregledno).

Nato spoznajo navidez povsem nepovezano področje, barvanje grafov, pri čemer začnejo iz običajnega izhodišča, barvanje zemljevidov.

Nato vidijo, kako se barvanje grafov skriva za reševanjem Sudoka in, končno, kako lahko s pomočjo barvanja grafov sestavljajo urnike krožkov.

Drugi viri in avtorji

Osnova aktivnosti je priredba CS Unplugged: Graph Colouring. Uvodna motivacija in razlaga s sudokujem sta izvirna.