ग्राफ (असतत गणित)

छह शीर्षों और सात किनारों वाला एक ग्राफ

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

किनारों को निर्देशित या अप्रत्यक्ष किया जा सकता है। उदाहरण के लिए, यदि शीर्ष किसी पार्टी में लोगों का प्रतिनिधित्व करते हैं, और दो लोगों के बीच हाथ मिलाने से किनारा हो जाता है तो उनके बीच एक किनारा है, तो यह ग्राफ अप्रत्यक्ष है क्योंकि कोई भी व्यक्ति A किसी व्यक्ति B से तभी हाथ मिला सकता है जब B भी A से हाथ मिलाए। इसके विपरीत, यदि किसी व्यक्ति A से किसी व्यक्ति B के किनारे का अर्थ है कि A का B के लिए धन बकाया है, तो यह ग्राफ निर्देशित है, क्योंकि धन देना जरूरी नहीं है।

रेखांकन मूल विषय हैं जिनका अध्ययन ग्राफ सिद्धांत द्वारा किया जाता है। गणित और रासायनिक संरचना के बीच सीधे संबंध के कारण 1878 में जे जे सिल्वेस्टर द्वारा इस अर्थ में "ग्राफ" शब्द का पहली बार उपयोग किया गया था (जिसे उन्होंने रसायन-ग्राफिकल छवि कहा था)।^[2]^[3]

परिभाषाएँ

ग्राफ सिद्धांत में परिभाषाएँ भिन्न होती हैं। ग्राफ़ और संबंधित गणितीय संरचनाओं को परिभाषित करने के कुछ और मुलभुत विधियां निम्नलिखित हैं।

ग्राफ

File:Undirected.svg

तीन शीर्षों और तीन किनारों वाला एक ग्राफ

एक ग्राफ़ (कभी-कभी इसे निर्देशित ग्राफ़ से अलग करने के लिए एक अप्रत्यक्ष ग्राफ़ कहा जाता है, या इसे एक मल्टीग्राफ़ से अलग करने के लिए एक साधारण ग्राफ़ कहा जाता है)^[4]^[5] क्रमित युग्म G = (V, E) है, जहाँ $V$ एक समुच्चय है जिसके अवयवों को कोना कहा जाता है (एकवचन: कोना), और $E$ युग्मित कोनो का एक समूह है, जिसके तत्वों को किनारा (कभी-कभी लिंक या रेखाएं) कहा जाता है।

किनारे ${x, y}$ के शीर्ष $x$ तथा $y$ एक किनारे के अंतिम बिंदु कहलाते हैं। किनारे को $x$ तथा $y$ से मिलाना और $x$ तथा $y$ पर पर आपतित होना कहा जाता है। एक कोने का कोई किनारा नहीं हो सकता है, जिस स्थिति में यह किसी अन्य कोने से जुड़ा नहीं होता है।

एक मल्टीग्राफ एक सामान्यीकरण है जो कई किनारों को समापन बिंदुओं की एक ही जोड़ी की अनुमति देता है। कुछ पाठों में, मल्टीग्राफ को केवल रेखांकन कहा जाता है।^[6]^[7]

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

सामान्यतः, शीर्ष का समुच्चय $V$ परिमित माना जाता है; इसका अर्थ है कि किनारों का समुच्चय भी परिमित है। कभी-कभी अनंत रेखांकन पर विचार किया जाता है, लेकिन अधिक बार इन्हें एक विशेष प्रकार के द्विआधारी संबंध के रूप में देखा जाता है, क्योंकि परिमित रेखांकन पर अधिकांश परिणाम अनंत स्थिति तक विस्तारित नहीं होते हैं, या एक भिन्न प्रमाण की आवश्यकता होती है।

एक खाली ग्राफ एक ऐसा ग्राफ़ होता है जिसमें कोने का एक खाली समुच्चय (और इस तरह किनारों का एक खाली समुच्चय) होता है। एक ग्राफ का क्रम इसके शीर्षों की संख्या $| V |$ होता है. एक ग्राफ का आकार उसके किनारों की संख्या $| E |$ होता है. चूँकि, कुछ संदर्भों में, जैसे कि कलन विधि की अभिकलनात्मक जटिलता को व्यक्त करने के लिए, आकार $| V | + | E |$ (अन्यथा, एक गैर-रिक्त ग्राफ़ का आकार 0 हो सकता है) है। किसी शीर्ष की डिग्री या संयोजकता उसके साथ आपतित किनारों की संख्या है; रेखांकन के लिए ^[1]लूप के साथ, एक लूप को दो बार गिना जाता है।

क्रम $n$ के ग्राफ में, प्रत्येक शीर्ष की अधिकतम घात $n - 1$ है (या $n$ + 1 यदि लूप की अनुमति है, क्योंकि एक लूप घात में 2 का योगदान देता है), और किनारों की अधिकतम संख्या $n (n - 1)/2$ (या $n (n + 1)/2$ यदि लूप की अनुमति है) है।

ग्राफ़ के किनारे कोने पर एक सममित संबंध को परिभाषित करते हैं, जिसे आसन्नता संबंध कहा जाता है। विशेष रूप से, यदि ${x, y}$ एक किनारा है, तो दो शीर्ष $x$ तथा $y$ निकट हैं । एक ग्राफ को उसके आसन्न आव्यूह $A$ द्वारा पूरी तरह से निर्दिष्ट किया जा सकता है, जो कि एक $n \times n$ वर्ग आव्यूह है, जिसमे $A ij$ शीर्ष $i$ से शीर्ष $j$ तक संयोजनों की संख्या निर्दिष्ट करता है. एक साधारण ग्राफ के लिए, $A ij$ या तो 0 है, जो वियोग का संकेत है, या 1, कनेक्शन का संकेत है; इसके अतिरिक्त $A ii = 0$ क्योंकि एक साधारण ग्राफ में एक किनारा एक ही शीर्ष पर प्रारंभ और समाप्त नहीं हो सकता। सेल्फ़-लूप वाले ग्राफ़ कुछ या सभी $A ii$ द्वारा एक सकारात्मक पूर्णांक के बराबर चित्रित किया जाएगा, और मल्टीग्राफ (शीर्षों के बीच कई किनारों के साथ) कुछ या सभी $A ij$ को एक धनात्मक पूर्णांक के बराबर होने की विशेषता होगी। अप्रत्यक्ष रेखांकन में एक सममित आव्यूह (अर्थ $A ij = A ji$ ) आसन्न आव्यूह होगा.

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

File:Directed.svg

तीन शीर्षों और चार निर्देशित किनारों वाला एक निर्देशित ग्राफ़ (डबल तीर प्रत्येक दिशा में किनारे का प्रतिनिधित्व करता है)

एक निर्देशित ग्राफ या दिशा ग्राफ एक ऐसा ग्राफ है जिसमें किनारों का झुकाव होता है।

एक प्रतिबंधित लेकिन शब्द के बहुत सामान्य अर्थ में,^[8] एक निर्देशित ग्राफ एक जोड़ी $G = (V, E)$ है जिसमे सम्मिलित है:

$V$ , शीर्षों का एक समुच्चय (गणित) (जिसे नोड या बिंदु भी कहा जाता है);
$E$ , किनारों का एक समुच्चय (गणित) (जिसे निर्देशित किनारे, निर्देशित लिंक, निर्देशित रेखाएँ, तीर या चाप भी कहा जाता है), जो अलग-अलग कोने के जोड़े हैं: $E\subseteq \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}$ .

अस्पष्टता से बचने के लिए, इस प्रकार की वस्तु को सटीक रूप से निर्देशित सरल ग्राफ कहा जा सकता है।

किनारे में $(x, y)$ में $x$ प्रति $y$ तक निर्देशित, कोने $x$ तथा $y$ को किनारे के अंतिम बिंदु कहलाते हैं, $x$ किनारे की पूंछ और $y$ किनारे का सिर किनारा $x$ तथा $y$ मिलाता है और $x$ और पर $y$ पर आपतित होता है. एक शीर्ष एक ग्राफ़ में उपस्थित हो सकता है और किनारे से संबंधित नहीं हो सकता है। किनारा $(y, x)$ को $(x, y)$ उल्टा किनारा कहा जाता है. उपरोक्त परिभाषा के अनुसार अनुमति नहीं है, एक ही पूंछ और एक ही सिर के साथ दो या दो से अधिक किनारे हैं।

कई किनारों की अनुमति देने वाले शब्द के एक और सामान्य अर्थ में,^[8] एक निर्देशित ग्राफ एक आदेशित त्रिपक्षीय $G = (V, E, ϕ)$ है जिसमे सम्मिलित है:

$V$ , शीर्षों का एक समुच्चय (गणित) (जिसे नोड या बिंदु भी कहा जाता है);
$E$ , किनारों का एक समुच्चय (गणित) (जिसे निर्देशित किनारे, निर्देशित लिंक, निर्देशित रेखाएँ, तीर या चाप भी कहा जाता है);
$ϕ$ , एक घटना फ़ंक्शन प्रत्येक किनारे को कोने की एक ऑर्डर की गई जोड़ी से मैप करता है (अर्थात्, एक एज दो अलग-अलग कोने से जुड़ा होता है): $\phi :E\to \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}$ .

अस्पष्टता से बचने के लिए, इस प्रकार की वस्तु को यथार्थ रूप से निर्देशित मल्टीग्राफ कहा जा सकता है।

एक लूप (ग्राफ थ्योरी) एक किनारा है जो एक शीर्ष को अपने आप से जोड़ता है। उपरोक्त दो परिभाषाओं में परिभाषित निर्देशित ग्राफ़ में लूप नहीं हो सकते, क्योंकि एक लूप एक शीर्ष $x$ से खुद जुड़ता है (एक निर्देशित सरल ग्राफ के लिए) या घटना है (एक निर्देशित मल्टीग्राफ के लिए) $(x,x)$ जो $\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}$ में नहीं है. तो लूप को अनुमति देने के लिए परिभाषाओं का विस्तार किया जाना चाहिए। निर्देशित सरल रेखांकन के लिए, $E$ की परिभाषा को $E\subseteq \{(x,y)\mid (x,y)\in V^{2}\}$ में संशोधित किया जाना चाहिए. $\phi :E\to \{(x,y)\mid (x,y)\in V^{2}\}$ निर्देशित मल्टीग्राफ के लिए, $\phi$ की परिभाषा में संशोधित किया जाना चाहिए . अस्पष्टता से बचने के लिए, इस प्रकार की वस्तुओं को क्रमशः एक निर्देशित सरल ग्राफ अनुमति लूप और एक निर्देशित मल्टीग्राफ अनुमति लूप (या तरकश (गणित) ) कहा जा सकता है।

एक निर्देशित सरल ग्राफ़ के किनारों को अनुमति देने वाले किनारे $G$ , $G$ के शीर्ष पर एक सजातीय संबंध ~ है जिसे $G$ का सन्निकट संबंध कहलाता है . विशेष रूप से, प्रत्येक किनारे के लिए $(x, y)$ , इसके अंतिम बिंदु $x$ तथा $y$ को आसन्न कहा जाता है एक दूसरे के लिए, जिसे $x ~ y$ द्वारा निरूपित किया जाता है।

मिश्रित ग्राफ

एक मिश्रित ग्राफ एक ऐसा ग्राफ है जिसमें कुछ किनारे निर्देशित हो सकते हैं और कुछ अप्रत्यक्ष हो सकते हैं। यह एक आदेशित त्रिपक्षीय $G = (V, E, A)$ है $V$ , $E$ (अप्रत्यक्ष किनारे) के साथ मिश्रित सरल ग्राफ के लिए $G = (V, E, A, ϕ E, ϕ A)$ निर्देशित किनारों), $ϕ E$ तथा $ϕ A$ ऊपर के रूप में परिभाषित किया गया है। निर्देशित और अप्रत्यक्ष रेखांकन विशेष स्थिति हैं।

भारित ग्राफ

File:Weighted network.svg

दस शीर्षों और बारह किनारों वाला एक भारित ग्राफ

एक भारित ग्राफ या एक संजाल^[9]^[10] एक ग्राफ है जिसमें प्रत्येक किनारे पर एक संख्या (वजन) निर्दिष्ट की जाती है।^[11]^[12] * विशेष रूप से निर्देशित ग्राफ़ के नियमित उदाहरण केली ग्राफ द्वारा अंतिम रूप से उत्पन्न समूहों के साथ-साथ श्रेयर कॉस्टेट ग्राफ द्वारा दिए गए हैं

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

रेखांकन के प्रकार

ओरिएंटेड ग्राफ

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

सामान्य ग्राफ

सामान्य ग्राफ एक ऐसा ग्राफ होता है जिसमें प्रत्येक शीर्ष के पड़ोसियों की संख्या समान होती है, अर्थात प्रत्येक शीर्ष की एक ही डिग्री होती है। डिग्री k के शीर्ष वाले सामान्य ग्राफ़ को k-सामान्य ग्राफ़ या डिग्री k का सामान्य ग्राफ़ कहा जाता है।

पूरा ग्राफ

File:Complete graph K5.svg

पाँच शीर्षों और दस किनारों वाला एक पूर्ण ग्राफ़। प्रत्येक शीर्ष का प्रत्येक दूसरे शीर्ष से किनारा होता है।

पूर्ण ग्राफ़ एक ऐसा ग्राफ़ होता है जिसमें प्रत्येक जोड़ी को एक किनारे से जोड़ा जाता है। एक पूर्ण ग्राफ़ में सभी संभावित किनारे होते हैं।

परिमित ग्राफ

परिमित ग्राफ एक ऐसा ग्राफ है जिसमें वर्टेक्स सेट और एज सेट परिमित सेट होते हैं। अन्यथा, इसे अनंत ग्राफ कहा जाता है। आमतौर पर ग्राफ़ सिद्धांत में यह निहित है कि चर्चा की गई रेखांकन परिमित हैं। यदि रेखांकन अनंत हैं, तो यह आमतौर पर विशेष रूप से कहा जाता है।

कनेक्टिविटी (ग्राफ सिद्धांत)

अप्रत्यक्ष ग्राफ़ में, वर्टिकल का एक अनियंत्रित युग्म {x, y} को कनेक्टेड कहा जाता है यदि कोई पथ x से y की ओर जाता है। अन्यथा, अक्रमित जोड़ी को डिस्कनेक्टेड कहा जाता है। एक कनेक्टेड ग्राफ़ एक अप्रत्यक्ष ग्राफ़ है जिसमें ग्राफ़ में प्रत्येक अनियंत्रित युग्म जुड़ा हुआ है। अन्यथा, इसे डिस्कनेक्टेड ग्राफ़ कहा जाता है। निर्देशित ग्राफ़ में, शीर्षों का एक क्रमित युग्म (x, y) यदि एक निर्देशित पथ x से y की ओर जाता है तो दृढ़ता से जुड़ा हुआ कहा जाता है। अन्यथा, आदेशित जोड़ी को कमजोर रूप से जुड़ा हुआ कहा जाता है यदि एक अप्रत्यक्ष पथ अपने सभी निर्देशित किनारों को अप्रत्यक्ष किनारों से बदलने के बाद x से y की ओर जाता है। अन्यथा, आदेशित जोड़ी को डिस्कनेक्ट किया गया कहा जाता है। एक दृढ़ता से कनेक्टिविटी (ग्राफ सिद्धांत) एक निर्देशित ग्राफ है जिसमें ग्राफ में प्रत्येक क्रमित युग्म दृढ़ता से जुड़ा हुआ है। अन्यथा, इसे कमजोर रूप से कनेक्टिविटी (ग्राफ सिद्धांत) कहा जाता है, अगर ग्राफ में प्रत्येक क्रमित युग्म कमजोर रूप से जुड़ा हुआ है। अन्यथा इसे डिस्कनेक्टेड ग्राफ कहा जाता है। एक के-वर्टेक्स-कनेक्टेड ग्राफ़ या के-एज-कनेक्टेड ग्राफ़ एक ग्राफ़ है जिसमें कोई सेट नहीं है k − 1 कोने (क्रमशः, किनारे) मौजूद होते हैं, जिन्हें हटाए जाने पर, ग्राफ़ को डिस्कनेक्ट कर देता है। एक k-वर्टेक्स-कनेक्टेड ग्राफ़ को अक्सर केवल k-कनेक्टेड ग्राफ़ कहा जाता है।

द्विपक्षीय ग्राफ

द्विपक्षीय ग्राफ एक सरल ग्राफ है जिसमें वर्टेक्स सेट एक सेट का दो सेटों, W और X में विभाजन हो सकता है, ताकि W में कोई भी दो कोने एक सामान्य किनारे को साझा न करें और X में कोई भी दो कोने एक सामान्य किनारे को साझा न करें। वैकल्पिक रूप से, यह 2 की रंगीन संख्या वाला एक ग्राफ है। एक पूर्ण द्विपक्षीय ग्राफ में, वर्टेक्स सेट दो अलग-अलग सेटों, W और X का मिलन होता है, ताकि W में प्रत्येक शीर्ष X में प्रत्येक शीर्ष के निकट हो, लेकिन W या X के भीतर कोई किनारा न हो।

पाथ ग्राफ

एक पाथ ग्राफ या आदेश का रैखिक ग्राफ n ≥ 2 एक ग्राफ है जिसमें शीर्षों को एक क्रम v में सूचीबद्ध किया जा सकता है₁, में₂, …, में_n ऐसे कि किनारे हैं {v_i, v_i+1} जहां i = 1, 2, ..., n - 1. पाथ ग्राफ़ को कनेक्टेड ग्राफ़ के रूप में वर्णित किया जा सकता है जिसमें दो शीर्षों को छोड़कर सभी की डिग्री 2 है और दो शेष शीर्षों की डिग्री 1 है। यदि पाथ ग्राफ़ के रूप में होता है ग्राफ थ्योरी की शब्दावली # दूसरे ग्राफ के सबग्राफ, यह उस ग्राफ में एक पाथ (ग्राफ थ्योरी) है।

प्लानर ग्राफ

प्लेनर ग्राफ एक ऐसा ग्राफ है जिसके कोने और किनारों को एक समतल में खींचा जा सकता है जैसे कि किनारों में से कोई भी एक दूसरे को नहीं काटता है।

चक्र ग्राफ

चक्र ग्राफ या आदेश का परिपत्र ग्राफ n ≥ 3 एक ग्राफ है जिसमें शीर्षों को एक क्रम v में सूचीबद्ध किया जा सकता है v₁, v₂, …, v_n ऐसे कि किनारे हैं {v_i, v_i+1} जहां i = 1, 2, ..., n − 1, प्लस किनारा {v_n, v₁}. साइकिल ग्राफ़ को कनेक्टेड ग्राफ़ के रूप में चित्रित किया जा सकता है जिसमें सभी कोने की डिग्री 2 है। यदि एक चक्र ग्राफ़ दूसरे ग्राफ़ के सबग्राफ के रूप में होता है, तो यह उस ग्राफ़ में एक चक्र या सर्किट होता है।

ट्री

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

पॉलीट्री

पॉलीट्री (या निर्देशित ट्री या उन्मुख ट्री या अकेले जुड़े नेटवर्क) एक निर्देशित अचक्रीय ग्राफ (डीएजी) है जिसका अंतर्निहित अप्रत्यक्ष ग्राफ एक ट्री है। एक पॉलीफॉरेस्ट (या निर्देशित वन या उन्मुख वन) एक निर्देशित चक्रीय ग्राफ है जिसका अंतर्निहित अप्रत्यक्ष ग्राफ एक जंगल है।

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Anonymous

Search