मल्टीग्राफ

This article is about the mathematical concept. For other uses, see मल्टीग्राफ (disambiguation).

"Pseudograph" redirects here. Not to be confused with Pseudepigraph.

एकाधिक किनारों (लाल) और कई लूप (नीला) के साथ एक मल्टीग्राफ। सभी लेखक मल्टीग्राफ को लूप की अनुमति नहीं देते हैं।

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

एकाधिक किनारों की दो अलग-अलग धारणाएँ हैं:

• किनारे बिना अपनी पहचान के: किनारे की पहचान पूरी तरह से उन दो नोड्स द्वारा परिभाषित की जाती है जो इसे जोड़ती हैं। इस मामले में, एकाधिक किनारों का अर्थ है कि एक ही किनारा इन दो नोड्स के बीच कई बार हो सकता है।
• स्वयं की पहचान वाले किनारे: किनारे नोड्स की तरह ही आदिम संस्थाएँ हैं। जब कई किनारे दो नोड्स को जोड़ते हैं, तो ये अलग-अलग किनारे होते हैं।

एक मल्टीग्राफ एक हाइपरग्राफ से अलग है, जो एक ऐसा ग्राफ है जिसमें एक किनारा केवल दो नहीं, बल्कि किसी भी संख्या में नोड्स को जोड़ सकता है।

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

अप्रत्यक्ष मल्टीग्राफ (अपनी पहचान के बिना किनारों)

मल्टीग्राफ G एक क्रमित युग्म G:= (V, E) है

• V कोने या नोड्स का एक सेट (गणित),
• E शीर्षों के अक्रमित युग्मों का एक बहुसमूह है, जिन्हें किनारे या रेखाएँ कहा जाता है।

अप्रत्यक्ष मल्टीग्राफ (स्वयं की पहचान वाले किनारे)

मल्टीग्राफ G एक क्रमित ट्रिपल (गणित) G := (V, E, r) है

• V कोने या नोड्स का एक सेट (गणित),
• ई किनारों या रेखाओं का एक सेट (गणित),
• r : E → {{x,y} : x, y ∈ V}, प्रत्येक किनारे को एंडपॉइंट नोड्स की एक अनियंत्रित जोड़ी असाइन करना।

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

निर्देशित मल्टीग्राफ (अपनी पहचान के बिना किनारे)

एक मल्टीडिग्राफ एक निर्देशित ग्राफ है जिसे एकाधिक चाप रखने की अनुमति है, यानी एक ही स्रोत और लक्ष्य नोड्स के साथ चाप। एक मल्टीडिग्राफ जी एक क्रमित जोड़ी जी := (वी, ए) के साथ है

• वी कोने या नोड्स का एक सेट,
• A डायरेक्टेड एज, आर्क्स या एरो कहे जाने वाले वर्टिकल के ऑर्डर किए गए जोड़े का एक मल्टीसेट है।

एक मिश्रित मल्टीग्राफ जी := (वी, ई, ए) को मिश्रित ग्राफ की तरह ही परिभाषित किया जा सकता है।

निर्देशित मल्टीग्राफ (स्वयं की पहचान वाले किनारे)

एक मल्टीडिग्राफ या तरकश (गणित) G एक क्रमित tuple|4-tuple G := (V, A, s, t) के साथ है

• V कोने या नोड्स का एक सेट (गणित),
• किनारों या रेखाओं का एक सेट (गणित),
• $s:A\rightarrow V$, प्रत्येक किनारे को इसका स्रोत नोड निर्दिष्ट करना,
• $t:A\rightarrow V$, प्रत्येक किनारे को अपना लक्ष्य नोड निर्दिष्ट करना।

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

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

लेबलिंग

मल्टीग्राफ और मल्टीडिग्राफ भी इसी तरह ग्राफ लेबलिंग की धारणा का समर्थन करते हैं। हालाँकि इस मामले में शब्दावली में कोई एकता नहीं है।

लेबल किए गए मल्टीग्राफ और लेबल किए गए मल्टीडिग्राफ की परिभाषाएं समान हैं, और हम यहां केवल बाद वाले को परिभाषित करते हैं।

परिभाषा 1: एक लेबल किया हुआ मल्टीडिग्राफ एक लेबल वाला ग्राफ है जिसमें लेबल चाप होते हैं।

औपचारिक रूप से: एक लेबल वाला मल्टीडिग्राफ जी एक मल्टीग्राफ है जिसमें लेबल कोने और चाप होते हैं। औपचारिक रूप से यह 8-ट्यूपल है $G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})$ कहाँ

• V शीर्षों का समुच्चय है और A चापों का समुच्चय है।
• $\Sigma _{V}$ और $\Sigma _{A}$ उपलब्ध वर्टेक्स और आर्क लेबल के परिमित अक्षर हैं,
• $s\colon A\rightarrow \ V$ और $t\colon A\rightarrow \ V$ एक चाप के स्रोत और लक्ष्य शीर्ष को दर्शाने वाले दो नक्शे हैं,
• $\ell _{V}\colon V\rightarrow \Sigma _{V}$ और $\ell _{A}\colon A\rightarrow \Sigma _{A}$ शीर्षों और चापों की लेबलिंग का वर्णन करने वाले दो मानचित्र हैं।

परिभाषा 2: एक लेबल मल्टीडिग्राफ एक लेबल वाला ग्राफ है जिसमें कई लेबल वाले आर्क होते हैं, यानी एक ही अंत के कोने और एक ही आर्क लेबल के साथ आर्क (ध्यान दें कि लेबल किए गए ग्राफ की यह धारणा लेख ग्राफ लेबलिंग द्वारा दी गई धारणा से अलग है)।

यह भी देखें

• बहुआयामी नेटवर्क
• ग्राफ सिद्धांत शब्दों की शब्दावली
• ग्राफ सिद्धांत

संदर्भ

• Balakrishnan, V. K. (1997). Graph Theory. McGraw-Hill. ISBN 0-07-005489-4.
• Bollobás, Béla (2002). Modern Graph Theory. Graduate Texts in Mathematics. Vol. 184. Springer. ISBN 0-387-98488-7.
• Chartrand, Gary; Zhang, Ping (2012). A First Course in Graph Theory. Dover. ISBN 978-0-486-48368-9.
• Diestel, Reinhard (2010). Graph Theory. Graduate Texts in Mathematics. Vol. 173 (4th ed.). Springer. ISBN 978-3-642-14278-9.
• Gross, Jonathan L.; Yellen, Jay (1998). Graph Theory and Its Applications. CRC Press. ISBN 0-8493-3982-0.
• Gross, Jonathan L.; Yellen, Jay, eds. (2003). Handbook of Graph Theory. CRC. ISBN 1-58488-090-2.
• Harary, Frank (1995). Graph Theory. Addison Wesley. ISBN 0-201-41033-8.
• Janson, Svante; Knuth, Donald E.; Luczak, Tomasz; Pittel, Boris (1993). "The birth of the giant component". Random Structures and Algorithms. 4 (3): 231–358. arXiv:math/9310236. Bibcode:1993math.....10236J. doi:10.1002/rsa.3240040303. ISSN 1042-9832. MR 1220220. S2CID 206454812.
• Wilson, Robert A. (2002). Graphs, Colourings and the Four-Colour Theorem. Oxford Science Publ. ISBN 0-19-851062-4.
• Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulae (31st ed.). Chapman & Hall/CRC. ISBN 1-58488-291-3.

बाहरी संबंध

•  This article incorporates public domain material from Black, Paul E. "Multigraph". Dictionary of Algorithms and Data Structures.