चार रंगांची समस्या

चार रंगांची समस्या  किंवा  four colour problem   ही समस्या रंगांची नसून रंगवण्याची आहे. शिवाय रंगवण्याची समस्या असली तरी रंगकामातली समस्या नाही! ही समस्या गणितातील आहे. ही समस्या आहे तरी काय?

नकाशे हा प्रकार आपल्याला नवीन नाही. जगाचा नकाशा, भारताचा नकाशा, महाराष्ट्राचा नकाशा हे आपण सर्वांनी पाहिलेले आहेत. नकाशातील निरनिराळे विभाग वेगळे कळावे यासाठी ते वेगवेगळ्या रंगात रंगवलेले असतात. आता महाराष्ट्राचाच नकाशा घ्या. महाराष्ट्रात ३४ जिल्हे आहेत. कधी आपण बारकाईने पाहिले आहे का की हे जिल्हे दर्शविण्यासाठी किती रंग वापरलेले आहेत? ३४ जिल्ह्यांसाठी ३४ वेगवेगळे रंग तर नक्कीच नाहीत. तर किती रंग वापरले आहेत? कमीतकमी किती रंग वापरावे लागतील? चार रंगांची समस्या ढोबळमानाने ही समस्या आहे.

पुढे जाण्यापूर्वी एक गोष्ट स्पष्ट करणे जरूरीचे आहे. ह्या प्रश्नात लागणारे कमीत कमी रंग आणि चित्रकलेतील मूळ रंग - लाल, पिवळा, निळा किंवा तंत्रविज्ञानातील मूळ रंग - आर बी जी (रेड, ब्लू, ग्रीन) ह्यांची गल्लत करू नये. रंगांच्या अनेक छटा कशा तयार होतात हा आपला सध्याचा प्रश्न नाही. कोणत्यातरी प्रकाराने बनवून आपल्याला बरेच रंग दिलेले आहेत. त्यापैकी आपण कमीत कमी किती वापरणार हा प्रश्न आहे.

सर्वांना समजण्यासाठी सोप्या भाषेत ही समस्या अशीही सांगतात की जगाचा नकाशात निरनिराळे देश दाखवण्यासाठी कमीत कमी किती रंग लागतील. आता असे म्हटल्यावर लगेच कोणीतरी विचारेल की जग म्हणजे पूर्व आणि पश्चिम जर्मनी एक व्हायच्या आधीचं का नंतरचं? भारताच्या फाळणीच्या आधीचं का नंतरचं? तर ह्या गोष्टींचा ह्या समस्येशी काही संबंध नाही. एकूणच आंतरराष्ट्रीय राजकारणाचा ह्या समस्येवर काही परिणाम होणार नाही. रशिया एकसंध होता आणि नंतर त्याची शकलं झाली त्याने ह्या समस्येचे रूप बदलले नाही. गणिती भाषेत ही समस्या सांगितली तर हे स्पष्ट होईल.

एखाद्या सपाट पृष्टभागावर निरनिराळे विभाग केलेले आहेत तर ते सर्व विभाग रंगवण्यासाठी कमीत कमी किती रंग लागतील? दिलेल्या अटी : १. दोन शेजारशेजारच्या विभागांचा रंग सारखा असता कामा नये. २. दोन विभागांना समाईक सीमारेषा असेल तरच ते शेजारशेजारचे म्हटले जातील, जर एकच बिंदू समाईक असेल तर ते विभाग शेजारशेजारचे नाहीत. (आकृती पहा. १ व २ ह्या विभागांत एक बिंदू समाईक आहे म्हणून त्यांना एकाच रंगात रंगवून चाललेले आहे. तसेच ३ व ४ ह्या विभागांचेही आहे.) ३. प्रत्येक विभाग हा सलग असला पाहिजे. (म्हणजे जगाच्या नकाशात प्रत्येक देश हा एकेक विभाग असे मानले तर अंदमान, निकोबार बेटे हा भारताचा भाग असला तरी ती भारताशी जोडलेली नाहीत म्हणून ते वेगवेगळे विभाग धरले जातील.)

हा प्रश्न प्रथम १८५२ मध्ये मांडला गेला. लंडनच्या युनिव्हर्सिटी कॉलेजमधील एक विद्यार्थी Francis Guthrie याला असे आढळले की सर्वसाधारणपणे नकाशातील वेगवेगळे विभाग दाखवायला चाराहून जास्त रंग लागत नाहीत. त्याने आपले गुरु द मॉर्गन यांना आपले हे निरीक्षण सांगितले. त्यानंतर त्यावर बऱ्याच लोकांनी काम केले पण त्यांना यश मिळाले नाही. एकोणीसशे सत्तरच्या दशकाच्या पूर्वार्धापर्यंत, "ह्या कामासाठी ३ रंग कमी पडतात आणि ५ रंगात काम भागते" इथपर्यंत सिद्ध झाले होते. पण चार रंग पुरतील असे काही निश्चितपणे सांगता येत नव्हते.

१९७६ मध्ये अमेरिकेतील इलिनॉय विद्यापीठातील डब्लू. हेकन (W.Haken) व के. ऍपल (K.Appel) ह्या गणितज्ञांनी हे सिद्ध केले. हे करताना त्यांना जे. कोश (J.Koch) यांची मदत झाली.

हे त्यांनी कसे केले? सपाट पृष्ठभगावर काढता येणाऱ्या आणि वेगवेगळ्या प्रकाराने विभाजित असणाऱ्या नकाशांची संख्या तर प्रचंड असणार. परंतु ह्या दोघांनी गणिताच्या साहाय्याने -गणितातील टॉपॉलॉजी/ग्राफ थिअरी यांच्या साहाय्याने हे प्रस्थापित केले की हा नियम ह्या असंख्य नकाशांसाठी सिद्ध करण्याची आवश्यकता नाही. फक्त काही विशिष्ठ रचनांसाठी (configurations) हे सिद्ध करणे पुरेसे आहे आणि त्या विशिष्ठ रचनांची संख्या १९३६ आहे. (पुढे ही संख्या त्यांनी १४७६ पर्यंत कमी करत आणली.*) त्यापुढील काम म्हणजे ह्या रचनांना रंगवायला ४ रंग पुरतात की नाही हे तपासून पहाणे. हे काम त्यांनी संगणकाकडे सोपवले!

एखाद्या महत्त्वाच्या गणितीय प्रश्नासाठी संगणक वापरला जाण्याची ही पहिलीच वेळ होती. ह्यासाठी लिहिलेली आज्ञावली जवळजवळ १२०० तास 'रन' होत होती. अशा निरनिराळ्या आज्ञावल्यांच्या द्वारे ह्या तपासण्या स्वतंत्रपणे केल्या गेल्या आणि १९७६ मध्ये हा चार रंगांची समस्या सुटली असे म्हटले जाऊ लागले. परंतु काही गणितज्ञांच्या मते ही काही खऱ्या अर्थाने गणितीय सिद्धता नाही. त्यामुळे हा प्रश्न सुटला आहे असे मानायला ते तयार नव्हते. पण थोड्याच वर्षात अशी सिद्धता दिली गेली की ह्या मंडळींचेही समाधान झाले. आणि अनेक वर्षे गाजत असलेली "चार रंगांची समस्या" आता "चार रंगांचा सिद्धांत" म्हणून ओळखली जाऊ लागली.
--------------
* १९९४ मध्ये आणखी काही गणितज्ञांनी ही संख्या ६३३ पर्यंत खाली आणली.