निर्देशित ग्राफ

साधारण निर्देशित ग्राफ

गणित में विशेष रूप से ग्राफ़ सिद्धांत में निर्देशित ग्राफ़ ( डिग्राफ) और ग्राफ़ असतत गणित है। जो शिखर ग्राफ़ सिद्धांत के सेट से बना होता है, जो निर्देशित किनारा ग्राफ़ सिद्धांत से जुड़ा होता है, जिसे अधिकांशतः चाप कहा जाता है।

परिभाषा

औपचारिक शब्दों में, निर्देशित ग्राफ क्रमित जोड़ी है G = (V, A) कहाँ^[1]

वी सेट (गणित) है जिसका तत्व (गणित) शिखर (ग्राफ सिद्धांत), नोड्स या अंक कहा जाता है;
A शीर्षों के क्रमित युग्मों का सेट है, जिन्हें चाप कहा जाता है, निर्देशित किनारे (कभी-कभी केवल A के बजाय E नाम के संगत सेट वाले किनारे), तीर, या निर्देशित रेखाएँ।

यह साधारण या अप्रत्यक्ष ग्राफ से भिन्न होता है, जिसमें बाद वाले को वर्टिकल के अनियंत्रित जोड़े के रूप में परिभाषित किया जाता है, जिसे आमतौर पर किनारे, लिंक या रेखा कहा जाता है।

उपरोक्त परिभाषा निर्देशित ग्राफ़ को ही स्रोत और लक्ष्य नोड्स के साथ कई तीरों की अनुमति नहीं देती है, लेकिन कुछ लेखक व्यापक परिभाषा पर विचार करते हैं जो निर्देशित ग्राफ़ को ऐसे कई चाप रखने की अनुमति देता है (अर्थात्, वे आर्क सेट को multiset होने की अनुमति देते हैं) . कभी-कभी इन संस्थाओं को 'निर्देशित मल्टीग्राफ' (या 'मल्टीडिग्राफ') कहा जाता है।
दूसरी ओर, उपरोक्त परिभाषा निर्देशित ग्राफ़ को लूप (ग्राफ़ सिद्धांत) (अर्थात, चाप जो सीधे नोड्स को खुद से जोड़ती है) की अनुमति देती है, लेकिन कुछ लेखक संकीर्ण परिभाषा पर विचार करते हैं जो निर्देशित ग्राफ़ को लूप की अनुमति नहीं देती है।^[2] लूप के बिना निर्देशित ग्राफ़ को सरल निर्देशित ग्राफ़ कहा जा सकता है, जबकि लूप के साथ निर्देशित ग्राफ़ को 'लूप-डिग्राफ़' कहा जा सकता है (अनुभाग # निर्देशित ग्राफ़ के प्रकार देखें)।

निर्देशित रेखांकन के प्रकार

उपवर्ग

सरल निर्देशित विश्वकोश ग्राफ

4 सिरों पर टूर्नामेंट

* सममित निर्देशित ग्राफ़ निर्देशित ग्राफ़ होते हैं जहाँ सभी किनारे दो बार दिखाई देते हैं, प्रत्येक दिशा में (अर्थात, प्रत्येक तीर के लिए जो कि डिग्राफ से संबंधित है, संबंधित उलटा तीर भी इसका है)। (इस तरह के किनारे को कभी-कभी बिडायरेक्टेड कहा जाता है और ऐसे ग्राफ़ को कभी-कभी बिडायरेक्टेड कहा जाता है, लेकिन यह द्विदिश ग्राफ के अर्थ के साथ संघर्ष करता है।)

सरल निर्देशित ग्राफ़ निर्देशित ग्राफ़ होते हैं जिनमें कोई लूप (ग्राफ़ सिद्धांत) नहीं होता है (तीर जो सीधे खुद को कोने से जोड़ते हैं) और ही स्रोत और लक्ष्य नोड्स के साथ कोई भी तीर नहीं होते हैं। जैसा कि पहले ही पेश किया जा चुका है, कई ऐरो के मामले में इकाई को आमतौर पर डायरेक्टेड मल्टीग्राफ के रूप में संबोधित किया जाता है। कुछ लेखक लूप के साथ डिग्राफ का वर्णन 'लूप-डिग्राफ' के रूप में करते हैं।^[2]** पूर्ण निर्देशित ग्राफ़ सरल निर्देशित ग्राफ़ होते हैं जहाँ प्रत्येक जोड़ी को निर्देशित चापों की सममित जोड़ी द्वारा जोड़ा जाता है (यह अप्रत्यक्ष पूर्ण ग्राफ़ के बराबर होता है जिसमें किनारों को व्युत्क्रम चापों के जोड़े द्वारा प्रतिस्थापित किया जाता है)। यह इस प्रकार है कि पूर्ण डिग्राफ सममित है।
- सेमीकंप्लीट मल्टीपार्टिट डिग्राफ सरल डिग्राफ होते हैं जिसमें शिखर सेट को सेट में विभाजित किया जाता है जैसे कि अलग-अलग सेटों में x और y के हर जोड़े के लिए x और के बीच चाप होता है। य। ध्यान दें कि x और y के बीच चाप हो सकता है या विपरीत दिशाओं में दो चाप हो सकते हैं। ^[3]
- सेमीकंप्लीट डिग्राफ सरल डिग्राफ होते हैं जहां प्रत्येक जोड़ी के शीर्ष के बीच चाप होता है। प्रत्येक अर्ध-पूर्ण डिग्राफ तुच्छ तरीके से अर्ध-पूर्ण मल्टीपार्टिट डिग्राफ है, जिसमें प्रत्येक शिखर विभाजन का सेट बनाता है। ^[4]
- अर्ध-सकर्मक डिग्राफ सरल डिग्राफ हैं जहां प्रत्येक ट्रिपल x, y, z के लिए x से y और 'से' चाप के साथ अलग-अलग कोने हैं। 'y' से z तक, x और z के बीच चाप है। ध्यान दें कि x और z के बीच केवल चाप हो सकता है या विपरीत दिशाओं में दो चाप हो सकते हैं। अर्ध-संक्रमणीय डिग्राफ अर्ध-संक्रमणीय डिग्राफ है। अर्ध-संक्रमणीय डिग्राफ के विस्तार हैं जिन्हें 'के'-अर्ध-संक्रमणीय डिग्राफ कहा जाता है। ^[5]
- ओरिएंटेड ग्राफ़ निर्देशित ग्राफ़ होते हैं जिनमें निर्देशित किनारों के विपरीत जोड़े नहीं होते हैं (अर्थात इनमें से अधिकांश में (x, y) और (y, x) ग्राफ के तीर हो सकते हैं)। यह इस प्रकार है कि निर्देशित ग्राफ उन्मुख ग्राफ है अगर और केवल अगर इसका कोई निर्देशित चक्र नहीं है। 2-चक्र।^[6] (यह केवल उन्मुख ग्राफ का अर्थ नहीं है; ओरिएंटेशन (ग्राफ सिद्धांत) देखें।)
  - टूर्नामेंट (गणित) अप्रत्यक्ष पूर्ण रेखांकन में प्रत्येक किनारे के लिए दिशा चुनकर प्राप्त उन्मुख रेखांकन हैं। ध्यान दें कि टूर्नामेंट अर्ध-पूर्ण डिग्राफ है। ^[7]
  - निर्देशित ग्राफ चक्रीय है यदि इसमें कोई निर्देशित चक्र नहीं है। ऐसे डिग्राफ का सामान्य नाम निर्देशित अचक्रीय ग्राफ (DAG) है।^[8] **** हॉटलाइन ज़ डीएजी होते हैं जिनमें ही शुरुआती शीर्ष से ही अंतिम शीर्ष तक दो अलग-अलग निर्देशित पथ नहीं होते हैं।
    - ओरिएंटेड पेड़ या पॉलीट्री पेड़ के किनारों (जुड़े, एसाइक्लिक अप्रत्यक्ष ग्राफ) को उन्मुख करके बनाए गए डीएजी हैं।
      - जड़ वाले पेड़ उन्मुख पेड़ होते हैं जिनमें अंतर्निहित अप्रत्यक्ष पेड़ के सभी किनारों को या तो जड़ से दूर या जड़ की ओर निर्देशित किया जाता है (उन्हें क्रमशः 'आरबोरेसेंस' या 'आउट-ट्री' और 'इन-ट्रीज़' कहा जाता है) '।

पूरक गुणों वाले डिग्राफ

भारित निर्देशित ग्राफ़ (जिन्हें निर्देशित नेटवर्क के रूप में भी जाना जाता है) (सरल) निर्देशित ग्राफ़ होते हैं, जो उनके तीरों को निर्दिष्ट किए जाते हैं, इसी तरह भारित ग्राफ़ (जिन्हें अप्रत्यक्ष नेटवर्क या भारित नेटवर्क के रूप में भी जाना जाता है)।^[2]** प्रवाह नेटवर्क भारित निर्देशित ग्राफ हैं जहां दो नोड्स प्रतिष्ठित हैं, स्रोत और सिंक।
जड़ा हुआ ग्राफ (फ्लो ग्राफ के रूप में भी जाना जाता है) ऐसे डिग्राफ हैं जिनमें शीर्ष को रूट के रूप में प्रतिष्ठित किया गया है।
- नियंत्रण-प्रवाह ग्राफ ़ कंप्यूटर विज्ञान में उपयोग किए जाने वाले पथों के प्रतिनिधित्व के रूप में उपयोग किए जाने वाले डिग्राफ हैं जो इसके निष्पादन के दौरान कार्यक्रम के माध्यम से हो सकते हैं।
सिग्नल-फ्लो ग्राफ़ निर्देशित ग्राफ़ होते हैं जिनमें नोड्स सिस्टम चर और शाखाओं (किनारे, चाप, या तीर) का प्रतिनिधित्व करते हैं जो नोड्स के जोड़े के बीच कार्यात्मक कनेक्शन का प्रतिनिधित्व करते हैं।
फ्लो ग्राफ (गणित) रैखिक बीजगणितीय या अंतर समीकरणों के सेट से जुड़े डिग्राफ हैं।
राज्य आरेख निर्देशित मल्टीग्राफ हैं जो परिमित अवस्था मशीनों का प्रतिनिधित्व करते हैं।
क्रमविनिमेय आरेख श्रेणी सिद्धांत में उपयोग किए जाने वाले डिग्राफ हैं, जहां कोने (गणितीय) वस्तुओं का प्रतिनिधित्व करते हैं और तीर आकारिकी का प्रतिनिधित्व करते हैं, इस गुण के साथ कि सभी निर्देशित पथ ही प्रारंभ और अंत बिंदु के साथ संरचना द्वारा समान परिणाम की ओर ले जाते हैं।
झूठ समूहों के सिद्धांत में, तरकश (गणित) क्यू निर्देशित ग्राफ है जो डोमेन के रूप में कार्य करता है, और इस प्रकार प्रतिनिधित्व वी के आकार को दर्शाता है, जिसे फ़ैक्टर श्रेणी रूप में परिभाषित किया गया है , विशेष रूप से functor श्रेणी FinVct का ऑब्जेक्ट_K^F(Q) जहां F(Q) A पर निःशुल्क श्रेणी है जिसमें Q और FinVest में पथ शामिल हैं_K फ़ील्ड (गणित) K पर परिमित-आयामी वेक्टर रिक्त स्थान की श्रेणी है। तरकश का प्रतिनिधित्व सदिश रिक्त स्थान और उसके किनारों (और इसलिए पथ) के साथ उनके कोने को उनके बीच रैखिक मानचित्र के साथ संगत रूप से लेबल करता है, और प्राकृतिक परिवर्तनों के माध्यम से रूपांतरित करता है।

मूल शब्दावली

संबंधित घटना मैट्रिक्स के साथ ओरिएंटेड ग्राफ

चाप (x, y) को x से y पर निर्देशित माना जाता है; y को शीर्ष कहा जाता है और x को चाप की पूंछ कहा जाता है; y को x का प्रत्यक्ष उत्तराधिकारी कहा जाता है और x को y का प्रत्यक्ष पूर्ववर्ती कहा जाता है। यदि कोई पथ (ग्राफ़ सिद्धांत) x से y की ओर जाता है, तो y को x का उत्तराधिकारी कहा जाता है और x से पहुँचा जा सकता है, और x को y का पूर्ववर्ती कहा जाता है। चाप (y, x) का उलटा चाप कहा जाता है (x, y).

लूप के साथ मल्टीडिग्राफ का आसन्न मैट्रिक्स पूर्णांक-मूल्यवान मैट्रिक्स (गणित) है जिसमें पंक्तियों और स्तंभों के अनुरूप स्तंभ होते हैं, जहां नॉनडायगोनल प्रविष्टि ए_ij शीर्ष i से शीर्ष j तक चापों की संख्या है, और विकर्ण प्रविष्टि a है_ii शीर्ष i पर लूपों की संख्या है। निर्देशित ग्राफ़ का आसन्न मैट्रिक्स तार्किक मैट्रिक्स है, और है पंक्तियों और स्तंभों के क्रमपरिवर्तन तक अद्वितीय।

निर्देशित ग्राफ के लिए अन्य मैट्रिक्स प्रतिनिधित्व इसकी घटना मैट्रिक्स है।

अधिक परिभाषाओं के लिए ग्राफ़ थ्योरी की शब्दावली#दिशा देखें।

इंडिग्री और आउटडिग्री

वर्टिकल लेबल वाला निर्देशित ग्राफ़ (इन्डिग्री, आउटडिग्री)

शीर्ष के लिए, शीर्ष के सन्निकट शीर्ष सिरों की संख्या को शीर्ष का इंडिग्री कहा जाता है और शीर्ष से सटे हुए टेल सिरों की संख्या इसकी आउटडिग्री (पेड़ों में ब्रांचिंग कारक कहा जाता है) है।

होने देना G = (V, A) और v ∈ V. V की डिग्री को डिग्री से दर्शाया जाता है⁻(v) और इसके आउटडिग्री को डिग्री से दर्शाया जाता है⁺(v).

के साथ शीर्ष deg⁻(v) = 0 को स्रोत कहा जाता है, क्योंकि यह इसके प्रत्येक आने वाले चाप का मूल है। इसी तरह, शीर्ष के साथ deg⁺(v) = 0 को सिंक कहा जाता है, क्योंकि यह इसके आने वाले प्रत्येक चाप का अंत है।

डिग्री योग सूत्र बताता है कि, निर्देशित ग्राफ के लिए,

\sum _{v\in V}\deg ^{-}(v)=\sum _{v\in V}\deg ^{+}(v)=|A|.

यदि प्रत्येक शीर्ष के लिए v ∈ V, deg⁺(v) = deg⁻(v), ग्राफ को संतुलित निर्देशित ग्राफ कहा जाता है।^[9]

डिग्री अनुक्रम

निर्देशित ग्राफ़ का डिग्री अनुक्रम इसके इंडिग्री और आउटडिग्री जोड़े की सूची है; उपरोक्त उदाहरण के लिए हमारे पास डिग्री अनुक्रम ((2, 0), (2, 2), (0, 2), (1, 1)) है। डिग्री अनुक्रम निर्देशित ग्राफ़ इनवेरिएंट है इसलिए आइसोमोर्फिक निर्देशित ग्राफ़ में समान डिग्री अनुक्रम होता है। हालांकि, डिग्री अनुक्रम, सामान्य तौर पर, विशिष्ट रूप से निर्देशित ग्राफ की पहचान नहीं करता है; कुछ मामलों में, गैर-आइसोमॉर्फिक डिग्राफ में समान डिग्री अनुक्रम होता है।

डिग्राफ की प्राप्ति की समस्या सकारात्मक पूर्णांक जोड़े के दिए गए अनुक्रम के डिग्री अनुक्रम के साथ निर्देशित ग्राफ खोजने की समस्या है। (शून्य के अनुगामी जोड़े को अनदेखा किया जा सकता है क्योंकि वे निर्देशित ग्राफ में उचित संख्या में अलग-अलग कोने जोड़कर तुच्छ रूप से महसूस किए जाते हैं।) अनुक्रम जो कुछ निर्देशित ग्राफ का डिग्री अनुक्रम है, यानी जिसके लिए निर्देशित ग्राफ प्राप्ति समस्या का समाधान है , निर्देशित ग्राफिक या निर्देशित ग्राफिकल अनुक्रम कहा जाता है। इस समस्या को क्लेटमैन-वैंग एल्गोरिथम या फुलकर्सन-चेन-एंस्टी प्रमेय द्वारा हल किया जा सकता है।