Monday, April 19, 2010

एक मानचित्र में कितने रंग?

कभी आपने सोचा है एक रंगीन नक्शे (मानचित्र) में कितने तरह के रंग प्रयोग किए जाते हैं? वैसे तो चाहे जितनी मर्जी इस्तेमाल किए जा सकते हैं लेकिन 1852 में एक नक्शे को रंगते हुए फ्रांसिस गुथरिए नामक एक वनस्पतिशास्त्री और गणितज्ञ के दिमाग में ये सवाल आया कि कम से कम कितने रंगों के इस्तेमाल से कोई भी नक्शा बनाया जा सकता है ताकि कोई भी दो पड़ोसी देशो को एक ही रंग में ना रंगना पड़े? देशों के आकार-प्रकार और हर देश के लिए पड़ोसी देशों की संख्या जो भी हो उन्होने अटकलबाजी करते हुए एक अनुमान लगाया कि इस सवाल का उत्तर चार रंग है. और चार रंग ही पर्याप्त हैं ऐसे किसी भी नक्शे को बनाने के लिए. इस अनुमान ने चार रंगों वाले कंजेक्चर को जन्म दिया.

गणित में अटकलबाजी का बड़ा महत्त्वपूर्ण स्थान है. अनुमान, अनुभव और अंतर्ज्ञान के आधार पर गणितज्ञ कोई बात कह देते हैं. जब तक ये बात सही या गलत सिद्ध नहीं हो जाती तब तक इसे अटकलबाजी ही तो कहेंगे ! तो इन्हें तब तक कंजेक्चर कहा जाता है, सिद्ध हो जाने के बाद ये कंजेक्चर प्रमेय हो जाते हैं.

फ्रांसिस के अनुमान के बाद सौ वर्षों से अधिक तक यह सवाल अनुमान ही बना रहा. चार रंग वाले सवाल (फोर कलर प्रोबलम) के नाम से प्रसिद्ध यह टोपोलोजी के सबसे प्रसिद्ध और ऐतिहासिक सवालों में से एक है. बाकी सवालों की ही तरह इसे भी हल करने के प्रयास होते रहे और कई लोगों ने इसे साबित भी कर दिखाया. इन कई लोगों के प्रमाण कई वर्षों तक मान्य भी रहे. पर कुछ सालों बाद इनमें गलतियाँ ढूँढ ली गयी. ऐसे ही एक प्रमाण को गलत साबित करते हुए 1890 में पार्सि जॉन हेवूड ने एक नया सिद्धांत दिया जिसमें उन्होने यह साबित किया कि पाँच रंगों से ऐसे नक्शे बनाना संभव है. पर वो ये नहीं दिखा सके कि चार रंगों में ही संभव है या नहीं ! तो मूल सवाल अभी भी  बना रहा.

इस सिलसिले में ग्राफ थियरि और टोपोलोजी का खूब विकास हुआ. ग्राफ रंगने से जुड़े अनगिनत सिद्धांत और सवालों का जन्म हुआ. ग्राफ थियरि में इस सवाल को इस तरह देखा जाता है: हर देश को एक बिन्दु से निरूपित किया जाता है और हर पड़ोसी देश को एक रेखा से जोड़ दिया जाता है. फिर सवाल ये हो गया कि कितने रंग चाहिए जिससे एक रेखा से जुड़े कोई भी दो बिन्दु एक ही रंग में ना रंगे हो? वैसे तो लगता है... ठीक है रोचक सवाल है. लेकिन इसका क्या उपयोग है? इस सवाल का बड़ा व्यापक उपयोग है... जैसे टेलीकॉम कंपनियां अपना नेटवर्क डिजाइन करते समय इसका इस्तेमाल कुछ इस तरीके से करती हैं: कम से कम कितने ट्रांसमीटर में काम हो जायेगा और फिर उतने ट्रांसमीटर से नेटवर्क डिजाइन कैसे किया जाय?

हाँ तो ये रंगों का सवाल कंजेक्चर बना रहा और अंततः 1976 में इलियोनोई विश्वविद्यालय के वोल्फगैंग हेकेन और केनेथ एपेल ने घोषणा की ये चार रंगों वाला सवाल अब चार रंगों वाले प्रमेय के नाम से जाना जायेगा. यानि उन्होने इस कंजेक्चर को सिद्ध कर देने की घोषणा की. पर समस्या अभी गयी नहीं और इस हल ने एक नए विवाद को जन्म दिया. कई गणितज्ञों ने इस हल को मानने से इंकार कर दिया. इस हल में गणित के अलावा कंप्यूटर की मदद ली गयी. इस सवाल को हल करते हुए अंत में 1476 ऐसी अवस्थाएँ बची जिन्हें अगर एक-एक करके जाँच लिया जाय तो ये हल पूर्ण हो जाता. लेकिन इस जाँच में इतनी गणनाएँ थी कि इन्हें कागज-कलम और इंसानी दिमाग-समय में करना असंभव था. दोनों गणितज्ञों ने इस हिस्से को कम्प्युटर जनित अलगोरिथ्म्स से जाँच लिया (कम्प्युटर पर भी इन्हें जाँचने में हजारो घंटे लगे). पर कुछ गणितज्ञों की आपत्ति थी कि अगर कुछ गणनाओं में कहीं कोई गलती हुई तो? पर यह लगभग मान लिया गया कि फ्रांसिस का अनुमान सही था और चार रंग ही पर्याप्त हैं.  तब से अब तक कई परिष्कृत प्रमाण दिये गए इस सवाल के. 2005 में माइक्रोसॉफ़्ट के जोर्जेस गोथिएर और इनरिया के बेंजामिन वर्नर ने इस प्रमेय का एक नया प्रमाण दिया पर वह भी कम्प्युटर आधारित ही है. पर इस प्रमाण में एक-एक करके जाँचने वाला चरण नहीं है. यह प्रमाण फंकशनल प्रोग्रामिंग लैंगवेज़ और कैलकुलस ऑफ इंडक्टिव कंस्ट्रक्शन पर आधारित इंटरैक्टिव थियोरम प्रूवर पर आधारित है.

बिना कम्प्युटर की मदद के इस प्रमेय का अभी भी कोई प्रमाण नहीं है. इस प्रमेय के हल के बाद कम्प्युटर वाली पद्धति का और भी कुछ सवालों के हल में इस्तेमाल हुआ है. वैसे ये पद्धति अभी भी विवादास्पद बनी हुई है !

April fool 5 color mapइस सवाल से जुड़ी कई रोचक बातों में से एक यह भी है: 1975 में मार्टिन गार्डनर  ने अप्रैल फूल जोक के रूप में एक 110 देशों का यह काल्पनिक मानचित्र बनाकर यह कहा कि इस मानचित्र के लिए 5 रंगों की आवश्यकता पड़ेगी और इस तरह चार रंगों वाला कंजेक्चर ही गलत है. पर बाद में यह दिखा दिया गया कि इस मानचित्र को भी 4 रंगों से रंगा जा सकता है.

~Abhishek Ojha~

--

इस पोस्ट के लिए उन्मुक्तजी का धन्यवाद. उन्होने पिछली पोस्ट पर की गयी टिपण्णी में इस सवाल पर लिखने का सुझाव दिया था.

Tuesday, March 23, 2010

कोनिसबर्ग के पुलों वाली पहेली और टोपोलोजी की शुरुआत

कोनिसबर्ग के पुलों वाली पहेली एक सरल और रोचक ऐतिहासिक पहेली है. ये गणित की उन पहेलियों में से है जिन्हें समझना बिल्कुल ही आसान था, पर हल करना थोड़ा मुश्किल. कहते हैं टोपोलोजी की विचारधारा का जन्म इसी पहेली से हुआ. यह पहला सवाल हैं जहाँ पर टोपोलोजी के निशान देखे जा सकते हैं. यही नहीं गणित (और कम्प्युटर साइन्स) की एक प्रसिद्ध शाखा ग्राफ थियरि का विकास भी इसी पहेली से शुरू हुआ. तब जर्मनी के कोनिसबर्ग शहर जो अब कालीनीनग्राद  के नाम सेजाना जाता है और अब रूस में स्थित है के प्रेगेल नदी से बने द्वीप और नदी पर बने सात पुलों ने एक पहेली को जन्म दिया. हालांकि द्वितीय विश्व युद्ध में इनमें से दो पुल ध्वस्त हो गए और उन पुलों में से अब बस पाँच (इन पाँच में से दो पुल उस समय के हैं, बाकी फिर से बनाये गए हैं) बचे हैं. कोनिसबर्ग के तब की तस्वीर का रेखाचित्र और अब के गूगल अर्थ की तस्वीर से तुलना की जा सकती है.

 image  Konigsberg

कोनिसबर्ग तब व्यापार का केंद्र हुआ करता और ये पुल शहर के अलग-अलग हिस्सों में जाने के लिए इस्तेमाल किए जाते. कोनिसबर्ग के किसी घुमंतू खुराफाती व्यक्ति के दिमाग में ये सवाल आया कि क्या किसी एक जगह से शुरू होने वाली ऐसी यात्रा संभव है जिसमें एक ही यात्रा में इन सातों पुलों को एक और बस एक ही बार पार किया जाय और उस जगह पर वापस आया जाय जहाँ से यात्रा शुरू की गयी थी. ना तो किसी पुल को दुबारा पार करना पड़े और ना ही आधा.

अब पहेली तो बन गयी पर ऐसा रास्ता कोई नहीं ढूँढ पाया. ना ही कोई ये सिद्ध कर पाता कि ऐसा संभव नहीं है. अगर आपको याद हो तो बचपन में हमसे भी कुछ होशियार बच्चे कहते कि बिना कलम उठाये एक विकर्ण सहित वर्ग बनाकर दिखाओ. अब बनाने की कोशिश तो हम सभी करते और अंत में कहते नहीं हो रहा ! कुछ ऐसी ही हालत कुछ वर्षों तक  रही होगी कोनिसबर्ग में भी. फिर किसी ने 1736 में ये पहेली तब के प्रसिद्ध गणितज्ञ ओयलर को लिख भेजा. ओयलर सेंट पिटसबर्ग में रहते थे. और उस समय गणित के अलावा यांत्रिकी, भौतिकी और खगोलीय विषयों पर भी काम करते थे. अब इतने मशहूर व्यक्ति थे तो जाहिर है व्यस्त भी रहते थे. कहते हैं उस दौरान वो औसतन सप्ताह में एक शोध पत्र छापा करते. ओयलर को ये सवाल पहले तो बहुत हल्का और बेकार सा लगा पर फिर उन्होने स्वयं एक पत्र में लिखा 'ये मामूली सा सवाल है पर फिर भी मुझे यह समय व्यतीत करने लायक लगा क्योंकि ज्यामिति, बीज गणित और अंक गणित से इसे हल कर पाना संभव नहीं लगता. ' ओयलर ने इस सवाल को व्यापक बनाकर हल किया और यह दिखाया कि किन हालतों में (कितने पुल हो तो) ऐसी यात्रा संभव है. उन्होने यह भी दिखाया कि 7 पुल वाले  मामले में ऐसी यात्रा संभव नहीं.
गौर करने की बात ये है कि इस पहेली में कौन सा पुल किस से कितनी दूरी पर है और किस पुल की लम्बाई कितनी है यह मायने नहीं रखता. संभवतः गणित का यह पहला ऐसा सवाल था जिसमें ज्यामिति जैसी स्थिति होते हुए भी नापने या अंकों की बात ही नहीं थी ! साथ ही यह भी मायने नहीं रखता था कि एक पुल से दूसरे पुल तक जाने का रास्ता सीधा था या टेढ़ा-मेढ़ा. ओयलर ने इसे ग्राफ थियरि से हल किया, इसे हल करने के सिलसिले ने ही ग्राफ थियरि को जन्म दिया और फिर आगे चल कर इन अवधारणाओं पर ही टोपोलोजी का जन्म हुआ. बाद के मशहूर ट्रावेलिंग सेल्समैन जैसे सवाल भी एक तरह से इसी श्रेणी में आते हैं. टोपोलोजी में एक जैसे सवालों/वस्तुओं/समुच्चयों का एक समूह होता है. जैसे यहाँ एक जगह से दूसरी जगह जाने के रास्ते के बीच की दूरी और सीधा-टेढ़ा होना माने नहीं रखता वैसे ही वहाँ एक गोले और घन में फर्क नहीं होता क्योंकि एक को पीटकर दूसरा बनाया जा सकता है. टोपोलोजी के इस सिद्धांत की चर्चा अगले पोस्ट में. 
गूगल ने इस प्रसिद्ध पहेली से जुड़ी प्रेगेल नदी के नाम पर ही अपने एक ग्राफ कम्प्यूटिंग का नाम प्रेगेल रखा है.
और ये रही ओयलर के आरिजिनल पेपर से एक तस्वीर:  image



__________________________________________
पोस्टोपरांत अपडेट: (अभय तिवारी जी की टिपण्णी के बाद)
ओयलर का हल:
ओयलर ने इस पहेली को ग्राफ में परिवर्तित किया और जैसा कि मैंने ऊपर कहा इस ग्राफ में रेखाओं का सीधा-टेढ़ा होना और बिन्दुओं के बीच की दुरी मायने नहीं रखती. इस ग्राफ में बिंदु जमीन और सात रेखाएं सात पुलों को दर्शाती हैं. ओयलर ने कहा कि पहेली के हिसाब से अगर एक रास्ता ढूँढना है तो यात्रा करते समय बीच में आने वाले सारे बिन्दुओं पर एक आने का और एक जाने का रास्ता होना चाहिए. इस हिसाब से सारे बिन्दुओं पर रेखाओं की संख्या सम होनी चाहिए. केवल २ बिन्दुओं पर जहाँ से यात्रा शुरू हो और जहाँ ख़त्म हो केवल वहीँ विषम संख्या में रेखाएं हो सकती है. और अगर यात्रा जहाँ से शुरू करनी है वहीँ ख़त्म भी तो फिर सारे ही बिंदुओं पर रेखाओं की संख्या सम होनी चाहिए. पर इस ग्राफ में सभी बिन्दुओं पर विषम संख्या में रेखाएं हैं (३ और ५). इसलिए पहेली के हिसाब से यात्रा संभव नहीं है !
__________________________________________


~Abhishek Ojha~

Monday, March 8, 2010

एलिस इन वंडरलैंड और गणित ?

टीम बर्टन की जॉनी डेप अभिनीत फिल्म 'एलिस इन वंडरलैंड' रिलीज हो गयी है और मुझे इंतज़ार है इसके पुणे में रिलीज होने का. फ़िलहाल सोने के पहले इस फिल्म से जुडी न्यूयोर्क  टाइम्स  में छपे इस आलेख पर नजर पड़ गयी. 'एलिस इन वंडरलैंड' के लेखक का गणितज्ञ होना और उनके जीवन काल में हो रहे गणितalice_in_wonderland में परिवर्तनों का इस पुस्तक पर असर होने की सोच बड़ी कमाल की लगी कहाँ गणित और कहाँ एलिस इन वंडरलैंड !  दो अलग ही बातों की तुलना बड़े अच्छे ढंग से की गयी है.
नए गणित और उसके आविष्कार के इतिहास में अगर रूचि ना भी हो तो ये आलेख पढने लायक है. कैसे हम जो भी लिखते(सोचते) हैं वो कहीं न कहीं हमारे परिवेश और हमारे अब तक के जीवन तथा कार्यक्षेत्र से प्रभावित होता है. भले ही देखने में बिलकुल हमारे कार्यक्षेत्र से अलग हो पर सोच कहीं न कहीं उससे प्रभावित तो होती ही है. जिस क्षेत्र में और जिस तरीके से हम काम कर रहे होते हैं (या करना पड़ता है) धीरे-धीरे उस तरीके से सोचने लगते हैं. आप आलेख लिंक पर  पढ़कर आईये. घंटे भर लगाकर टाइप और ट्रांसलेशन का कुछ फायदा नहीं दीखता मुझे.

Algebra in Wonderland

दसवीं क्लास में एक श्लोक पढ़ा था, बाबा चाणक्य सही ही कह गए हैं:

दीपो भक्षयते थ्वान्तं काजलं च प्रसूयते.
यदन्नं भक्षयते नित्यं जायते तादृशी प्रजा.

जिस प्रकार दीपक अन्धकार को खाकर काजल को जन्म देता है उसी तरह इंसान के विचार भी वैसे ही होते हैं जिस प्रकार का अन्न वह खाता है और उसकी संतानें भी वैसी ही पैदा होती हैं.
अब यहाँ अन्न का मतलब डायरेक्ट अन्न ही तो नहीं है (विशेषज्ञ बतायेंगे कुछ)? हाँ उस जमाने में अन्न कमाने के लिए जिस तरह के काम किये जाते हो उसी काम की बात बाबा चाणक्य कर रहे थे होंगे*. मतलब जो काम करो, जैसा पढो, जैसे लोगों के साथ रहो वैसे ही विचार होंगे. अपनी सोच ऐसे ही तो बनती है. जीवन में साथ मिले/रहे लोग, घटनाएं, काम एक बड़ा प्रतिशत बनाते हैं हमारी पर्सनालिटी का.  मुझसे किसी ने कहा तुम्हें सीधे-सीधे बात करनी ही नहीं आती. एक सीधी बात समझाने के लिए ऐसे उदहारण देते हो कि बात सुलझने के वजाय उलझ ही जाती है. [वैसे ये बात इसलिए भी कही गयी होगी क्योंकि सामने वाले को कुछ सीधे-सीधे सुनना होगा मेरे मुंह से ;) जो मैं कह ना पा रहा था होऊंगा*].

*हमारे इतिहास के शिक्षक प्रागैतिहासिक काल का इतिहास पढ़ाते समय 'थे होंगे' का बहुत इस्तेमाल किया करते थे, मुझे बड़ा अच्छा लगा करता था !
आप आलेख पढने जाइए, फुर्सत मिले तो उस पर सोचियेगा, अपने से जोड़कर... मजा आएगा :)

~Abhishek Ojha~

Thursday, January 28, 2010

ये क्या उपयोग हुआ?

टोपोलोजी शुद्ध गणित का एक विशुद्ध टाइप का ब्रांच होता है. एकदम अमूर्त... वो गणित जो बस इसलिये पढ़ा-पढ़ाया और विकसित किया जाता है क्योंकि बस गणित है. सालों तक कोई उपयोग या वास्तविक जीवन से जोड़कर नहीं देखा गया. ऐसे में अगर कोई पूछ ले: टोपोलोजी का उपयोग क्या है? तो ये सवाल बड़ा कठिन हो जाता है. अगर आपसे कोई पूछे कि अंकगणित का क्या उपयोग है, त्रिकोणमिति का क्या उपयोग है या फिर ज्यामिति का क्या उपयोग है तो झट से कुछ चित्र  दिमाग में आते हैं. कुछ कोण, क्षेत्रफल, खगोल, गति, दूरी, ऊँचाई... इत्यादि. लेकिन टोपोलोजी का प्रत्यक्ष उपयोग देखने को नहीं मिलता और सीधा-सीधा उपयोग बता पाना थोड़ा मुश्किल है क्योंकि ऐसा उपयोग है ही नहीं. वैसे धीरे-धीरे टोपोलोजी के सिद्धांतों के कई उपयोग होने लगे हैं. इस ज्यामितीय सोच से कई बातों को समझने में सुविधा हुई है.

अगर कोई उत्सुक व्यक्ति गणित की अन्य शाखाओं के उपयोग के बारे में जानना चाहे तो उसे कोई वस्तु या कोई चित्र बनाकर संतुष्ट किया जा सकता है. अगर किसी टोपोलोजिस्ट से पूछा जाय तो वो भी शायद एक कैंची और कागज की सहायता से मोबियस स्ट्रिप (पट्टी) बना कर दिखा सकता है. उस पट्टी को Mobius stripRecycling Symbol काटकर और क्या बनाया जा सकता है ये भी दिखा सकता है. हाँ ये बात अलग है कि किसी भी सामान्य व्यक्ति का अगला सवाल ये होगा कि इस स्ट्रिप का अब मैं क्या करूँ? मोबियस स्ट्रिप एक ही सतह की ऐसी पट्टी होती है जिसपर अगर आप एक बिन्दु से चलना चालू करें तो उस पट्टी के हर भाग से घूमकर वापस उसी बिन्दु पर वापस आ सकते हैं बिना कभी किनारे को पार किए ! इस लिंक पर आप चींटियों का मोबियस स्ट्रिप पर चलना देख सकते हैं.  इस स्ट्रिप की तर्ज पर ही एक क्लाइन बोतल भी होती है. घूम-फिर के वापस वहीं पर आ जाने वाली बात के चलते रिसाइक्लिंग का संकेत मोबियस स्ट्रिप पर आधारित होता है.

एक टोपोलोजिस्ट आपको एक धागे कि मदद से ये भी दिखा सकता है कि कैसे तीन छल्लों को आपस में इस तरह जोड़ा जा सकता है जबकि कोई भी दो आपस में ना जुड़े हो ! (बोरोमीयन रिंगस). अगर वो कुछ और उपयोग दिखाना चाहे तो कुछ पार्लर ट्रिक भी दिखा सकता है. जैसे बिना कोट उतारे अंदर के अँगरखे को उतरना borromean rings संभव है या नहीं ! अगर पक्का टोपोलोजिस्ट हुआ तो ट्रिक तो दिखाने से रहा... कागज पर इस ट्रिक के पीछे का गणित घंटों तक जरूर लिख सकता है.

पर ये उपयोग टोपोलोजी के उपयोग का कार्टून बनाने की तरह है. इसके असली उपयोग गणितीय ही होते हैं. इन उपयोगों से मुझे अपने एक गणित के प्रोफेसर साहब याद आते हैं. वो कहते कि मैं घर बैठे अपने दोस्त के साथ या अकेले भी बैंडमिंटन खेल लेता हूँ ! हाथ में कागज और पेंसिल लेकर. मुझे इसके लिए न तो कोर्ट जाने की जरूरत पड़ती है ना भाग-दौड़ ही. लेकिन अगर कागज पर बैडमिंटन के समीकरण लिखे जायें तो इसे बैडमिंटन खेलना तो नहीं कह सकते न? ठीक इसी तरह ऊपर जो उपयोग मैंने बताये वो किसी तरह टोपोलोजी के कुछ वास्तविक उपयोग ढूँढने के प्रयास भर हैं.

पार्लर ट्रिक वाला उदाहरण थोड़ा बेहतर है. कुछ भी संभव है या नहीं? इस सवाल/प्रक्रिया को गणितीय/ज्यामितीय रूप में लिखकर फिर हाँ या ना में उत्तर निकालना... टोपोलोजी का एक अच्छा उपयोग है.

टोपोलोजी की बाकी कड़ियाँ:

टोपोलोजी और फक्का !
बंद भी खुला भी !

~Abhishek Ojha~