निर्देशित ग्राफ: Difference between revisions
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
== परिभाषा == | == परिभाषा == | ||
औपचारिक शब्दों में निर्देशित ग्राफ क्रमित जोड़ी है {{nobreak|1=''G'' = (''V'', ''A'')}} जहाँ, <ref>{{harvtxt|Bang-Jensen|Gutin|2000}}. {{harvtxt|Bang-Jensen|Gutin|2018}}, Chapter 1.{{harvtxt|Diestel|2005}}, Section 1.10. {{harvtxt|Bondy|Murty|1976}}, Section 10.</ref> | औपचारिक शब्दों में निर्देशित ग्राफ क्रमित जोड़ी है {{nobreak|1=''G'' = (''V'', ''A'')}} जहाँ, <ref>{{harvtxt|Bang-Jensen|Gutin|2000}}. {{harvtxt|Bang-Jensen|Gutin|2018}}, Chapter 1.{{harvtxt|Diestel|2005}}, Section 1.10. {{harvtxt|Bondy|Murty|1976}}, Section 10.</ref> | ||
* | * V [[समूह (गणित)|समूह]] [[सेट (गणित)|(गणित)]] है, जिसका [[तत्व (गणित)]] शिखर ग्राफ सिद्धांत, नोड अंक कहा जाता है। | ||
* A शीर्षों के [[क्रमित युग्म]] का समूह है, जिन्हें चाप कहा जाता है, निर्देशित किनारे कभी-कभी केवल | * A शीर्षों के [[क्रमित युग्म]] का समूह है, जिन्हें चाप कहा जाता है, निर्देशित किनारे कभी-कभी केवल A के अतिरिक्त E नाम के संगत समूहो वाले किनारे, तीर और निर्देशित रेखाएँ है। | ||
यह साधारण [[अप्रत्यक्ष ग्राफ]] से भिन्न होता है, जिसमें बाद वाले को लंबरूप के अनियंत्रित जोड़े के रूप में परिभाषित किया जाता है, जिसे सामान्यतः किनारे को लिंक रेखा कहा जाता है। | यह साधारण [[अप्रत्यक्ष ग्राफ]] से भिन्न होता है, जिसमें बाद वाले को लंबरूप के अनियंत्रित जोड़े के रूप में परिभाषित किया जाता है, जिसे सामान्यतः किनारे को लिंक रेखा कहा जाता है। | ||
| Line 48: | Line 48: | ||
[[File:DirectedDegrees.svg|thumb|लंबरूप लेबल वाला निर्देशित ग्राफ़ (इन्डिग्री, आउटडिग्री)]]शीर्ष के लिए शीर्ष के सन्निकट शीर्ष सिरों की संख्या को शीर्ष का इंडिग्री कहा जाता है और शीर्ष से सटे हुए टेल सिरों की संख्या इसकी आउटडिग्री पेड़ों में [[ब्रांचिंग कारक|शाखाओं मेंकारक]] कहा जाता है। | [[File:DirectedDegrees.svg|thumb|लंबरूप लेबल वाला निर्देशित ग्राफ़ (इन्डिग्री, आउटडिग्री)]]शीर्ष के लिए शीर्ष के सन्निकट शीर्ष सिरों की संख्या को शीर्ष का इंडिग्री कहा जाता है और शीर्ष से सटे हुए टेल सिरों की संख्या इसकी आउटडिग्री पेड़ों में [[ब्रांचिंग कारक|शाखाओं मेंकारक]] कहा जाता है। | ||
माना कि {{nobreak|1=''G'' = (''V'', ''A'')}} और {{nobreak|''v'' ∈ ''V''}}. V की डिग्री को डिग्री से दर्शाया जाता है<sup>−</sup>(v) और इसके आउटडिग्री को डिग्री से दर्शाया जाता है<sup>+</sup>(v). | |||
शीर्ष {{nobreak|1=deg<sup>−</sup>(''v'') = 0}} को स्रोत कहा जाता है, क्योंकि यह इसके प्रत्येक आने वाले चाप का मूल है। इसी प्रकार, शीर्ष के साथ {{nobreak|1=deg<sup>+</sup>(''v'') = 0}} को सिंक कहा जाता है, क्योंकि यह इसके आने वाले प्रत्येक चाप का अंत है। | शीर्ष {{nobreak|1=deg<sup>−</sup>(''v'') = 0}} को स्रोत कहा जाता है, क्योंकि यह इसके प्रत्येक आने वाले चाप का मूल है। इसी प्रकार, शीर्ष के साथ {{nobreak|1=deg<sup>+</sup>(''v'') = 0}} को सिंक कहा जाता है, क्योंकि यह इसके आने वाले प्रत्येक चाप का अंत है। | ||
| Line 137: | Line 137: | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
{{DEFAULTSORT:Directed Graph}} | {{DEFAULTSORT:Directed Graph}} | ||
Revision as of 11:32, 14 March 2023
गणित में विशेष रूप से ग्राफ़ सिद्धांत में निर्देशित ग्राफ़ ( संयुक्ताक्षर) और ग्राफ़ असतत गणित है। जो शिखर ग्राफ़ सिद्धांत के समूहो से बना होता है, जो निर्देशित किनारा ग्राफ़ सिद्धांत से जुड़ा होता है, जिसे अधिकांशतः चाप कहा जाता है।
परिभाषा
औपचारिक शब्दों में निर्देशित ग्राफ क्रमित जोड़ी है G = (V, A) जहाँ, [1]
- V समूह (गणित) है, जिसका तत्व (गणित) शिखर ग्राफ सिद्धांत, नोड अंक कहा जाता है।
- A शीर्षों के क्रमित युग्म का समूह है, जिन्हें चाप कहा जाता है, निर्देशित किनारे कभी-कभी केवल A के अतिरिक्त E नाम के संगत समूहो वाले किनारे, तीर और निर्देशित रेखाएँ है।
यह साधारण अप्रत्यक्ष ग्राफ से भिन्न होता है, जिसमें बाद वाले को लंबरूप के अनियंत्रित जोड़े के रूप में परिभाषित किया जाता है, जिसे सामान्यतः किनारे को लिंक रेखा कहा जाता है।
उपरोक्त परिभाषा निर्देशित ग्राफ़ को ही स्रोत और लक्ष्य नोड के साथ कई तीरों की अनुमति नहीं देती है, किन्तु कुछ लेखक व्यापक परिभाषा पर विचार करते हैं जो निर्देशित ग्राफ़ को ऐसे कई चाप रखने की अनुमति देता है। अर्थात्, वे आर्क समूहो को बहु सेट होने की अनुमति देते हैं। कभी-कभी इन संस्थाओं को 'निर्देशित बहु ग्राफ' कहा जाता है।
दूसरी ओर, उपरोक्त परिभाषा निर्देशित ग्राफ़ को कुंडली ग्राफ़ सिद्धांत अर्थात, चाप जो सीधे नोड को स्वयं से जोड़ने की अनुमति देती है, किन्तु कुछ लेखक संकीर्ण परिभाषा पर विचार करते हैं जो निर्देशित ग्राफ़ को कुंडली की अनुमति नहीं देती है।[2] कुंडली के अतिरिक्त निर्देशित ग्राफ़ को सरल निर्देशित ग्राफ़ कहा जा सकता है, जबकि कुंडली के साथ निर्देशित ग्राफ़ को 'कुंडली-संयुक्ताक्षऱ' कहा जा सकता है।
निर्देशित रेखांकन के प्रकार
उपवर्ग
* सममित निर्देशित ग्राफ़ निर्देशित ग्राफ़ होते हैं, जहाँ सभी किनारे दो बार दिखाई देते हैं। प्रत्येक दिशा में अर्थात, प्रत्येक तीर के लिए जो कि संयुक्ताक्षर से संबंधित संबंधित उलटा तीर भी इसका है। इस प्रकार के किनारे को कभी-कभी द्विदिश कहा जाता है और ऐसे ग्राफ़ को कभी-कभी द्विदिश कहा जाता है, किन्तु यह द्विदिश ग्राफ के अर्थ के साथ संघर्ष करता है।
- सरल निर्देशित ग्राफ़ निर्देशित ग्राफ़ होते हैं, जिनमें कोई कुंडली ग्राफ़ सिद्धांत नहीं होता है। तीर जो सीधे स्वयं को कोने से जोड़ते हैं और ही स्रोत और लक्ष्य नोड्स के साथ कोई भी तीर नहीं होते हैं। जैसा कि पहले ही प्रस्तुत किया जा चुका है, कई तीरो के स्थितियों में इकाई को सामान्यतः निर्देशित बहु ग्राफ के रूप में संबोधित किया जाता है। कुछ लेखक कुंडली के साथ संयुक्ताक्षर का वर्णन 'कुंडली-संयुक्ताक्षर' के रूप में करते हैं।[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]
- निर्देशित ग्राफ चक्रीय है यदि इसमें कोई निर्देशित चक्र नहीं है। ऐसे संयुक्ताक्षर का सामान्य नाम निर्देशित अचक्रीय ग्राफ (डीएजी) है।[8] हॉटलाइन डीएजी होते हैं जिनमें ही प्रारंभिक शीर्ष से ही अंतिम शीर्ष तक दो अलग-अलग निर्देशित पथ नहीं होते हैं।
- उन्मुख पेड़ पाली के पेड़ के किनारों जुड़े, अचक्रीय अप्रत्यक्ष ग्राफ को उन्मुख करके बनाए गए डीएजी हैं।
- जड़ वाले पेड़ उन्मुख पेड़ होते हैं जिनमें अंतर्निहित अप्रत्यक्ष पेड़ के सभी किनारों को जड़ से दूर या जड़ की ओर निर्देशित किया जाता है उन्हें क्रमशः बाहर का पेड़ और वृक्षों मे' 'वृक्षानुरूपता' कहा जाता है।
- उन्मुख पेड़ पाली के पेड़ के किनारों जुड़े, अचक्रीय अप्रत्यक्ष ग्राफ को उन्मुख करके बनाए गए डीएजी हैं।
पूरक गुणों वाले संयुक्ताक्षर
- भारित निर्देशित ग्राफ़ जिन्हें निर्देशित नेटवर्क के रूप में भी जाना जाता है। सरल निर्देशित ग्राफ़ होते हैं, जो उनके तीरों को निर्दिष्ट किए जाते हैं, इसी प्रकार भारित ग्राफ जिन्हें अप्रत्यक्ष नेटवर्क भारित नेटवर्क के रूप में भी जाना जाता है।[2] प्रवाह नेटवर्क भारित निर्देशित ग्राफ हैं, जहां दो नोड प्रतिष्ठित हैं।
- जड़ा हुआ ग्राफ प्रवाह ग्राफ के रूप में भी जाना जाता है, ऐसे संयुक्ताक्षर हैं जिनमें स्रोत और सिंक शीर्ष को मूल के रूप में प्रतिष्ठित किया गया है।
- नियंत्रण-प्रवाह ग्राफ कंप्यूटर विज्ञान में उपयोग किए जाने वाले पथों के प्रतिनिधित्व के रूप में उपयोग किए जाने वाले संयुक्ताक्षर हैं जो इसके निष्पादन के पर्यन्त कार्यक्रम के माध्यम से हो सकते हैं।
- सिग्नल-प्रवाह ग्राफ निर्देशित ग्राफ़ होते हैं जिनमें नोड प्रणाली चर और शाखाओं किनारे, चाप और तीर का प्रतिनिधित्व करते हैं जो नोड के जोड़े के बीच कार्यात्मक संयोजन का प्रतिनिधित्व करते हैं।
- प्रवाह ग्राफ (गणित) रैखिक बीजगणितीय अंतर समीकरणों के समूहो से जुड़े संयुक्ताक्षर हैं।
- राज्य आरेख निर्देशित बहु ग्राफ हैं जो परिमित अवस्था मशीन का प्रतिनिधित्व करते हैं।
- क्रमविनिमेय आरेख श्रेणी सिद्धांत में उपयोग किए जाने वाले संयुक्ताक्षर हैं, जहां कोने गणितीय वस्तुओं का प्रतिनिधित्व करते हैं और तीर आकारिकी का प्रतिनिधित्व करते हैं। इस गुण के साथ कि सभी निर्देशित पथ ही प्रारंभ और अंत बिंदु के साथ संरचना द्वारा समान परिणाम की ओर ले जाते हैं।
- झूठ समूह के सिद्धांत में तरकश (गणित) क्यू निर्देशित ग्राफ है जो डोमेन के रूप में कार्य करता है और इस प्रकार प्रतिनिधित्व वी के आकार को दर्शाता है, जिसे कारक श्रृंखला रूप में परिभाषित किया गया है। विशेष रूप से फ़ैक्टर श्रेणी फिनवेस्ट का प्रयोजनKF(Q) जहां F(Q) ए पर निःशुल्क श्रेणी है जिसमें QK और फिनवेस्ट में पथ सम्मलित हैं क्षेत्र (गणित) 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 तक चापों की संख्या है और विकर्ण प्रविष्टि ए हैii शीर्ष i पर कुंडलीों की संख्या है। निर्देशित ग्राफ़ का आसन्न आव्यूह तार्किक आव्यूह है और है पंक्तियों और स्तंभों के क्रमपरिवर्तन तक अद्वितीय है।
निर्देशित ग्राफ के लिए अन्य आव्यूह प्रतिनिधित्व इसकी घटना आव्यूह है।
अधिक परिभाषाओं के लिए ग्राफ़ सिद्धांत की शब्दावली दिशा देखें।
इंडिग्री और आउटडिग्री
शीर्ष के लिए शीर्ष के सन्निकट शीर्ष सिरों की संख्या को शीर्ष का इंडिग्री कहा जाता है और शीर्ष से सटे हुए टेल सिरों की संख्या इसकी आउटडिग्री पेड़ों में शाखाओं मेंकारक कहा जाता है।
माना कि G = (V, A) और v ∈ V. V की डिग्री को डिग्री से दर्शाया जाता है−(v) और इसके आउटडिग्री को डिग्री से दर्शाया जाता है+(v).
शीर्ष deg−(v) = 0 को स्रोत कहा जाता है, क्योंकि यह इसके प्रत्येक आने वाले चाप का मूल है। इसी प्रकार, शीर्ष के साथ deg+(v) = 0 को सिंक कहा जाता है, क्योंकि यह इसके आने वाले प्रत्येक चाप का अंत है।
डिग्री योग सूत्र बताता है कि निर्देशित ग्राफ के लिए,
यदि प्रत्येक शीर्ष के लिए v ∈ V, deg+(v) = deg−(v), ग्राफ को संतुलित निर्देशित ग्राफ कहा जाता है।[9]
डिग्री अनुक्रम
निर्देशित ग्राफ़ का डिग्री अनुक्रम इसके इंडिग्री और आउटडिग्री जोड़े की सूची है, उपरोक्त उदाहरण के लिए हमारे पास डिग्री अनुक्रम ((2, 0), (2, 2), (0, 2), (1, 1)) है। डिग्री अनुक्रम निर्देशित ग्राफ़ अपरिवर्तनीय है इसलिए समरूपी निर्देशित ग्राफ़ में समान डिग्री अनुक्रम होता है। चूंकि, डिग्री अनुक्रम सामान्यतः विशिष्ट रूप से निर्देशित ग्राफ की पहचान नहीं करता है, कुछ स्थितियों में गैर-समरूपी संयुक्ताक्षर में समान डिग्री अनुक्रम होता है।
संयुक्ताक्षर की प्राप्ति की समस्या सकारात्मक पूर्णांक जोड़े के दिए गए अनुक्रम के डिग्री अनुक्रम के साथ निर्देशित ग्राफ खोजने की समस्या है। शून्य के अनुगामी जोड़े को अनदेखा किया जा सकता है क्योंकि वे निर्देशित ग्राफ में उचित संख्या में अलग-अलग कोने जोड़कर तुच्छ रूप से अनुभव किए जाते हैं। अनुक्रम जो कुछ निर्देशित ग्राफ का डिग्री अनुक्रम है, अर्थात जिसके लिए निर्देशित ग्राफ प्राप्ति समस्या का समाधान है, जिसे निर्देशित ग्राफिकल अनुक्रम कहा जाता है। इस समस्या को क्लेटमैन-वैंग एल्गोरिथम और फुलकर्सन-चेन-एंस्टी प्रमेय द्वारा हल किया जा सकता है।
निर्देशित ग्राफ कनेक्टिविटी
निर्देशित ग्राफ कमजोर रूप से अभी जुड़ा हुआ है[10] यदि अप्रत्यक्ष किनारों के साथ ग्राफ के सभी निर्देशित किनारों को बदलकर प्राप्त अप्रत्यक्ष अंतर्निहित ग्राफ कनेक्टिविटी (ग्राफ सिद्धांत) है।
निर्देशित ग्राफ दृढ़ता से जुड़ा हुआ शक्तिशाली होता है, यदि इसमें x से y और y से x तक के प्रत्येक जोड़े के लिए निर्देशित पथ होता है (x, y). मजबूत घटक अधिकतम मजबूती से जुड़े उप ग्राफ हैं।
जुड़ा हुआ प्रवाह ग्राफ वह है जहां विशिष्ट मूल शिखर से प्रत्येक शीर्ष के लिए निर्देशित पथ उपस्तिथ होता है।
यह भी देखें
टिप्पणियाँ
- ↑ Bang-Jensen & Gutin (2000). Bang-Jensen & Gutin (2018), Chapter 1.Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.
- ↑ 2.0 2.1 2.2 Chartrand, Gary (1977). परिचयात्मक ग्राफ सिद्धांत. Courier Corporation. ISBN 9780486247755. Archived from the original on 2023-02-04. Retrieved 2020-10-02.
- ↑ Bang-Jensen & Gutin (2018), Chapter 7 by Yeo.
- ↑ Bang-Jensen & Gutin (2018), Chapter 2 by Bang-Jensen and Havet.
- ↑ Bang-Jensen & Gutin (2018), Chapter 8 by Galeana-Sanchez and Hernandez-Cruz.
- ↑ Diestel (2005), Section 1.10.
- ↑ Bang-Jensen & Gutin (2018), Chapter 2 by Bang-Jensen and Havet.
- ↑ Bang-Jensen & Gutin (2018), Chapter 3 by Gutin.
- ↑ Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd., p. 460, ISBN 978-81-203-3842-5; Brualdi, Richard A. (2006), Combinatorial Matrix Classes, Encyclopedia of Mathematics and Its Applications, vol. 108, Cambridge University Press, p. 51, ISBN 978-0-521-86565-4.
- ↑ Bang-Jensen & Gutin (2000) p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).
संदर्भ
- Bang-Jensen, Jørgen; Gutin, Gregory (2000), Digraphs: Theory, Algorithms and Applications, Springer, ISBN 1-85233-268-9
(the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009 ISBN 1-84800-997-6). - Bang-Jensen, Jørgen; Gutin, Gregory (2018), Classes of Directed Graphs, Springer, ISBN 978-3319718408.
- Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7.
- Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6 (the electronic 3rd edition is freely available on author's site).
- Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley.
- Number of directed graphs (or directed graphs) with n nodes from On-Line Encyclopedia of Integer Sequences
