Directed graph
गणित में, और विशेष रूप से ग्राफ सिद्धांत में, एक निर्देशित ग्राफ (या डिग्राफ) एक ग्राफ है जो निर्देशित किनारों से जुड़े शीर्षों के एक समूह से बना होता है, जिसे अक्सर चाप कहा जाता है। परिभाषा औपचारिक शब्दों में, एक निर्देशित ग्राफ एक क्रमबद्ध जोड़ी है जहाँ वी एक समूह है जिसके तत्वों को शीर्ष, नोड्स या बिंदु कहा जाता है; ए शीर्षों के क्रमबद्ध जोड़े का एक समूह है, जिसे चाप, निर्देशित किनारे (कभी-कभी केवल ए के बजाय ई नामक संबंधित सेट के साथ किनारे), तीर, या निर्देशित रेखाएँ कहा जाता है। यह एक साधारण या दिशाहीन ग्राफ से अलग है, जिसमें बाद वाले को शीर्षों के क्रमहीन जोड़े के संदर्भ में परिभाषित किया गया है, जिन्हें आमतौर पर किनारे, लिंक या रेखाएं कहा जाता है। उपरोक्त परिभाषा एक निर्देशित ग्राफ को एक ही स्रोत और लक्ष्य नोड्स के साथ कई तीर रखने की अनुमति नहीं देती है, लेकिन कुछ लेखक एक व्यापक परिभाषा पर विचार करते हैं जो निर्देशित ग्राफ को इस तरह के कई चाप रखने की अनुमति देता है (अर्थात्, वे चाप सेट को एक मल्टीसेट होने की अनुमति देते हैं)। कभी-कभी इन संस्थाओं को निर्देशित बहुलेखन (या बहुलेखन) कहा जाता है। दूसरी ओर, उपरोक्त परिभाषा एक निर्देशित ग्राफ को लूप होने की अनुमति देती है (यानी, चाप जो सीधे नोड्स को खुद से जोड़ते हैं), लेकिन कुछ लेखक एक संकीर्ण परिभाषा पर विचार करते हैं जो निर्देशित ग्राफ को लूप होने की अनुमति नहीं देता है। बिना लूप के निर्देशित ग्राफ को सरल निर्देशित ग्राफ कहा जा सकता है, जबकि लूप के साथ निर्देशित ग्राफ को लूप-डिग्राफ कहा जा सकता है (खंड देखें निर्देशित ग्राफ के प्रकार)। निर्देशित ग्राफ के प्रकार उपवर्ग सममित निर्देशित ग्राफ निर्देशित ग्राफ होते हैं जहां सभी किनारे दो बार दिखाई देते हैं, प्रत्येक दिशा में एक (यानी, डिग्राफ से संबंधित प्रत्येक तीर के लिए, संबंधित व्युत्क्रम तीर भी इससे संबंधित होता है)। (इस तरह के किनारे को कभी-कभी "द्विदिश" कहा जाता है और इस तरह के ग्राफ को कभी-कभी "द्विदिश" कहा जाता है, लेकिन यह द्विदिश ग्राफ के अर्थ के साथ संघर्ष करता है।) सरल निर्देशित ग्राफ निर्देशित ग्राफ होते हैं जिनमें कोई लूप (तीर जो सीधे शीर्षों को खुद से जोड़ते हैं) नहीं होते हैं और एक ही स्रोत और लक्ष्य नोड्स के साथ कई तीर नहीं होते हैं। जैसा कि पहले से ही पेश किया गया है, कई तीरों के मामले में इकाई को आमतौर पर निर्देशित बहुलेखन के रूप में संबोधित किया जाता है। कुछ लेखक लूप वाले डिग्राफ को लूप-डिग्राफ के रूप में वर्णित करते हैं। पूर्ण निर्देशित ग्राफ सरल निर्देशित ग्राफ होते हैं जहां शीर्षों की प्रत्येक जोड़ी निर्देशित चापों की एक सममित जोड़ी से जुड़ी होती है (यह विपरीत चापों के जोड़े द्वारा प्रतिस्थापित किनारों के साथ एक अनिर्दिष्ट पूर्ण ग्राफ के बराबर होता है)। यह इस प्रकार है कि एक पूर्ण डिग्राफ सममित है। अर्ध-पूर्ण बहुपक्षीय डिग्राफ सरल डिग्राफ होते हैं जिनमें शीर्ष समूह को ऐसे सेटों में विभाजित किया जाता है कि विभिन्न सेटों में x और y शीर्षों की प्रत्येक जोड़ी के लिए, x और y के बीच एक चाप होता है। x और y के बीच एक चाप या विपरीत दिशाओं में दो चाप हो सकते हैं। अर्ध-पूर्ण डिग्राफ सरल डिग्राफ होते हैं जहाँ शीर्षों की प्रत्येक जोड़ी के बीच एक चाप होता है। प्रत्येक अर्ध-पूर्ण डिग्राफ एक तुच्छ तरीके से एक अर्ध-पूर्ण बहुपक्षीय डिग्राफ है, जिसमें प्रत्येक शीर्ष विभाजन का एक समूह बनाता है। अर्ध-संक्रमणशील डिग्राफ सरल डिग्राफ होते हैं जहां x से y और y से z तक के चाप वाले अलग-अलग शीर्षों के प्रत्येक ट्रिपल x, y, z के लिए x और z के बीच एक चाप होता है। x और z के बीच केवल एक चाप या विपरीत दिशाओं में दो चाप हो सकते हैं। एक अर्ध-पूर्ण डिग्राफ एक अर्ध-सकर्मक डिग्राफ है। अर्ध-संक्रमणशील डिग्राफ के विस्तार हैं जिन्हें के-अर्ध-संक्रमणशील डिग्राफ कहा जाता है। उन्मुख ग्राफ निर्देशित ग्राफ होते हैं जिनमें निर्देशित किनारों का कोई विपरीत जोड़ा नहीं होता है (अर्थात। अधिक से अधिक एक और ग्राफ के तीर हो सकते हैं)। यह इस प्रकार है कि एक निर्देशित ग्राफ एक उन्मुख ग्राफ है यदि और केवल तभी जब इसका कोई 2-चक्र न हो। (यह "उन्मुख ग्राफ" का एकमात्र अर्थ नहीं है; अभिविन्यास (ग्राफ सिद्धांत) देखें। टूर्नामेंट दिशाहीन पूर्ण ग्राफ में प्रत्येक किनारे के लिए एक दिशा चुनकर प्राप्त किए गए उन्मुख ग्राफ हैं। एक टूर्नामेंट एक अर्ध-पूर्ण डिग्राफ है। एक निर्देशित ग्राफ चक्रीय होता है यदि इसमें कोई निर्देशित चक्र नहीं होता है। इस तरह के डिग्राफ का सामान्य नाम निर्देशित एसाइक्लिक ग्राफ (डी. ए. जी.) है। मल्टीट्री डी. ए. जी. होते हैं जिनमें एक ही प्रारंभिक शीर्ष से एक ही अंत शीर्ष तक दो अलग-अलग निर्देशित मार्ग नहीं होते हैं। उन्मुख पेड़ या पॉलीट्री डी. ए. जी. हैं जो पेड़ों के किनारों को उन्मुख करके बनाए जाते हैं (जुड़े हुए, एसाइक्लिक अनिर्दिष्ट ग्राफ)। जड़ वाले पेड़ उन्मुख पेड़ होते हैं जिनमें अंतर्निहित अनिर्देशित पेड़ के सभी किनारे या तो जड़ से दूर या उसकी ओर निर्देशित होते हैं (उन्हें क्रमशः, आर्बोरेसेन्स या आउट-ट्री और इन-ट्री कहा जाता है। पूरक गुणों वाले डिग्राफ भारित निर्देशित ग्राफ (जिन्हें निर्देशित नेटवर्क के रूप में भी जाना जाता है) (सरल) निर्देशित ग्राफ होते हैं जिनके तीरों को भार सौंपा जाता है, भारित ग्राफ के समान (जिन्हें अनिर्दिष्ट नेटवर्क या भारित नेटवर्क के रूप में भी जाना जाता है)। प्रवाह नेटवर्क भारित निर्देशित ग्राफ होते हैं जहाँ दो नोड्स को अलग किया जाता है, एक स्रोत और एक सिंक। जड़ निर्देशित ग्राफ (जिसे प्रवाह ग्राफ के रूप में भी जाना जाता है) डिग्राफ हैं जिनमें एक शीर्ष को मूल के रूप में अलग किया गया है। नियंत्रण-प्रवाह ग्राफ उन मार्गों के प्रतिनिधित्व के रूप में कंप्यूटर विज्ञान में उपयोग किए जाने वाले मूल डिग्राफ हैं जिन्हें इसके निष्पादन के दौरान एक प्रोग्राम के माध्यम से पार किया जा सकता है। सिग्नल-फ्लो ग्राफ निर्देशित ग्राफ होते हैं जिसमें नोड्स सिस्टम चर का प्रतिनिधित्व करते हैं और शाखाएं (किनारे, चाप या तीर) नोड्स के जोड़े के बीच कार्यात्मक कनेक्शन का प्रतिनिधित्व करते हैं। प्रवाह ग्राफ रैखिक बीजगणितीय या विभेदक समीकरणों के एक समूह से जुड़े डिग्राफ हैं। राज्य आरेख निर्देशित बहुलेखन हैं जो सीमित राज्य मशीनों का प्रतिनिधित्व करते हैं। कम्यूटेटिव आरेख श्रेणी सिद्धांत में उपयोग किए जाने वाले डिग्राफ हैं, जहां शीर्ष (गणितीय) वस्तुओं का प्रतिनिधित्व करते हैं और तीर आकृतिवाद का प्रतिनिधित्व करते हैं, इस गुण के साथ कि एक ही शुरुआत और अंतिम बिंदुओं के साथ सभी निर्देशित पथ संरचना द्वारा एक ही परिणाम की ओर ले जाते हैं। लाइ समूहों के सिद्धांत में, एक क्विवर क्यू एक निर्देशित ग्राफ है जो डोमेन के रूप में कार्य करता है, और इस प्रकार एक प्रतिनिधित्व वी के आकार की विशेषता है, जिसे एक फ़ंक्टर के रूप में परिभाषित किया गया है, विशेष रूप से फ़ंक्टर श्रेणी FinVctKF (Q) की एक वस्तु जहां F (Q) Q पर मुक्त श्रेणी है जिसमें Q में पथ शामिल हैं और FinVctK एक क्षेत्र K पर सीमित-आयामी वेक्टर रिक्त स्थान की श्रेणी है। मूल शब्दावली एक चाप को x से y तक निर्देशित माना जाता है; y को शीर्ष कहा जाता है और x को चाप की पूंछ कहा जाता है; y को x का प्रत्यक्ष उत्तराधिकारी कहा जाता है और x को y का प्रत्यक्ष पूर्ववर्ती कहा जाता है। यदि कोई पथ x से y की ओर जाता है, तो y को x का उत्तराधिकारी और x से पहुँच योग्य कहा जाता है, और x को y का पूर्ववर्ती कहा जाता है। आर्क को रिवर्स आर्क ऑफ कहा जाता है। लूपों के साथ एक बहुलेखन का निकटता मैट्रिक्स शीर्षों के अनुरूप पंक्तियों और स्तंभों के साथ पूर्णांक-मूल्यवान मैट्रिक्स है, जहां एक गैर-विकर्ण प्रविष्टि ij शीर्ष i से शीर्ष j तक चापों की संख्या है, और विकर्ण प्रविष्टि iii शीर्ष i पर लूपों की संख्या है। एक निर्देशित ग्राफ का निकटता मैट्रिक्स एक तार्किक मैट्रिक्स है, और पंक्तियों और स्तंभों के क्रमपरिवर्तन तक अद्वितीय है। एक निर्देशित ग्राफ के लिए एक और मैट्रिक्स प्रतिनिधित्व इसकी आपतन मैट्रिक्स है। अधिक परिभाषाओं के लिए दिशा देखें। एक शीर्ष के लिए, एक शीर्ष से सटे सिर के सिरों की संख्या को शीर्ष की इंडेग्री कहा जाता है और एक शीर्ष से सटे पूंछ के सिरों की संख्या इसकी आउट डिग्री (पेड़ों में शाखा कारक कहा जाता है) है। चलो और। v की डिग्री को डिग्री-(v) और इसकी डिग्री को डिग्री + (v) दर्शाया जाता है। एक शीर्ष के साथ एक स्रोत कहा जाता है, क्योंकि यह इसके प्रत्येक आने वाले चाप की उत्पत्ति है। इसी तरह, एक शीर्ष को सिंक कहा जाता है, क्योंकि यह इसके प्रत्येक आने वाले चाप का अंत होता है। डिग्री सम सूत्र बताता है कि, एक निर्देशित ग्राफ के लिए, यदि प्रत्येक शीर्ष के लिए, ग्राफ को एक संतुलित निर्देशित ग्राफ कहा जाता है। डिग्री अनुक्रम एक निर्देशित ग्राफ का डिग्री अनुक्रम इसके अनिर्णित और बाहरी डिग्री जोड़े की सूची है; उपरोक्त उदाहरण के लिए हमारे पास डिग्री अनुक्रम ((2,0), (2,2), (0,2), (1,1)) है। डिग्री अनुक्रम एक निर्देशित ग्राफ अपरिवर्तनीय है इसलिए समरूप निर्देशित ग्राफ में समान डिग्री अनुक्रम होता है। हालांकि, डिग्री अनुक्रम, सामान्य रूप से, विशिष्ट रूप से एक निर्देशित ग्राफ की पहचान नहीं करता है; कुछ मामलों में, गैर-समरूपी डिग्राफ में समान डिग्री अनुक्रम होता है। निर्देशित ग्राफ प्राप्ति समस्या सकारात्मक पूर्णांक जोड़े के दिए गए अनुक्रम के साथ एक निर्देशित ग्राफ खोजने की समस्या है। (शून्यों के पीछे के जोड़े को नजरअंदाज किया जा सकता है क्योंकि उन्हें निर्देशित ग्राफ में अलग-अलग शीर्षों की एक उचित संख्या जोड़कर मामूली रूप से महसूस किया जाता है।) एक अनुक्रम जो किसी निर्देशित ग्राफ का डिग्री अनुक्रम है, अर्थात। जिसके लिए निर्देशित ग्राफ प्राप्ति समस्या का समाधान होता है, उसे निर्देशित ग्राफिक या निर्देशित ग्राफिकल अनुक्रम कहा जाता है। इस समस्या को या तो क्लेटमैन-वांग एल्गोरिदम या फुल्करसन-चेन-एंस्टी प्रमेय द्वारा हल किया जा सकता है। निर्देशित ग्राफ संपर्क एक निर्देशित ग्राफ कमजोर रूप से जुड़ा हुआ है (या बस जुड़ा हुआ है) यदि ग्राफ के सभी निर्देशित किनारों को दिशाहीन किनारों से बदलकर प्राप्त दिशाहीन अंतर्निहित ग्राफ एक जुड़ा हुआ ग्राफ है। एक निर्देशित ग्राफ दृढ़ता से जुड़ा हुआ या मजबूत होता है यदि इसमें शीर्षों की प्रत्येक जोड़ी के लिए x से y (और y से x) तक एक निर्देशित पथ होता है। मजबूत घटक अधिकतम दृढ़ता से जुड़े उपग्राफ हैं। एक जुड़ा हुआ जड़ ग्राफ (या प्रवाह ग्राफ) वह है जहां एक विशिष्ट मूल शीर्ष से प्रत्येक शीर्ष के लिए एक निर्देशित मार्ग मौजूद है। टिप्पणियों के संदर्भ भी देखें (2007 का संशोधित पहला संस्करण अब लेखकों की साइट पर स्वतंत्र रूप से उपलब्ध है; दूसरा संस्करण 2009 में प्रकाशित हुआ)। .. .. (इलेक्ट्रॉनिक तीसरा संस्करण लेखक की साइट पर स्वतंत्र रूप से उपलब्ध है)। .. पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश से एन नोड्स के साथ निर्देशित ग्राफ (या निर्देशित ग्राफ) की संख्या बाहरी लिंक निर्देशित ग्राफ सिद्धांत ग्राफ डेटा संरचनाएँ