Page 114 - vol1

leszorítani, végül csak 1976-ban sikerül Kenneth Appelnek és Wolfgang
Hakennek helyes bizonyítást adnia. Meglepetésre Heawoord és Kempe
elgondolásait használták fel, számottevő kiterjesztés nélkül. A négyszín-tétel
bizonyítása volt az első számítógépre alapozott bizonyítás.

A négyszíntétel tehát a következő: egy tetszőleges régiókra osztott síkot,
akár egy politikai térképet egy ország megyéiről, ki lehet úgy színezni legfeljebb
négy szín felhasználásával, hogy ne legyen két azonos színű szomszédos régió.
Gráfokkal megfogalmazva pedig a következő: Ha G egy síkba rajzolható gráf,
akkor a gráf színezéséhez elegendő 4 szín.

A gráfok színezése szoros kapcsolatban áll a kromatikus számmal. Egy G gráf
csúcskromatikus száma az a legkisebb pozitív egész szám, amennyi színnel
kiszínezhetők a gráf csúcsai úgy, hogy egy él két végpontja nem lehet azonos
színű. Ezt a számot X(G)-vel jelöljük. Teljesen hasonlóan értelmezik az
élkromatikus számot is.

A gráfszínezést az 1970-es évek óta tanulmányozták algoritmuselméleti
problémaként. Nagyon sok megoldatlan kérdés van a gráfok színezése terén,
viszont számtalan érdekes használata is van a gráfszínezésnek. Már maga a
csúcskromatikus szám megállapítása érdekes és egyben szórakoztató kihívás.
Ezt a tényt kihasználva, a Play Áruházban 3 érdekes játékra leltem, amelyek
csúcskromatikus számokkal kapcsolatosak és szórakoztató jellegük miatt egyben
didaktikai jellegük is van. A legegyszerűbb játék a Graph Puzzle. A feladat az,
hogy adott gráf esetén a csúcsait színezzük ki úgy, hogy egy-egy él végpontjain
a színek ne legyenek egyformák. Sajnos ez a játék csak 6 pályát tartalmaz, de a
szerző leírása szerint szándéka van bővíteni a játékot. A második játék a
Chromatic Puzzle, amely annyi újítást hoz, hogy a gráfok úgymond lebegnek,
vagyis mozgathatók a csúcsaik, ezáltal könnyebb látni, hogy mely csúcsokat
kötnek össze élek. A játékban több szint is van, a könnyűtől egészen a nagyon
nehéz szintig. Mindkét játék menete az, hogy egy adott színre rátapíntunk, és
azzal annyi csúcsot színezünk ki amennyit akarunk, majd színt válthatunk. A
program egyetlen hátránya talán az, hogy aránylag terjedelmes, mert közel 24
MB-ot foglal a telepítéskor. A harmadik játék a The Appies: Graph Puzzle, a
nemében egyedi és érdekes, hasznos és szórakoztató. Szintén gráfokkal találjuk
szembe magunkat, na meg a színek helyett színes kis manókák (appies)
amelyeket rá kell húzni a gráf valamely csúcsaira úgy, hogy egy él két végpontján
a manók színe különböző legyen. A játékban annyi újítás található, hogy az egyes
színes manókák mellett egy-egy szám is található ami azt jelzi, hogy hányszor is

114