Ugrás a tartalomhoz

Matematikai mozaik

Andrásfai Béla, Bakos Tibor, Bognár Jánosné, Bognár Mátyás, Gallai Tibor, Hódi Endre, Laczkovich Miklós, Molnár Ferenc, Reimann István, Rényi Alfréd, Révész Pál, Rónyai Lajos, Surányi János, Vadkerty Tibor, Varga Tamás

Typotex

5. TETSZŐLEGES TÉRKÉPEK SZÍNEZÉSE

5. TETSZŐLEGES TÉRKÉPEK SZÍNEZÉSE

A térképek színezésének problémáját a normál térképek színezésére korlátoztuk. Amint láttuk, ez lényeges megszorítást jelent. A minimális színszükséglet függ attól, hogy az országok különálló részekből állnak-e vagy sem. Felmerülhet a kérdés: vajon akkor is akármilyen sok szín szükséges a térképek jó színezéséhez, ha az országok nem akármilyen sok különálló részből állnak?

A 13. ábrán olyan térképet láthatunk, amelyen 12 ország van, minden ország két különálló részből áll (az azonos országokhoz tartozó részeket azonos számmal láttuk el), és az országok mind páronként szomszédosak. Ennek a térképnek a jó színezéséhez nyilván 12 szín szükséges. Másrészt sikerült bebizonyítani, hogy 12 színnel minden olyan térkép jól színezhető, amelyen minden ország legfeljebb két különálló részből áll.

Érdekes, hogy e bonyolultabb feladatot sikerült teljesen megoldani. Megoldatlan még az a kérdés, amelynél megengedünk a térképen kettőnél több különálló részből álló országot is.