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

{{about|किनारों से जुड़े हुए शीर्षों का समूह|गणितीय कार्यों के रेखांकन|किसी फलन का ग्राफ़|अन्य प्रयोग|ग्राफ (बहुविकल्पी)}}
{{short description|Vertices connected in pairs by edges}}
[[File:6n-graf.svg|thumb|छह शीर्षों और सात किनारों वाला एक ग्राफ]]असतत गणित में, और अधिक विशेष रूप शीर्ष ([[ग्राफ सिद्धांत]]) में, एक ग्राफ एक संरचना है जो वस्तुओं के एक [[सेट (गणित)|समुच्चय (गणित)]] के बराबर होती है जिसमें वस्तुओं के कुछ जोड़े कुछ अर्थों में संबंधित होते हैं। वस्तुएं  गणितीय सार के अनुरूप होते है जिसे ''कोने (ग्राफ थ्योरी) '' (जिसे 'नोड्स' या '' पॉइंट्स '' भी कहा जाता है) कहा जाता है, और कोने के प्रत्येक संबंधित जोड़े को प्रत्येक को 'किनारा' (जिसे लिंक या लाइन भी कहा जाता है) कहा जाता है।<ref name=":0">{{cite book|last=Trudeau|first=Richard J.|title=ग्राफ थ्योरी का परिचय|year=1993|publisher=Dover Pub.|location=New York|isbn=978-0-486-67870-2|pages=19|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|access-date=8 August 2012|quote=ग्राफ़ एक ऑब्जेक्ट होता है जिसमें दो सेट होते हैं जिन्हें इसका ''वर्टेक्स सेट'' और इसका ''एज सेट'' कहा जाता है।}}</ref> सामान्यतः, एक ग्राफ को [[आरेखीय रूप]] में बिंदुओं या वृतो के एक समुच्चेय के रूप में चित्रित किया जाता है, जो किनारों के लिए रेखाओं या वक्रों से जुड़ा होता है। रेखांकन असतत गणित में अध्ययन की वस्तुओं में से एक है।

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

रेखांकन मूल विषय हैं जिनका अध्ययन ग्राफ सिद्धांत द्वारा किया जाता है। गणित और [[रासायनिक संरचना]] के बीच सीधे संबंध के कारण 1878 में जे जे सिल्वेस्टर द्वारा इस अर्थ में "ग्राफ" शब्द का पहली बार उपयोग किया गया था (जिसे उन्होंने रसायन-ग्राफिकल छवि कहा था)।<ref>See:
*J. J. Sylvester (February 7, 1878) [https://books.google.com/books?id=KcoKAAAAYAAJ&vq=Sylvester&pg=PA284#v=onepage&q&f=false "Chemistry and algebra,"] ''Nature'', ''17'' : 284. {{doi|10.1038/017284a0}}. From page 284: "Every invariant and covariant thus becomes expressible by a ''graph'' precisely identical with a Kekuléan diagram or chemicograph."
*J. J. Sylvester (1878) [https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64#v=onepage&q&f=false "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices,"] ''American Journal of Mathematics, Pure and Applied'', ''1'' (1) : 64–90. {{doi|10.2307/2369436}}. {{JSTOR|2369436}}. The term "graph" first appears in this paper on page 65.</ref><ref>{{Cite book
 | title = ग्राफ सिद्धांत की पुस्तिका| first1 = Jonathan L.
 | last1 = Gross
 | first2 = Jay
 | last2 = Yellen
 | publisher = [[CRC Press]]
 | year = 2004
 | page = [https://books.google.com/books?id=mKkIGIea_BkC&pg=PA35&lpg=PA35 35]
 | isbn = 978-1-58488-090-5
 | url = https://books.google.com/books?id=mKkIGIea_BkC
 }}</ref>


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

=== {{anchor|Undirected graph}} ग्राफ ===
[[File:Undirected.svg|thumb|तीन शीर्षों और तीन किनारों वाला एक ग्राफ]]'' एक ग्राफ़ (कभी-कभी इसे निर्देशित ग्राफ़ से अलग करने के लिए एक अप्रत्यक्ष ग्राफ़ कहा जाता है, या इसे एक मल्टीग्राफ़ से अलग करने के लिए एक साधारण ग्राफ़ कहा जाता है){{sfn|Bender|Williamson|2010|p=148}}<ref>See, for instance, Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.</ref> [[क्रमित युग्म]]  {{math|1=''G'' = (''V'', ''E'') है}}, जहाँ  {{mvar|V}} एक समुच्चय है जिसके अवयवों को कोना कहा जाता है (एकवचन: कोना), और {{mvar|E}} युग्मित कोनो का एक समूह है, जिसके तत्वों को किनारा (कभी-कभी लिंक या रेखाएं) कहा जाता है।

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

एक मल्टीग्राफ एक सामान्यीकरण है जो कई किनारों को समापन बिंदुओं की एक ही जोड़ी की अनुमति देता है। कुछ पाठों में, मल्टीग्राफ को केवल रेखांकन कहा जाता है।{{sfn|Bender|Williamson|2010|p=149}}<ref>Graham et al., p. 5.</ref>

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

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

एक [[खाली ग्राफ]] एक ऐसा ग्राफ़ होता है जिसमें कोने का एक [[खाली सेट|खाली समुच्चय]] (और इस तरह किनारों का एक खाली समुच्चय) होता है। एक ग्राफ का क्रम इसके शीर्षों की संख्या {{math|{{abs|''V''}}}} होता है. एक ग्राफ का आकार उसके किनारों की संख्या {{math|{{abs|''E''}}}} होता है. चूँकि, कुछ संदर्भों में, जैसे कि कलन विधि की अभिकलनात्मक जटिलता को व्यक्त करने के लिए, आकार {{math|{{abs|''V''}} + {{abs|''E''}}}} (अन्यथा, एक गैर-रिक्त ग्राफ़ का आकार 0 हो सकता है) है। किसी शीर्ष की डिग्री या संयोजकता उसके साथ आपतित किनारों की संख्या है; रेखांकन के लिए <ref name=":0" />लूप के साथ, एक लूप को दो बार गिना जाता है।

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

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

=== निर्देशित ग्राफ ===
{{main|निर्देशित ग्राफ}}
[[File:Directed.svg|thumb|तीन शीर्षों और चार निर्देशित किनारों वाला एक निर्देशित ग्राफ़ (डबल तीर प्रत्येक दिशा में किनारे का प्रतिनिधित्व करता है)]]एक निर्देशित ग्राफ या दिशा ग्राफ एक ऐसा ग्राफ है जिसमें किनारों का झुकाव होता है।

एक प्रतिबंधित लेकिन शब्द के बहुत सामान्य अर्थ में,{{sfn|Bender|Williamson|2010|p=161}} एक निर्देशित ग्राफ एक जोड़ी {{math|1=''G'' = (''V'', ''E'')}} है जिसमे  सम्मिलित है:
* {{mvar|V}}, शीर्षों का एक समुच्चय (गणित) (जिसे नोड या बिंदु भी कहा जाता है);
* {{mvar|E}}, किनारों का एक समुच्चय (गणित) (जिसे निर्देशित किनारे, निर्देशित लिंक, निर्देशित रेखाएँ, तीर या चाप भी कहा जाता है), जो अलग-अलग कोने के जोड़े हैं: <math>E \subseteq \{(x,y) \mid (x,y) \in V^2 \;\textrm{ and }\; x \neq y \}</math>.
अस्पष्टता से बचने के लिए, इस प्रकार की वस्तु को सटीक रूप से निर्देशित सरल ग्राफ कहा जा सकता है।

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

कई किनारों की अनुमति देने वाले शब्द के एक और सामान्य अर्थ में,{{sfn|Bender|Williamson|2010|p=161}} एक निर्देशित ग्राफ एक आदेशित त्रिपक्षीय  {{math|1=''G'' = (''V'', ''E'', ''ϕ'')}} है जिसमे सम्मिलित है:
* {{mvar|V}}, शीर्षों का एक समुच्चय (गणित) (जिसे नोड या बिंदु भी कहा जाता है);
* {{mvar|E}}, किनारों का एक समुच्चय (गणित) (जिसे निर्देशित किनारे, निर्देशित लिंक, निर्देशित रेखाएँ, तीर या चाप भी कहा जाता है);
* {{mvar|ϕ}}, एक घटना फ़ंक्शन प्रत्येक किनारे को कोने की एक ऑर्डर की गई जोड़ी से मैप करता है (अर्थात्, एक एज दो अलग-अलग कोने से जुड़ा होता है): <math>\phi : E \to \{(x,y) \mid (x,y) \in V^2 \;\textrm{ and }\; x \neq y \}</math>.

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

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

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

=== मिश्रित ग्राफ ===
{{main|मिश्रित ग्राफ}}

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

=== भारित ग्राफ ===
[[File:Weighted_network.svg|thumb|दस शीर्षों और बारह किनारों वाला एक भारित ग्राफ]]एक भारित ग्राफ या एक संजाल<ref>{{Citation | last=Strang | first=Gilbert | title=Linear Algebra and Its Applications | publisher=Brooks Cole | edition=4th | year=2005 | isbn=978-0-03-010567-8 | url=https://books.google.com/books?id=ISBN0030105676 }}</ref><ref>{{Citation | last=Lewis | first=John | title=Java Software Structures | publisher=Pearson | edition=4th | year=2013 | isbn=978-0133250121 | page=405 }}</ref> एक ग्राफ है जिसमें प्रत्येक किनारे पर एक संख्या (वजन) निर्दिष्ट की जाती है।<ref>{{cite book|last1=Fletcher|first1=Peter|last2=Hoyle|first2=Hughes|last3=Patty|first3=C. Wayne|title=असतत गणित की नींव|year=1991|publisher=PWS-KENT Pub. Co.| location=Boston| isbn=978-0-53492-373-0| pages=463 | edition=International student|quote=एक ''वेटेड ग्राफ़'' एक ग्राफ़ है जिसमें एक संख्या ''w''(''e''), जिसे उसका ''वेट'' कहा जाता है, प्रत्येक किनारे ''e'' को निर्दिष्ट किया जाता है।}}

</ref><ref name="twitterwtf">Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh [http://dl.acm.org/citation.cfm?id=2488433 WTF: The who-to-follow system at Twitter], ''Proceedings of the 22nd international conference on World Wide Web''. {{doi|10.1145/2488388.2488433}}.</ref> * विशेष रूप से निर्देशित ग्राफ़ के नियमित उदाहरण [[केली ग्राफ]] द्वारा अंतिम रूप से उत्पन्न समूहों के साथ-साथ [[श्रेयर कॉस्टेट ग्राफ]] द्वारा दिए गए हैं
*श्रेणी के सिद्धांत में, प्रत्येक [[छोटी श्रेणी]] में एक अंतर्निहित निर्देशित मल्टीग्राफ होता है, जिसके कोने श्रेणी की वस्तुएं हैं, और जिनके किनारे श्रेणी के तीर हैं। श्रेणी सिद्धांत की भाषा में कहा जाता है कि [[छोटी श्रेणियों की श्रेणी]] से लेकर तरकश (गणित) तक एक भुलक्कड़ फनकार है।

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

===सामान्य ग्राफ===
{{main|सामान्य ग्राफ}}

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

===पूरा ग्राफ===
{{main|पूर्ण ग्राफ़}}[[File:Complete graph K5.svg|thumb|125px|पाँच शीर्षों और दस किनारों वाला एक पूर्ण ग्राफ़। प्रत्येक शीर्ष का प्रत्येक दूसरे शीर्ष से किनारा होता है।]]पूर्ण ग्राफ़ एक ऐसा ग्राफ़ होता है जिसमें प्रत्येक जोड़ी को एक किनारे से जोड़ा जाता है। एक पूर्ण ग्राफ़ में सभी संभावित किनारे होते हैं।

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

===कनेक्टिविटी (ग्राफ सिद्धांत)===
{{main|Connectivity (graph theory)}}

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

===द्विपक्षीय ग्राफ===
{{main|द्विपक्षीय ग्राफ}}

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

===पाथ ग्राफ===
{{main|पाथ ग्राफ}}

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

===प्लानर ग्राफ===
{{main|प्लानर ग्राफ}}

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

===चक्र ग्राफ===
{{main|चक्र ग्राफ}}

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

===ट्री===
{{main|ट्री (ग्राफ सिद्धांत)}}

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

===पॉलीट्री===
{{main|पॉलीट्री}}

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

===उन्नत कक्षाएं===
अधिक उन्नत प्रकार के रेखांकन हैं:
*[[पीटरसन ग्राफ]] और इसके सामान्यीकरण;
*सही रेखांकन;
*[[कोग्राफ]];
*कॉर्डल रेखांकन;
*बड़े [[ग्राफ ऑटोमोर्फिज्म]] के साथ अन्य ग्राफ़: [[वर्टेक्स-सकर्मक ग्राफ]]|वर्टेक्स-ट्रांसिटिव, [[चाप-सकर्मक ग्राफ]]|आर्क-ट्रांसिटिव, और [[दूरी-सकर्मक ग्राफ]];
*दृढ़ता से नियमित रेखांकन और उनके सामान्यीकरण दूरी-नियमित रेखांकन।
==रेखांकन के गुण==
{{see also|ग्राफ सिद्धांत शब्दावली|ग्राफ प्रॉपर्टी}}

ग्राफ के दो किनारों को सन्निकट कहा जाता है यदि वे एक सामान्य शीर्ष साझा करते हैं। निर्देशित ग्राफ़ के दो किनारों को लगातार कहा जाता है यदि पहले वाले का सिर दूसरे की पूंछ है। इसी तरह, दो शीर्षों को आसन्न कहा जाता है यदि वे एक सामान्य किनारे को साझा करते हैं (लगातार यदि पहला एक पूंछ है और दूसरा एक किनारे का सिर है), इस मामले में सामान्य किनारे को दो शीर्षों में शामिल होने के लिए कहा जाता है। एक किनारे और उस किनारे पर एक शीर्ष घटना कहलाती है। केवल एक शीर्ष और बिना किनारे वाले ग्राफ को तुच्छ ग्राफ कहा जाता है। एक ग्राफ जिसमें केवल कोने होते हैं और कोई किनारा नहीं होता है, उसे किनारे रहित ग्राफ के रूप में जाना जाता है। बिना कोने और किनारों वाले ग्राफ़ को कभी-कभी [[शून्य ग्राफ]]़ या खाली ग्राफ़ कहा जाता है, लेकिन शब्दावली सुसंगत नहीं है और सभी गणितज्ञ इस वस्तु की अनुमति नहीं देते हैं। आम तौर पर, एक ग्राफ के कोने, एक सेट के तत्वों के रूप में उनकी प्रकृति से, अलग-अलग होते हैं। इस तरह के ग्राफ को वर्टेक्स-लेबल कहा जा सकता है। हालांकि, कई प्रश्नों के लिए शीर्षों को अप्रभेद्य मानना बेहतर है। (बेशक, शीर्ष अभी भी ग्राफ़ के गुणों द्वारा अलग-अलग हो सकते हैं, उदाहरण के लिए, घटना किनारों की संख्या से।) वही टिप्पणी किनारों पर लागू होती है, इसलिए लेबल वाले किनारों वाले ग्राफ़ को किनारे-लेबल कहा जाता है। किनारों या कोने से जुड़े लेबल वाले ग्राफ़ को आमतौर पर लेबल के रूप में निर्दिष्ट किया जाता है। नतीजतन, ऐसे ग्राफ़ जिनमें कोने अप्रभेद्य होते हैं और किनारे अप्रभेद्य होते हैं, उन्हें लेबल रहित कहा जाता है। (साहित्य में, लेबल किया गया शब्द अन्य प्रकार के लेबलिंग पर भी लागू हो सकता है, इसके अलावा जो केवल विभिन्न कोने या किनारों को अलग करने के लिए कार्य करता है।) सभी ग्राफ़ का [[श्रेणी सिद्धांत]] [[अल्पविराम श्रेणी]] सेट ↓ D है जहाँ D: सेट → सेट एक सेट s को s × s पर ले जाने वाला [[ऑपरेटर]] है।

==उदाहरण==
[[File:6n-graf.svg|thumb|छह शीर्षों और सात किनारों वाला एक ग्राफ]]* आरेख शीर्षों के साथ ग्राफ का एक योजनाबद्ध प्रतिनिधित्व है <math>V = \{1, 2, 3, 4, 5, 6\}</math> और किनारों <math>E = \{\{1, 2\}, \{1, 5\}, \{2, 3\}, \{2, 5\}, \{3, 4\}, \{4, 5\}, \{4, 6\}\}.</math>
*[[कंप्यूटर विज्ञान]] में, निर्देशित रेखांकन का उपयोग ज्ञान (जैसे, [[वैचारिक ग्राफ]]), परिमित राज्य मशीनों और कई अन्य असतत संरचनाओं का प्रतिनिधित्व करने के लिए किया जाता है।
*एक सेट एक्स पर एक बाइनरी रिलेशन आर एक निर्देशित ग्राफ को परिभाषित करता है। X का एक तत्व x, X के एक तत्व y का प्रत्यक्ष पूर्ववर्ती है यदि और केवल यदि xRy।
*एक निर्देशित ग्राफ [[ट्विटर]] जैसे सूचना नेटवर्क को मॉडल कर सकता है, जिसमें एक उपयोगकर्ता दूसरे का अनुसरण करता है।
== ग्राफ संचालन ==
{{main|ग्राफ संचालन}}
ऐसे कई ऑपरेशन हैं जो प्रारंभिक से नए ग्राफ़ बनाते हैं, जिन्हें निम्नलिखित श्रेणियों में वर्गीकृत किया जा सकता है:
* एकात्मक संचालन, जो प्रारंभिक एक से एक नया ग्राफ बनाते हैं, जैसे:
** किनारा संकुचन,
** [[लाइन ग्राफ|पंक्ति ग्राफ]],
** [[दोहरा ग्राफ]],
** [[पूरक ग्राफ]],
** [[ग्राफ पुनर्लेखन]];
* द्विआधारी संचालन, जो दो प्रारंभिक लोगों से एक नया ग्राफ बनाते हैं, जैसे:
** रेखांकन का संघ अलग करना,
** [[रेखांकन का कार्टेशियन उत्पाद|रेखांकन का कार्तीय उत्पाद]],
** [[रेखांकन का टेंसर उत्पाद|रेखांकन का प्रदिश उत्पाद]],
** [[रेखांकन का मजबूत उत्पाद]],
** रेखांकन का शब्दकोष उत्पाद,
** श्रृंखला-समानांतर रेखांकन।

== सामान्यीकरण ==
[[hypergraph|हाइपर ग्राफ]] में, एक किनारा दो से अधिक शीर्षों को जोड़ सकता है।

एक अप्रत्यक्ष ग्राफ को [[सिंप्लेक्स|सरल जटिल]] (किनारों) और 0-सरलता (कोने) से मिलकर एक साधारण परिसर के रूप में देखा जा सकता है। जैसे, जटिल ग्राफ़ के सामान्यीकरण हैं क्योंकि वे उच्च-आयामी सरलताओं की अनुमति देते हैं।

हर ग्राफ एक [[matroid|मैट्रोइड]] को जन्म देता है।

[[मॉडल सिद्धांत]] में, एक ग्राफ केवल एक [[संरचना (मॉडल सिद्धांत)]] है। लेकिन उस स्थिति में, किनारों की संख्या पर कोई सीमा नहीं है: यह कोई भी मुख्य संख्या हो सकती है, [[निरंतर ग्राफ]] देखें।

[[कम्प्यूटेशनल बायोलॉजी|संगणनात्मक जीवविज्ञान]] विज्ञान में, घात ग्राफ़ विश्लेषण अप्रत्यक्ष ग्राफ़ के वैकल्पिक प्रतिनिधित्व के रूप में घात ग्राफ़ का परिचय देता है।

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

== यह भी देखें ==
* वैचारिक ग्राफ
* ग्राफ (सार डेटा प्रकार)
* [[ग्राफ डेटाबेस]]
* [[ग्राफ ड्राइंग]]
* [[ग्राफ सिद्धांत विषयों की सूची]]
* गणित में प्रकाशनों की सूची#ग्राफ सिद्धांत
* [[नेटवर्क सिद्धांत]]

== टिप्पणियाँ ==
{{reflist|30em}}


== संदर्भ ==
* {{cite book |last=Balakrishnan |first=V. K. |date=1997 |title=Graph Theory|publisher=McGraw-Hill |edition=1st|isbn=978-0-07-005489-9}}
* {{cite book |last1=Bang-Jensen |first1=J. |last2=Gutin |first2=G. |date=2000 |title=Digraphs: Theory, Algorithms and Applications |url=http://www.cs.rhul.ac.uk/books/dbook/ |publisher=Springer }}
* {{cite book |last1=Bender |first1=Edward A. |last2=Williamson |first2=S. Gill |date=2010 |title=Lists, Decisions and Graphs. With an Introduction to Probability |url=https://books.google.com/books?id=vaXv_yhefG8C }}
* {{cite book |last=Berge |first=Claude |date=1958 |title=Théorie des graphes et ses applications |language=fr |location=Paris |publisher=Dunod }}
* {{cite book |last=Biggs |first=Norman |date=1993 |title=Algebraic Graph Theory |edition=2nd |publisher=Cambridge University Press |isbn=978-0-521-45897-9 }}
* {{cite book |last=Bollobás |first=Béla |date=2002 |title=Modern Graph Theory |edition=1st |publisher=Springer |isbn=978-0-387-98488-9 }}
* {{cite book |last=Diestel |first=Reinhard |date=2005 |title=Graph Theory |url=http://diestel-graph-theory.com/GrTh.html |edition=3rd |location=Berlin, New York |publisher=Springer-Verlag |isbn=978-3-540-26183-4 }}
* {{cite book |last1=Graham |first1=R.L. |last2=Grötschel |first2=M. |last3=Lovász |first3=L. |date=1995 |title=Handbook of Combinatorics |publisher=MIT Press |isbn=978-0-262-07169-7 }}
* {{cite book |last1=Gross |first1=Jonathan L. |last2=Yellen |first2=Jay |date=1998 |title=Graph Theory and Its Applications |publisher=CRC Press |isbn=978-0-8493-3982-0 }}
* {{cite book |last1=Gross |first1=Jonathan L. |last2=Yellen |first2=Jay |date=2003 |title=Handbook of Graph Theory |publisher=CRC |isbn=978-1-58488-090-5 }}
* {{cite book |last=Harary |first=Frank |date=1995 |title=Graph Theory |publisher=Addison Wesley Publishing Company |isbn=978-0-201-41033-4 }}
* {{cite book |last1=Iyanaga |first1=Shôkichi |last2=Kawada |first2=Yukiyosi |date=1977 |title=Encyclopedic Dictionary of Mathematics |url=https://archive.org/details/encyclopedicdict0000niho |publisher=MIT Press |isbn=978-0-262-09016-2 |url-access=registration }}
* {{cite book |last=Zwillinger |first=Daniel |date=2002 |title=CRC Standard Mathematical Tables and Formulae |edition=31st |publisher=Chapman & Hall/CRC |isbn=978-1-58488-291-6 }}


== अग्रिम पठन ==
* {{cite book|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory|year=1993|publisher=[[Dover Publications]]|location=New York|isbn=978-0-486-67870-2|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|access-date=8 August 2012}}
















== बाहरी संबंध ==
{{Library resources box
|by=no
|onlinebooks=no
|others=no
|about=yes
|label=Graph(mathematics)}}
* {{Commonscatinline}}
* {{MathWorld | urlname=Graph | title = Graph}}

{{DEFAULTSORT:Graph (Discrete mathematics)}}

[[Category:Articles with hatnote templates targeting a nonexistent page|Graph (Discrete mathematics)]]
[[Category:Articles with short description|Graph (Discrete mathematics)]]
[[Category:CS1 errors|Graph (Discrete mathematics)]]
[[Category:CS1 français-language sources (fr)|Graph (Discrete mathematics)]]
[[Category:CS1 maint|Graph (Discrete mathematics)]]
[[Category:CS1 Ελληνικά-language sources (el)|Graph (Discrete mathematics)]]
[[Category:Citation Style 1 templates|W]]
[[Category:Collapse templates|Graph (Discrete mathematics)]]
[[Category:Commons category link is the pagename|Graph (Discrete mathematics)]]
[[Category:Created On 27/11/2022|Graph (Discrete mathematics)]]
[[Category:Machine Translated Page|Graph (Discrete mathematics)]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|Graph (Discrete mathematics)]]
[[Category:Pages with script errors|Graph (Discrete mathematics)]]
[[Category:Short description with empty Wikidata description|Graph (Discrete mathematics)]]
[[Category:Sidebars with styles needing conversion|Graph (Discrete mathematics)]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates based on the Citation/CS1 Lua module|Graph (Discrete mathematics)]]
[[Category:Templates generating COinS|Cite web]]
[[Category:Templates generating microformats|Graph (Discrete mathematics)]]
[[Category:Templates that are not mobile friendly|Graph (Discrete mathematics)]]
[[Category:Templates used by AutoWikiBrowser|Cite web]]
[[Category:Templates using TemplateData|Graph (Discrete mathematics)]]
[[Category:Wikipedia fully protected templates|Cite web]]
[[Category:Wikipedia metatemplates|Graph (Discrete mathematics)]]
[[Category:ग्राफ सिद्धांत|Graph (Discrete mathematics)]]