निर्देशित ग्राफ: Difference between revisions

Latest revision as of 17:40, 15 March 2023

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

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

परिभाषा

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

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

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

उपरोक्त परिभाषा निर्देशित ग्राफ़ को ही स्रोत और लक्ष्य नोड के साथ कई तीरों की अनुमति नहीं देती है, किन्तु कुछ लेखक व्यापक परिभाषा पर विचार करते हैं जो निर्देशित ग्राफ़ को ऐसे कई चाप रखने की अनुमति देता है। अर्थात्, वे आर्क समूहो को बहु सेट होने की अनुमति देते हैं। कभी-कभी इन संस्थाओं को 'निर्देशित बहु ग्राफ' कहा जाता है।
दूसरी ओर, उपरोक्त परिभाषा निर्देशित ग्राफ़ को कुंडली ग्राफ़ सिद्धांत अर्थात, चाप जो सीधे नोड को स्वयं से जोड़ने की अनुमति देती है, किन्तु कुछ लेखक संकीर्ण परिभाषा पर विचार करते हैं जो निर्देशित ग्राफ़ को कुंडली की अनुमति नहीं देती है।^[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]
  - निर्देशित ग्राफ चक्रीय है यदि इसमें कोई निर्देशित चक्र नहीं है। ऐसे संयुक्ताक्षर का सामान्य नाम निर्देशित अचक्रीय ग्राफ (डीएजी) है।^[8] हॉटलाइन डीएजी होते हैं जिनमें ही प्रारंभिक शीर्ष से ही अंतिम शीर्ष तक दो अलग-अलग निर्देशित पथ नहीं होते हैं।
    - उन्मुख पेड़ पाली के पेड़ के किनारों जुड़े, अचक्रीय अप्रत्यक्ष ग्राफ को उन्मुख करके बनाए गए डीएजी हैं।
      - जड़ वाले पेड़ उन्मुख पेड़ होते हैं जिनमें अंतर्निहित अप्रत्यक्ष पेड़ के सभी किनारों को जड़ से दूर या जड़ की ओर निर्देशित किया जाता है उन्हें क्रमशः बाहर का पेड़ और वृक्षों मे' 'वृक्षानुरूपता' कहा जाता है।

पूरक गुणों वाले संयुक्ताक्षर

भारित निर्देशित ग्राफ़ जिन्हें निर्देशित नेटवर्क के रूप में भी जाना जाता है। सरल निर्देशित ग्राफ़ होते हैं, जो उनके तीरों को निर्दिष्ट किए जाते हैं, इसी प्रकार भारित ग्राफ जिन्हें अप्रत्यक्ष नेटवर्क भारित नेटवर्क के रूप में भी जाना जाता है।^[2] प्रवाह नेटवर्क भारित निर्देशित ग्राफ हैं, जहां दो नोड प्रतिष्ठित हैं।
जड़ा हुआ ग्राफ प्रवाह ग्राफ के रूप में भी जाना जाता है, ऐसे संयुक्ताक्षर हैं जिनमें स्रोत और सिंक शीर्ष को मूल के रूप में प्रतिष्ठित किया गया है।
- नियंत्रण-प्रवाह ग्राफ कंप्यूटर विज्ञान में उपयोग किए जाने वाले पथों के प्रतिनिधित्व के रूप में उपयोग किए जाने वाले संयुक्ताक्षर हैं जो इसके निष्पादन के पर्यन्त कार्यक्रम के माध्यम से हो सकते हैं।
सिग्नल-प्रवाह ग्राफ निर्देशित ग्राफ़ होते हैं जिनमें नोड प्रणाली चर और शाखाओं किनारे, चाप और तीर का प्रतिनिधित्व करते हैं जो नोड के जोड़े के बीच कार्यात्मक संयोजन का प्रतिनिधित्व करते हैं।
प्रवाह ग्राफ (गणित) रैखिक बीजगणितीय अंतर समीकरणों के समूहो से जुड़े संयुक्ताक्षर हैं।
राज्य आरेख निर्देशित बहु ग्राफ हैं जो परिमित अवस्था मशीन का प्रतिनिधित्व करते हैं।
क्रमविनिमेय आरेख श्रेणी सिद्धांत में उपयोग किए जाने वाले संयुक्ताक्षर हैं, जहां कोने गणितीय वस्तुओं का प्रतिनिधित्व करते हैं और तीर आकारिकी का प्रतिनिधित्व करते हैं। इस गुण के साथ कि सभी निर्देशित पथ ही प्रारंभ और अंत बिंदु के साथ संरचना द्वारा समान परिणाम की ओर ले जाते हैं।
झूठ समूह के सिद्धांत में तरकश (गणित) क्यू निर्देशित ग्राफ है जो डोमेन के रूप में कार्य करता है और इस प्रकार प्रतिनिधित्व वी के आकार को दर्शाता है, जिसे कारक श्रृंखला रूप में परिभाषित किया गया है। विशेष रूप से फ़ैक्टर श्रेणी फिनवेस्ट का प्रयोजन_K^F(Q) जहां F(Q) ए पर निःशुल्क श्रेणी है जिसमें Q_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 तक चापों की संख्या है और विकर्ण प्रविष्टि ए है_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)) है। डिग्री अनुक्रम निर्देशित ग्राफ़ अपरिवर्तनीय है इसलिए समरूपी निर्देशित ग्राफ़ में समान डिग्री अनुक्रम होता है। चूंकि, डिग्री अनुक्रम सामान्यतः विशिष्ट रूप से निर्देशित ग्राफ की पहचान नहीं करता है, कुछ स्थितियों में गैर-समरूपी संयुक्ताक्षर में समान डिग्री अनुक्रम होता है।

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

निर्देशित ग्राफ कनेक्टिविटी

निर्देशित ग्राफ कमजोर रूप से अभी जुड़ा हुआ है^[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

बाहरी संबंध

[1] Bang-Jensen & Gutin (2000). Bang-Jensen & Gutin (2018), Chapter 1.Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.

[Chartrand-2] 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.

[3] Bang-Jensen & Gutin (2018), Chapter 7 by Yeo.

[4] Bang-Jensen & Gutin (2018), Chapter 2 by Bang-Jensen and Havet.

[5] Bang-Jensen & Gutin (2018), Chapter 8 by Galeana-Sanchez and Hernandez-Cruz.

[6] Diestel (2005), Section 1.10.

[7] Bang-Jensen & Gutin (2018), Chapter 2 by Bang-Jensen and Havet.

[8] Bang-Jensen & Gutin (2018), Chapter 3 by Gutin.

[9] 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.

[10] Bang-Jensen & Gutin (2000) p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ 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>
-* वी [[समूह (गणित)|समूह]] [[सेट (गणित)|(गणित)]] है, जिसका [[तत्व (गणित)]] शिखर ग्राफ सिद्धांत, नोड अंक कहा जाता है।
+* V [[समूह (गणित)|समूह]] [[सेट (गणित)|(गणित)]] है, जिसका [[तत्व (गणित)]] शिखर ग्राफ सिद्धांत, नोड अंक कहा जाता है।
-* A शीर्षों के [[क्रमित युग्म]] का समूह है, जिन्हें चाप कहा जाता है, निर्देशित किनारे कभी-कभी केवल ए के अतिरिक्त इ नाम के संगत समूहो वाले किनारे, तीर और निर्देशित रेखाएँ है।
+* A शीर्षों के [[क्रमित युग्म]] का समूह है, जिन्हें चाप कहा जाता है, निर्देशित किनारे कभी-कभी केवल A के अतिरिक्त E नाम के संगत समूहो वाले किनारे, तीर और निर्देशित रेखाएँ है।
 यह साधारण [[अप्रत्यक्ष ग्राफ]] से भिन्न होता है, जिसमें बाद वाले को लंबरूप के अनियंत्रित जोड़े के रूप में परिभाषित किया जाता है, जिसे सामान्यतः किनारे को लिंक रेखा कहा जाता है।
@@ Line 27: / Line 27: @@
 === पूरक गुणों वाले संयुक्ताक्षर ===
-* भारित निर्देशित ग्राफ़ (जिन्हें निर्देशित नेटवर्क के रूप में भी जाना जाता है) (सरल) निर्देशित ग्राफ़ होते हैं, जो उनके तीरों को निर्दिष्ट किए जाते हैं, इसी प्रकार [[भारित ग्राफ]] (जिन्हें अप्रत्यक्ष नेटवर्क या [[भारित नेटवर्क]] के रूप में भी जाना जाता है)।<ref name="Chartrand"/>** [[ प्रवाह नेटवर्क |प्रवाह नेटवर्क]] भारित निर्देशित ग्राफ हैं जहां दो नोड्स प्रतिष्ठित हैं, ''स्रोत'' और ''सिंक''।
+* भारित निर्देशित ग्राफ़ जिन्हें निर्देशित नेटवर्क के रूप में भी जाना जाता है। सरल निर्देशित ग्राफ़ होते हैं, जो उनके तीरों को निर्दिष्ट किए जाते हैं, इसी प्रकार [[भारित ग्राफ]] जिन्हें अप्रत्यक्ष नेटवर्क [[भारित नेटवर्क]] के रूप में भी जाना जाता है।<ref name="Chartrand"/> [[ प्रवाह नेटवर्क |प्रवाह नेटवर्क]] भारित निर्देशित ग्राफ हैं, जहां दो नोड प्रतिष्ठित हैं।
-* [[ जड़ा हुआ ग्राफ | जड़ा हुआ ग्राफ]] (फ्लो ग्राफ के रूप में भी जाना जाता है) ऐसे संयुक्ताक्षर हैं जिनमें शीर्ष को रूट के रूप में प्रतिष्ठित किया गया है।
+* [[ जड़ा हुआ ग्राफ | जड़ा हुआ ग्राफ]] प्रवाह ग्राफ के रूप में भी जाना जाता है, ऐसे संयुक्ताक्षर हैं जिनमें ''स्रोत'' और ''सिंक'' शीर्ष को मूल के रूप में प्रतिष्ठित किया गया है।
-** ''[[ नियंत्रण-प्रवाह ग्राफ ]]़'' कंप्यूटर विज्ञान में उपयोग किए जाने वाले पथों के प्रतिनिधित्व के रूप में उपयोग किए जाने वाले संयुक्ताक्षर हैं जो इसके निष्पादन के दौरान कार्यक्रम के माध्यम से हो सकते हैं।
+** ''[[ नियंत्रण-प्रवाह ग्राफ | नियंत्रण-प्रवाह ग्राफ]]'' कंप्यूटर विज्ञान में उपयोग किए जाने वाले पथों के प्रतिनिधित्व के रूप में उपयोग किए जाने वाले संयुक्ताक्षर हैं जो इसके निष्पादन के पर्यन्त कार्यक्रम के माध्यम से हो सकते हैं।
-* [[सिग्नल-फ्लो ग्राफ]]़ निर्देशित ग्राफ़ होते हैं जिनमें नोड्स सिस्टम चर और शाखाओं (किनारे, चाप, या तीर) का प्रतिनिधित्व करते हैं जो नोड्स के जोड़े के बीच कार्यात्मक कनेक्शन का प्रतिनिधित्व करते हैं।
+* [[सिग्नल-फ्लो ग्राफ|सिग्नल-प्रवाह ग्राफ]] निर्देशित ग्राफ़ होते हैं जिनमें नोड प्रणाली चर और शाखाओं किनारे, चाप और तीर का प्रतिनिधित्व करते हैं जो नोड के जोड़े के बीच कार्यात्मक संयोजन का प्रतिनिधित्व करते हैं।
-* [[फ्लो ग्राफ (गणित)]] रैखिक बीजगणितीय या अंतर समीकरणों के समूहो से जुड़े संयुक्ताक्षर हैं।
+* [[फ्लो ग्राफ (गणित)|प्रवाह ग्राफ (गणित)]] रैखिक बीजगणितीय अंतर समीकरणों के समूहो से जुड़े संयुक्ताक्षर हैं।
-* [[ राज्य आरेख | राज्य आरेख]] निर्देशित बहु ग्राफ हैं जो [[परिमित अवस्था मशीन]]ों का प्रतिनिधित्व करते हैं।
+* [[ राज्य आरेख | राज्य आरेख]] निर्देशित बहु ग्राफ हैं जो [[परिमित अवस्था मशीन]] का प्रतिनिधित्व करते हैं।
-* [[क्रमविनिमेय आरेख]] [[श्रेणी सिद्धांत]] में उपयोग किए जाने वाले संयुक्ताक्षर हैं, जहां कोने (गणितीय) वस्तुओं का प्रतिनिधित्व करते हैं और तीर आकारिकी का प्रतिनिधित्व करते हैं, इस गुण के साथ कि सभी निर्देशित पथ ही प्रारंभ और अंत बिंदु के साथ संरचना द्वारा समान परिणाम की ओर ले जाते हैं।
+* [[क्रमविनिमेय आरेख]] [[श्रेणी सिद्धांत]] में उपयोग किए जाने वाले संयुक्ताक्षर हैं, जहां कोने गणितीय वस्तुओं का प्रतिनिधित्व करते हैं और तीर आकारिकी का प्रतिनिधित्व करते हैं। इस गुण के साथ कि सभी निर्देशित पथ ही प्रारंभ और अंत बिंदु के साथ संरचना द्वारा समान परिणाम की ओर ले जाते हैं।
-* [[झूठ समूह]]ों के सिद्धांत में, [[तरकश (गणित)]] ''क्यू'' निर्देशित ग्राफ है जो डोमेन के रूप में कार्य करता है, और इस प्रकार ''प्रतिनिधित्व'' ''वी'' के आकार को दर्शाता है, जिसे [[फ़ैक्टर श्रेणी]] रूप में परिभाषित किया गया है , विशेष रूप से [[functor]] श्रेणी FinVct का ऑब्जेक्ट<sub>''K''</sub><sup>F(Q)</sup> जहां F(Q) ए पर निःशुल्क श्रेणी है जिसमें Q और FinVest में पथ शामिल हैं<sub>''K''</sub> फ़ील्ड (गणित) K पर परिमित-आयामी वेक्टर रिक्त स्थान की श्रेणी है। तरकश का प्रतिनिधित्व सदिश रिक्त स्थान और उसके किनारों (और इसलिए पथ) के साथ उनके कोने को उनके बीच [[रैखिक मानचित्र]] के साथ संगत रूप से लेबल करता है, और [[प्राकृतिक परिवर्तन]]ों के माध्यम से रूपांतरित करता है।
+* [[झूठ समूह]] के सिद्धांत में [[तरकश (गणित)]] ''क्यू'' निर्देशित ग्राफ है जो डोमेन के रूप में कार्य करता है और इस प्रकार ''प्रतिनिधित्व'' ''वी'' के आकार को दर्शाता है, जिसे [[फ़ैक्टर श्रेणी|कारक श्रृंखला]] रूप में परिभाषित किया गया है। विशेष रूप से [[functor|फ़ैक्टर]] श्रेणी फिनवेस्ट का प्रयोजन<sub>''K''</sub><sup>F(Q)</sup> जहां F(Q) ए पर निःशुल्क श्रेणी है जिसमें Q<sub>''K''</sub> और फिनवेस्ट में पथ सम्मलित हैं क्षेत्र (गणित) K पर परिमित-आयामी वेक्टर रिक्त स्थान की श्रेणी है। तरकश का प्रतिनिधित्व सदिश रिक्त स्थान और उसके किनारों के साथ उनके कोने को उनके बीच [[रैखिक मानचित्र]] के साथ संगत रूप से लेबल करता है, और इसलिए पथ [[प्राकृतिक परिवर्तन]] के माध्यम से रूपांतरित करता है।
 == मूल शब्दावली ==
-[[File:Incidence matrix - directed graph.svg|thumb|संबंधित घटना मैट्रिक्स के साथ उन्मुख ग्राफ]]चाप {{nobreak|(''x'', ''y'')}} को x से y पर निर्देशित माना जाता है; y को शीर्ष कहा जाता है और x को चाप की पूंछ कहा जाता है; y को x का प्रत्यक्ष उत्तराधिकारी कहा जाता है और x को y का प्रत्यक्ष पूर्ववर्ती कहा जाता है। यदि कोई पथ (ग्राफ़ सिद्धांत) x से y की ओर जाता है, तो y को x का उत्तराधिकारी कहा जाता है और x से पहुँचा जा सकता है, और x को y का पूर्ववर्ती कहा जाता है। चाप {{nobreak|(''y'', ''x'')}} का उलटा चाप कहा जाता है {{nobreak|(''x'', ''y'')}}.
+[[File:Incidence matrix - directed graph.svg|thumb|संबंधित घटना आव्यूह के साथ उन्मुख ग्राफ]]चाप {{nobreak|(''x'', ''y'')}} को x से y पर निर्देशित माना जाता है, y को शीर्ष कहा जाता है और x को चाप की पूंछ कहा जाता है, y को x का प्रत्यक्ष उत्तराधिकारी कहा जाता है और x को y का प्रत्यक्ष पूर्ववर्ती कहा जाता है। यदि कोई पथ ग्राफ़ सिद्धांत x से y की ओर जाता है, तो y को x का उत्तराधिकारी कहा जाता है और x से पहुँचा जा सकता है और x को y का पूर्ववर्ती कहा जाता है। चाप {{nobreak|(''y'', ''x'')}} का उलटा चाप कहा जाता है {{nobreak|(''x'', ''y'')}}.
-कुंडली के साथ मल्टीसंयुक्ताक्षर का आसन्न मैट्रिक्स पूर्णांक-मूल्यवान [[मैट्रिक्स (गणित)]] है जिसमें पंक्तियों और स्तंभों के अनुरूप स्तंभ होते हैं, जहां नॉनडायगोनल प्रविष्टि ए<sub>''ij''</sub> शीर्ष i से शीर्ष j तक चापों की संख्या है, और विकर्ण प्रविष्टि ए है<sub>''ii''</sub> शीर्ष i पर कुंडलीों की संख्या है। निर्देशित ग्राफ़ का आसन्न मैट्रिक्स [[तार्किक मैट्रिक्स]] है, और है
+कुंडली के साथ बहु संयुक्ताक्षर का आसन्न आव्यूह पूर्णांक-मूल्यवान [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] है जिसमें पंक्तियों और स्तंभों के अनुरूप स्तंभ होते हैं, जहां गैर विकर्ण प्रविष्टि ए<sub>''ij''</sub> शीर्ष i से शीर्ष j तक चापों की संख्या है और विकर्ण प्रविष्टि ए है<sub>''ii''</sub> शीर्ष i पर कुंडलीों की संख्या है। निर्देशित ग्राफ़ का आसन्न आव्यूह [[तार्किक मैट्रिक्स|तार्किक आव्यूह]] है और है पंक्तियों और स्तंभों के क्रमपरिवर्तन तक अद्वितीय है।
-पंक्तियों और स्तंभों के क्रमपरिवर्तन तक अद्वितीय।
-निर्देशित ग्राफ के लिए अन्य मैट्रिक्स प्रतिनिधित्व इसकी [[घटना मैट्रिक्स]] है।
+निर्देशित ग्राफ के लिए अन्य आव्यूह प्रतिनिधित्व इसकी [[घटना (सापेक्षता)|घटना आव्यूह]] है।
-अधिक परिभाषाओं के लिए ग्राफ़ थ्योरी की शब्दावली#दिशा देखें।
+अधिक परिभाषाओं के लिए ग्राफ़ सिद्धांत की शब्दावली दिशा देखें।
 == इंडिग्री और आउटडिग्री ==
-[[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=''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}} को सिंक कहा जाता है, क्योंकि यह इसके आने वाले प्रत्येक चाप का अंत है।
-डिग्री योग सूत्र बताता है कि, निर्देशित ग्राफ के लिए,
+डिग्री योग सूत्र बताता है कि निर्देशित ग्राफ के लिए,
 : <math>\sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |A|.</math>
 यदि प्रत्येक शीर्ष के लिए {{nobreak|''v'' ∈ ''V''}}, {{nobreak|1=deg<sup>+</sup>(''v'') = deg<sup>−</sup>(''v'')}}, ग्राफ को संतुलित निर्देशित ग्राफ कहा जाता है।<ref>{{citation|page=460|title=Discrete Mathematics and Graph Theory|first1=Bhavanari|last1=Satyanarayana|first2=Kuncham Syam| last2=Prasad| publisher=PHI Learning Pvt. Ltd.|isbn=978-81-203-3842-5}}; {{citation|page=[https://archive.org/details/combinatorialmat0000brua/page/51 51]| title=Combinatorial Matrix Classes| volume=108|series=Encyclopedia of Mathematics and Its Applications|first=Richard A. |last=Brualdi| publisher=Cambridge University Press|year=2006|isbn=978-0-521-86565-4| url=https://archive.org/details/combinatorialmat0000brua/page/51}}.</ref>
@@ Line 59: / Line 58: @@
 == डिग्री अनुक्रम ==
-निर्देशित ग्राफ़ का डिग्री अनुक्रम इसके इंडिग्री और आउटडिग्री जोड़े की सूची है; उपरोक्त उदाहरण के लिए हमारे पास डिग्री अनुक्रम ((2, 0), (2, 2), (0, 2), (1, 1)) है। डिग्री अनुक्रम निर्देशित ग्राफ़ इनवेरिएंट है इसलिए आइसोमोर्फिक निर्देशित ग्राफ़ में समान डिग्री अनुक्रम होता है। हालांकि, डिग्री अनुक्रम, सामान्य तौर पर, विशिष्ट रूप से निर्देशित ग्राफ की पहचान नहीं करता है; कुछ मामलों में, गैर-आइसोमॉर्फिक संयुक्ताक्षर में समान डिग्री अनुक्रम होता है।
+निर्देशित ग्राफ़ का डिग्री अनुक्रम इसके इंडिग्री और आउटडिग्री जोड़े की सूची है, उपरोक्त उदाहरण के लिए हमारे पास डिग्री अनुक्रम ((2, 0), (2, 2), (0, 2), (1, 1)) है। डिग्री अनुक्रम निर्देशित ग्राफ़ अपरिवर्तनीय है इसलिए समरूपी निर्देशित ग्राफ़ में समान डिग्री अनुक्रम होता है। चूंकि, डिग्री अनुक्रम सामान्यतः विशिष्ट रूप से निर्देशित ग्राफ की पहचान नहीं करता है, कुछ स्थितियों में गैर-समरूपी संयुक्ताक्षर में समान डिग्री अनुक्रम होता है।
-संयुक्ताक्षर की प्राप्ति की समस्या सकारात्मक [[पूर्णांक]] जोड़े के दिए गए अनुक्रम के डिग्री अनुक्रम के साथ निर्देशित ग्राफ खोजने की समस्या है। (शून्य के अनुगामी जोड़े को अनदेखा किया जा सकता है क्योंकि वे निर्देशित ग्राफ में उचित संख्या में अलग-अलग कोने जोड़कर तुच्छ रूप से महसूस किए जाते हैं।) अनुक्रम जो कुछ निर्देशित ग्राफ का डिग्री अनुक्रम है, यानी जिसके लिए निर्देशित ग्राफ प्राप्ति समस्या का समाधान है , निर्देशित ग्राफिक या निर्देशित ग्राफिकल अनुक्रम कहा जाता है। इस समस्या को क्लेटमैन-वैंग एल्गोरिथम या फुलकर्सन-चेन-एंस्टी प्रमेय द्वारा हल किया जा सकता है।
+संयुक्ताक्षर की प्राप्ति की समस्या सकारात्मक [[पूर्णांक]] जोड़े के दिए गए अनुक्रम के डिग्री अनुक्रम के साथ निर्देशित ग्राफ खोजने की समस्या है। शून्य के अनुगामी जोड़े को अनदेखा किया जा सकता है क्योंकि वे निर्देशित ग्राफ में उचित संख्या में अलग-अलग कोने जोड़कर तुच्छ रूप से अनुभव किए जाते हैं। अनुक्रम जो कुछ निर्देशित ग्राफ का डिग्री अनुक्रम है, अर्थात जिसके लिए निर्देशित ग्राफ प्राप्ति समस्या का समाधान है, जिसे निर्देशित ग्राफिकल अनुक्रम कहा जाता है। इस समस्या को क्लेटमैन-वैंग एल्गोरिथम और फुलकर्सन-चेन-एंस्टी प्रमेय द्वारा हल किया जा सकता है।
 == निर्देशित ग्राफ कनेक्टिविटी ==
-{{main|Connectivity (graph theory)}}
+{{main|कनेक्टिविटी (ग्राफ सिद्धांत)}}
-निर्देशित ग्राफ कमजोर रूप से जुड़ा हुआ है (या अभी जुड़ा हुआ है<ref>{{harvtxt|Bang-Jensen|Gutin|2000}} p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).</ref>) यदि अप्रत्यक्ष किनारों के साथ ग्राफ के सभी निर्देशित किनारों को बदलकर प्राप्त अप्रत्यक्ष अंतर्निहित ग्राफ [[कनेक्टिविटी (ग्राफ सिद्धांत)]] है।
-निर्देशित ग्राफ [[दृढ़ता से जुड़ा हुआ]] या मजबूत होता है यदि इसमें x से y (और y से x तक) के प्रत्येक जोड़े के लिए निर्देशित पथ होता है {{nobreak|(''x'', ''y'')}}. मजबूत घटक अधिकतम मजबूती से जुड़े सबग्राफ हैं।
+निर्देशित ग्राफ कमजोर रूप से अभी जुड़ा हुआ है<ref>{{harvtxt|Bang-Jensen|Gutin|2000}} p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).</ref> यदि अप्रत्यक्ष किनारों के साथ ग्राफ के सभी निर्देशित किनारों को बदलकर प्राप्त अप्रत्यक्ष अंतर्निहित ग्राफ [[कनेक्टिविटी (ग्राफ सिद्धांत)]] है।
-कनेक्टेड रूटेड ग्राफ (या फ्लो ग्राफ) वह है जहां विशिष्ट रूट शिखर से प्रत्येक शीर्ष के लिए निर्देशित पथ मौजूद होता है।
+निर्देशित ग्राफ [[दृढ़ता से जुड़ा हुआ]] शक्तिशाली होता है, यदि इसमें x से y और y से x तक के प्रत्येक जोड़े के लिए निर्देशित पथ होता है {{nobreak|(''x'', ''y'')}}. मजबूत घटक अधिकतम मजबूती से जुड़े उप ग्राफ हैं।
+जुड़ा हुआ प्रवाह ग्राफ वह है जहां विशिष्ट मूल शिखर से प्रत्येक शीर्ष के लिए निर्देशित पथ उपस्तिथ होता है।
 == यह भी देखें ==
-{{cmn|
+{{cmn|* [[द्विआधारी संबंध]]
-* [[Binary relation]]
+* [[कोट्स ग्राफ]]
-* [[Coates graph]]
+* [[ड्रैकोन |ड्रैकन फ़्लोचार्ट]]
-* [[DRAKON|DRAKON flowchart]]
+* [[फ्लो चार्ट]]
-* [[Flow chart]]
+* [[गोलाकार सेट]]
-* [[Globular set]]
+* [[ग्राफ सिद्धांत की शब्दावली]]
-* [[Glossary of graph theory]]
+* [[ग्राफ स्टाइल शीट्स]]
-* [[Graph Style Sheets]]
+* [[ग्राफ सिद्धांत]]
-* [[Graph theory]]
+* [[ग्राफ (अमूर्त डेटा प्रकार)]]
-* [[Graph (abstract data type)]]
+* [[नेटवर्क सिद्धांत]]
-* [[Network theory]]
+* [[अभिविन्यास (ग्राफ़ सिद्धांत)|अभिविन्यास]]
-* [[Orientation (graph theory)|Orientation]]
+* [[पूर्व आदेश]]
-* [[Preorder]]
+* [[टोपोलॉजिकल सॉर्टिंग]]
-* [[Topological sorting]]
+* [[ग्राफ़ ट्रांसपोज़ करें]]
-* [[Transpose graph]]
+* [[ऊर्ध्वाधर बाधा ग्राफ]]}}
-* [[Vertical constraint graph]]
-}}
 ==टिप्पणियाँ==
@@ Line 139: / Line 137: @@
 ==बाहरी संबंध==
-{{Commons category|Directed graphs}}
+{{DEFAULTSORT:Directed Graph}}
-{{DEFAULTSORT:Directed Graph}}[[Category: निर्देशित रेखांकन]] [[Category: ग्राफ सिद्धांत]] [[Category: ग्राफ डेटा संरचनाएं]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Directed Graph]]
-[[Category:Created On 28/02/2023]]
+[[Category:Commons category link is locally defined|Directed Graph]]
+[[Category:Created On 28/02/2023|Directed Graph]]
+[[Category:Lua-based templates|Directed Graph]]
+[[Category:Machine Translated Page|Directed Graph]]
+[[Category:Multi-column templates|Directed Graph]]
+[[Category:Pages using div col with small parameter|Directed Graph]]
+[[Category:Pages with script errors|Directed Graph]]
+[[Category:Templates Vigyan Ready|Directed Graph]]
+[[Category:Templates that add a tracking category|Directed Graph]]
+[[Category:Templates using TemplateData|Directed Graph]]
+[[Category:Templates using under-protected Lua modules|Directed Graph]]
+[[Category:Wikipedia fully protected templates|Div col]]
+[[Category:ग्राफ डेटा संरचनाएं|Directed Graph]]
+[[Category:ग्राफ सिद्धांत|Directed Graph]]
+[[Category:निर्देशित रेखांकन|Directed Graph]]

Anonymous

Search

निर्देशित ग्राफ: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 17:40, 15 March 2023

Contents

परिभाषा

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

उपवर्ग

पूरक गुणों वाले संयुक्ताक्षर

मूल शब्दावली

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

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

निर्देशित ग्राफ कनेक्टिविटी

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

निर्देशित ग्राफ: Difference between revisions

Latest revision as of 17:40, 15 March 2023

परिभाषा

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

उपवर्ग

पूरक गुणों वाले संयुक्ताक्षर

मूल शब्दावली

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

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

निर्देशित ग्राफ कनेक्टिविटी

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories