gráf színezés

Rövid szöveges bemutatás: 
A gráf színezés egy a gráfokkal kapcsolatos érdekes feladat. A cél az, hogy úgy színezzük ki a gráfot, hogy az egymással összekötött csomópontok különböző színűek legyenek, de azok a csomópontok melyek nincsenek összekötve egymással lehetnek azonos színűek. Ebből számos megállapítást lehet tenni, a legkézenfekvőbb például, hogy az azonos színű csomópontok függetlenek egymástól. Sok érdekes probléma merült fel a színezésekkel kapcsolatban, ilyen például a 3szín probléma, mely NP teljes probléma. A 3színezést a térképek kiszínezésénél merült fel először. Bővebben a témáről a mellékelt weboldalon tájékozódhat.