ग्राफ़ सिद्धान्त

गणित तथा संगणक विज्ञान में ग्राफ सिद्धांत (graph theory) में वस्तुओं से जुड़ी वस्तुओं और उनकी आपसी दूरी का अध्ययन किया जाता है। इस संदर्भ में ग्राफ उन गणितीय संरचनाओं को कहते हैं जो वस्तुओं के बीच जुड़े या युग्मित संबन्धों (pairwise relations) को मॉडल करने के काम आती हैं। इसकी तुलना किसी मानचित्र में शहरों के बीच बने सड़कों के जाल से कर सकते हैं। दो शहरों के बीच की दूरी उनके बीच बनी सड़क की लंबाई बताती है। यदि उन शहरों से बीच सीधी सड़क न हो, तो किसी अन्य शहर द्वारा वहाँ तक पहुँचने की दूरी निकाली जा सकती है।

एक ग्राफ जिसमें छः नोड और सात कोर हैं।

इसके आरेखों और चित्रों में दर्शाने के लिए वस्तुओं को बिन्दु या गोले (node, vertex) से दर्शाया जाता है। इनके बीच के जुड़ाव को एक रेख द्वारा जिसे कोर (edges) कहते हैं। अतः ग्राफ शीर्षों (vertices or nodes) तथा उनको जोड़ने वाली कोरों (edges) का समुच्चय है। विविक्त गणित (discrete mathematics) में ग्राफ का अध्ययन एक महत्वपूर्ण विषय है।

ध्यान रहे कि 'ग्राफ सिद्धान्त' का 'ग्राफ', फलनों के आलेख (ग्राफ) यानि वक्र रेखा द्वारा किसी संबंध को दिखाने से बिलकुल भिन्न चीज है। ग्राफ़ सिद्धांत का प्रयोग वस्तुओं के विशाल समूह में एक दूसरे से दूरी (या अन्तर) निकालने के लिए किया जाता है। ग्राफ़ सिद्धांत के अनुसार, इसी प्रकार आकड़ों के पुंजीकरण, वस्तुओं की समरूपता इत्यादि जैसे कार्यों का हल निकाला जा सकता है।

सामान्यतया ग्राफ़ को G=(V,E) से व्यक्त किया जाता है। यहाँ V बिन्दुओ यानि वस्तुओं का संग्रह है और E उनके बीच बने जोड़ों (कोर) का। ध्यान दीजिये कि एक ग्राफ़ में सभी बिन्दु एक दूसरे से जुड़े नहीं होते। केवल कुछ ही एक दूसरे से सीधे तौर पर जुड़े होते हैं। जैसे उपर दिये गए आरेख में बिन्दु २ और बिन्दु ६ के बीच कोई सीधा संबंध नहीं है।

बाहरी कड़ियाँ

आनलाइन पुस्तकें

• Graph Theory with Applications (1976) by Bondy and Murty
• Digraphs: Theory Algorithms and Applications 2007 by Jorgen Bang-Jensen and Gregory Gutin
• Graph Theory, by Reinhard Diestel

अन्य स्रोत

• Graph theory tutorial
• A searchable database of small connected graphs
• Concise, annotated list of graph theory resources for researchers
• rocs - a graph theory IDE
• Graph Theory Software