फिलिप हॉल (११ एप्रिल १९०४ – ३० डिसेंबर १९८२) या इंग्लिश गणितज्ञाचे मुख्य कार्य गट सिद्धांत (Group Theory) या विषयात आणि त्यातही विशेषतः सांत संच (Finite Set) आणि उकलक्षम गट (Solvable Groups) क्षेत्रात होते. सांत संचांवर काम करताना १९३५ मध्ये त्यांनी ‘विवाह प्रमेय’ सिद्ध केले.
या प्रमेयाचे सूत्र समचय सिद्धांत (Combinatorics) आणि आलेख सिद्धांत (Graph Theory) असे दोन प्रकारे पाहता येते. समचय सिद्धांतानुसार मर्यादित संचाच्या संग्रहातून वेगवेगळे घटक (Distinct Elements) निवडण्यासाठी हे सूत्र वापरले जाते. तर आलेख सिद्धांतानुसार द्विभाजिय आलेखामध्ये सुजोड शोधण्यासाठी हे ‘विवाह प्रमेय’ वापरले जाते. कोनिग्झबर्गच्या सात पुलांचे कोडे सोडवताना १७३६ मध्ये लेनार्ड ऑयलर यांनी आलेख सिद्धांताचा पाया रचला.
विवाह प्रमेय समजण्यासाठी आलेख सिद्धांतामधील काही संज्ञा समजून घेणे गरजेचे आहे.
द्विभाजिय आलेख (Bipartite Graph) : दिलेल्या आलेखाला दोन भागांमध्ये अशाप्रकारे विभाजित करता येत असेल, की आलेखातील प्रत्येक रेषाखंड एका विभागातील बिंदू दुसऱ्या विभागातील बिंदुला जोडत असेल तर त्या आलेखाला ‘द्विभाजिय आलेख’ असे म्हणतात. आ. 1 मधील आलेख हा द्विभाजिय आलेखाचे उदाहरण आहे. हा आलेख U आणि V या दोन भागांत विभागला गेला आहे आणि यातील प्रत्येक रेषाखंड U मधील बिंदूला V मधील बिंदूशी जोडतो.
सुजोड / जुळवणी (Matching) : जर दोन रेषाखंडांच्या मध्ये सामायिक बिंदू असेल तर त्या रेषाखंडांना ‘शेजारी रेषाखंड’ म्हणतात. दिलेल्या आकृती क्र. 1 च्या आलेखात शेजारी-शेजारी (adjacent) नसलेल्या रेषाखंडांच्या संचाला ‘सुजोड’ म्हणतात. आ.2 मध्ये लाल रंगाने दाखवलेल्या रेषांखंडांचा संच { X-1, Y-2, Z-3} यातील रेषाखंड एकमेकांशेजारी नाहीत त्यामुळे हा संच सुजोड होईल. याच आलेखाचा आ.3 मध्ये लाल रेषांखंडांनी दाखवलेल्या रेषाखंडांचा संच { Y-1, Z-3, W-2} हा सुद्धा सुजोड होईल. एका आलेखात अनेक सुजोड असू शकतात.
द्विभाजिय आलेखातील एकाच संचामधील सर्व बिंदूना जर सुजोड संचातील रेषाखंड समाविष्ट करत असतील तर त्या सुजोडास ‘संपूर्ण सुजोड’ (Complete Matching) म्हणतात. आ.2 आणि आ.3 मध्ये {1, 2, 3} या संचातील सर्व बिंदू ‘सुजोड’ मध्ये समाविष्ट आहेत, त्यामुळे येथे ‘संपूर्ण सुजोड’ आहे. आलेखातील सर्व बिंदूना जर सुजोड संचातील रेषा समाविष्ट करत असतील तर अशा सुजोडास ‘परिपूर्ण सुजोड ’(Perfect Matching ) म्हणतात.
हॉलचे ‘विवाह‘ प्रमेय : समजा एक वधू-वर मेळावा आयोजित केला आहे. त्यासाठी विवाहेच्छुक स्त्री-पुरुष जमले आहेत. त्यातील प्रत्येक व्यक्ती स्वतःच्या पसंतीचे काही जोडीदार निवडते आणि आयोजकाला देते. आयोजकास यातील विवाहयोग्य जोड्या तयार करायच्या आहेत. आयोजक सगळी माहिती एकत्र करून परस्पर पसंतीचा एक तक्ता तयार करतात. यात जर A ला B पसंत असेल आणि B ला A पसंत असेल तरच त्यांची परस्पर जोडी तयार होईल. विवाहयोग्य जोडी बनण्यासाठी परस्पर पसंतीचा जोडीदार मिळणे गरजेचे आहे. तर प्रत्येक ‘स्त्रीस’ विवाह योग्य जोडीदार मिळणे शक्य आहे का?
यासाठी दिलेल्या संचांवर कुठल्या अटींची पूर्तता होणे आवश्यक आहे? असे प्रश्न विवाहाच्या प्रमेयाने सोडवले जातात. समजा मेळाव्यात विवाहेच्छुक असे 4 स्त्रिया व 4 पुरुष आहेत. स्त्रिया : { A, B, C, D } आणि पुरुष : {P, Q, R, S} असे दोन संच आहेत.त्यांच्या पसंतीची माहिती तक्ता क्र. 1 प्रमाणे आहे. ही माहिती आलेखाचा वापर करून आपण आ. 4 प्रमाणे दाखवू शकतो. यातील बिंदू हे स्त्री आणि पुरुष दर्शवितात तर रेषाखंड ‘परस्पर पसंतीचा जोडीदार’ दोन बिंदूत संबंध दर्शवितात.
या माहितीवरून आ. 5 प्रमाणे जोड्या लावता येतील. यानुसार A चे R शी, B चे Q शी, C चे P शी आणि D चे S शी लग्न होऊ शकते. अशा इतर प्रकारेही जोड्या शक्य आहेत. आ. 5 ‘परिपूर्ण सुजोड’चे उदाहरण आहे. समजा मेळाव्यात विवाहेच्छुक असे 4 स्त्रिया व 5 पुरुष आहेत. स्त्रिया : { A, B, C, D } आणि पुरुष : {P, Q, R, S, T} असे दोन संच आहेत. त्यांच्या पसंतीची माहिती तक्ता क्र. 2 प्रमाणे आहे. ही माहिती आलेखाचा वापर करून आपण आ.६ प्रमाणे दाखवू शकतो. यामध्ये लाल रेषेने लग्नायोग्य जोड्या दाखविलेल्या आहेत. हे ‘संपूर्ण सुजोड’चे उदाहरण आहे.
मात्र जर पसंतीची माहिती तक्ता क्र. 3 प्रमाणे असेल प्रत्येक स्त्रिला विवाह योग्य जोडीदार मिळणे शक्य नाही. कारण यात C आणि D याची पसंती एकाच पुरुषाची आहे त्यामुळे यातील एक स्त्री जोडीदाराशिवाय राहील. ही माहिती, आलेखाचा वापर करून आ. 7 प्रमाणे दाखवता येते. यामध्ये लाल रेषाखंडांने ‘सुजोड’ दाखवले आहेत. येथे D ला पसंतीचा जोडीदार मिळत नाही.
वरील उदाहरणानुसार प्रत्येक स्त्रीस विवाहयोग्य पुरुष मिळण्यासाठी स्त्रियांच्या संचावरील काही अटी पूर्ण होणे गरजेचे असते. त्याविषयीचे प्रमेय हे ‘हॉलचे विवाह प्रमेय’ म्हणून ओळखले जाते. या प्रमेयानुसार जर विवाहेच्छुक स्त्री आणि पुरुष यांची संख्या समान असेल आणि प्रत्येक ‘क’ स्त्रियांच्या परस्पर पसंतीचे किमान ‘क’ पुरुष असतील तर आणि तरच प्रत्येक स्त्रीस विवाहयोग्य जोडीदार मिळेल. या अटीस ‘विवाह अट’ (Marriage Condition) असेही म्हणतात.
तक्ता क्र. 1 मध्ये वरील अटीची पूर्तता होते मात्र तक्ता 3 मध्ये {C, D} या दोन स्त्रियांसाठी {S} हा एकच पुरुष आहे त्यामुळे वरील अटीची पूर्तता होत नाही. यावरून असे म्हणता येईल की प्रत्येक स्त्रीस जर जोडीदार मिळत असेल तर तिथे ‘संपूर्ण सुजोड’ होते. यामध्ये काही पुरुष जोडीदाराशिवाय राहतील. जर प्रत्येक स्त्रीस आणि पुरुषास जर जोडीदार मिळत असेल तर ‘परिपूर्ण सुजोड’ होते. यामध्ये प्रत्येकास जोडीदार मिळेल.
आलेख सिद्धांतानुसार ‘विवाह प्रमेय’ पुढीलप्रमाणे देता येईल. समजा G हा द्विभाजिय आलेख U आणि V या दोन संचात विभागला आहे आणि V मध्ये U इतकेच अथवा जास्त बिंदू आहेत. जर U मधील प्रत्येक ‘क’ बिंदू V मधील किमान ‘क’ बिंदूंशी जोडलेले असतील तर आणि तरच G मध्ये संपूर्ण सुजोड आहे असे म्हणतात. या व्याख्येत समजा U आणि V मध्ये समान संख्येने बिंदू असतील तर तिथे परिपूर्ण सुजोड होईल.
दैनंदिन जीवनातील वेळापत्रक नियोजन, कामाचे वाटप यासारख्या कामांसाठी आलेख सिद्धांतातील जुळवणीचा वापर होतच असतो. संजालाशी निगडित प्रश्नांनासाठी आलेख सिद्धांतातील गणिती प्रारूपांचा वापरहोतो. यात वीज पुरवठा, पाणी पुरवठा, वाहतूक व्यवस्था अशासारख्या प्रवाह संजालाशी (Flow Network) संबंधित प्रश्न सोडवण्यासाठी आणि कृत्रिम बुद्धिमत्तेमधील तांत्रिक संजालामध्येही (Neural Network) जुळवणीचा वापर होतो.
संदर्भ :
- Gary Chartrand, Introductory Graph Theory, (1984).
- Robin J. Wilson, Introduction to Graph Theory, Fourth Edition (1996).
- Wikipedia, Matchings, Perfect Matchings, Philip Hall.
समीक्षक : शरद साने
