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

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

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

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

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

परिभाषाएँ

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

ग्राफ

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

एक ग्राफ़ (कभी-कभी इसे निर्देशित ग्राफ़ से अलग करने के लिए एक अप्रत्यक्ष ग्राफ़ कहा जाता है, या इसे एक मल्टीग्राफ़ से अलग करने के लिए एक साधारण ग्राफ़ कहा जाता है)^[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$ ) आसन्न आव्यूह होगा.

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

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

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

एक प्रतिबंधित लेकिन शब्द के बहुत सामान्य अर्थ में,^[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$ ऊपर के रूप में परिभाषित किया गया है। निर्देशित और अप्रत्यक्ष रेखांकन विशेष स्थिति हैं।

भारित ग्राफ

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

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

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

ग्राफ संचालन

ऐसे कई ऑपरेशन हैं जो प्रारंभिक से नए ग्राफ़ बनाते हैं, जिन्हें निम्नलिखित श्रेणियों में वर्गीकृत किया जा सकता है:

एकात्मक संचालन, जो प्रारंभिक एक से एक नया ग्राफ बनाते हैं, जैसे:
- किनारा संकुचन,
- पंक्ति ग्राफ,
- दोहरा ग्राफ,
- पूरक ग्राफ,
- ग्राफ पुनर्लेखन;
द्विआधारी संचालन, जो दो प्रारंभिक लोगों से एक नया ग्राफ बनाते हैं, जैसे:
- रेखांकन का संघ अलग करना,
- रेखांकन का कार्तीय उत्पाद,
- रेखांकन का प्रदिश उत्पाद,
- रेखांकन का मजबूत उत्पाद,
- रेखांकन का शब्दकोष उत्पाद,
- श्रृंखला-समानांतर रेखांकन।

सामान्यीकरण

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

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

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

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

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

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

यह भी देखें

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

↑ ^1.0 ^1.1 Trudeau, Richard J. (1993). ग्राफ थ्योरी का परिचय (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 19. ISBN 978-0-486-67870-2. Retrieved 8 August 2012. ग्राफ़ एक ऑब्जेक्ट होता है जिसमें दो सेट होते हैं जिन्हें इसका वर्टेक्स सेट और इसका एज सेट कहा जाता है। {{cite book}}: zero width space character in |quote= at position 94 (help)
↑
See:
- J. J. Sylvester (February 7, 1878) "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) "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.
↑ Gross, Jonathan L.; Yellen, Jay (2004). ग्राफ सिद्धांत की पुस्तिका. CRC Press. p. 35. ISBN 978-1-58488-090-5.
↑ Bender & Williamson 2010, p. 148.
↑ See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
↑ Bender & Williamson 2010, p. 149.
↑ Graham et al., p. 5.
↑ ^8.0 ^8.1 Bender & Williamson 2010, p. 161.
↑ Strang, Gilbert (2005), Linear Algebra and Its Applications (4th ed.), Brooks Cole, ISBN 978-0-03-010567-8
↑ Lewis, John (2013), Java Software Structures (4th ed.), Pearson, p. 405, ISBN 978-0133250121
↑ Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). असतत गणित की नींव (International student ed.). Boston: PWS-KENT Pub. Co. p. 463. ISBN 978-0-53492-373-0. एक वेटेड ग्राफ़ एक ग्राफ़ है जिसमें एक संख्या w(e), जिसे उसका वेट कहा जाता है, प्रत्येक किनारे e को निर्दिष्ट किया जाता है।</ रेफरी> इस तरह के वजन हाथ में समस्या के आधार पर उदाहरण के लिए लागत, लंबाई या क्षमता का प्रतिनिधित्व कर सकते हैं। इस तरह के ग्राफ़ कई संदर्भों में उत्पन्न होते हैं, उदाहरण के लिए सबसे छोटी पथ समस्याओं जैसे ट्रैवलिंग सेल्समैन की समस्या।
रेखांकन के प्रकार

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

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

नियमित ग्राफ

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

पूरा ग्राफ

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

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

जुड़ा हुआ ग्राफ

एक अप्रत्यक्ष ग्राफ़ में, वर्टिकल का एक अनियंत्रित युग्म {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 में सूचीबद्ध किया जा सकता है1, में2, …, मेंn ऐसे कि किनारे हैं {vi, vi+1} जहां i = 1, 2, ..., n - 1. पथ ग्राफ़ को कनेक्टेड ग्राफ़ के रूप में वर्णित किया जा सकता है जिसमें दो शीर्षों को छोड़कर सभी की डिग्री 2 है और दो शेष शीर्षों की डिग्री 1 है। यदि पथ ग्राफ़ के रूप में होता है ग्राफ थ्योरी की शब्दावली # दूसरे ग्राफ के सबग्राफ, यह उस ग्राफ में एक पाथ (ग्राफ थ्योरी) है।

प्लानर ग्राफ

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

चक्र ग्राफ

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

पेड़

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

पॉलीट्री

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

उन्नत कक्षाएं

अधिक उन्नत प्रकार के रेखांकन हैं:

पीटरसन ग्राफ और इसके सामान्यीकरण;

सही रेखांकन;

कोग्राफ;

कॉर्डल रेखांकन;

बड़े ग्राफ ऑटोमोर्फिज्म के साथ अन्य ग्राफ़: वर्टेक्स-सकर्मक ग्राफ|वर्टेक्स-ट्रांसिटिव, चाप-सकर्मक ग्राफ|आर्क-ट्रांसिटिव, और दूरी-सकर्मक ग्राफ;

दृढ़ता से नियमित रेखांकन और उनके सामान्यीकरण दूरी-नियमित रेखांकन।

रेखांकन के गुण

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

उदाहरण

छह शीर्षों और सात किनारों वाला एक ग्राफ
* आरेख शीर्षों के साथ ग्राफ का एक योजनाबद्ध प्रतिनिधित्व है V={1,2,3,4,5,6}{\displaystyle V=\{1,2,3,4,5,6\}} और किनारों E={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}.{\displaystyle E=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}.}
कंप्यूटर विज्ञान में, निर्देशित रेखांकन का उपयोग ज्ञान (जैसे, वैचारिक ग्राफ), परिमित राज्य मशीनों और कई अन्य असतत संरचनाओं का प्रतिनिधित्व करने के लिए किया जाता है।

एक सेट एक्स पर एक बाइनरी रिलेशन आर एक निर्देशित ग्राफ को परिभाषित करता है। X का एक तत्व x, X के एक तत्व y का प्रत्यक्ष पूर्ववर्ती है यदि और केवल यदि xRy।

एक निर्देशित ग्राफ ट्विटर जैसे सूचना नेटवर्क को मॉडल कर सकता है, जिसमें एक उपयोगकर्ता दूसरे का अनुसरण करता है।<ref name="snatwitter">Grandjean, Martin (2016). "ट्विटर का एक सोशल नेटवर्क विश्लेषण: डिजिटल मानविकी समुदाय का मानचित्रण". Cogent Arts & Humanities. 3 (1): 1171458. doi:10.1080/23311983.2016.1171458.
↑ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web. doi:10.1145/2488388.2488433.

संदर्भ

Balakrishnan, V. K. (1997). Graph Theory (1st ed.). McGraw-Hill. ISBN 978-0-07-005489-9.
Bang-Jensen, J.; Gutin, G. (2000). Digraphs: Theory, Algorithms and Applications. Springer.
Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability.
Berge, Claude (1958). Théorie des graphes et ses applications (in français). Paris: Dunod.
Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge University Press. ISBN 978-0-521-45897-9.
Bollobás, Béla (2002). Modern Graph Theory (1st ed.). Springer. ISBN 978-0-387-98488-9.
Diestel, Reinhard (2005). Graph Theory (3rd ed.). Berlin, New York: Springer-Verlag. ISBN 978-3-540-26183-4.
Graham, R.L.; Grötschel, M.; Lovász, L. (1995). Handbook of Combinatorics. MIT Press. ISBN 978-0-262-07169-7.
Gross, Jonathan L.; Yellen, Jay (1998). Graph Theory and Its Applications. CRC Press. ISBN 978-0-8493-3982-0.
Gross, Jonathan L.; Yellen, Jay (2003). Handbook of Graph Theory. CRC. ISBN 978-1-58488-090-5.
Harary, Frank (1995). Graph Theory. Addison Wesley Publishing Company. ISBN 978-0-201-41033-4.
Iyanaga, Shôkichi; Kawada, Yukiyosi (1977). Encyclopedic Dictionary of Mathematics. MIT Press. ISBN 978-0-262-09016-2.
Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulae (31st ed.). Chapman & Hall/CRC. ISBN 978-1-58488-291-6.

अग्रिम पठन

Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Publications. ISBN 978-0-486-67870-2. Retrieved 8 August 2012.

इस पेज में लापता आंतरिक लिंक की सूची

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

बाहरी संबंध

Media related to ग्राफ (असतत गणित) at Wikimedia Commons
Weisstein, Eric W. "Graph". MathWorld.

[:0-1] 1.0 ^1.1 Trudeau, Richard J. (1993). ग्राफ थ्योरी का परिचय (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 19. ISBN 978-0-486-67870-2. Retrieved 8 August 2012. ग्राफ़ एक ऑब्जेक्ट होता है जिसमें दो सेट होते हैं जिन्हें इसका वर्टेक्स सेट और इसका एज सेट कहा जाता है। {{cite book}}: zero width space character in |quote= at position 94 (help)

[2] See:
J. J. Sylvester (February 7, 1878) "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) "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.

[3] J. J. Sylvester (February 7, 1878) "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."

[4] J. J. Sylvester (1878) "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.

[3] Gross, Jonathan L.; Yellen, Jay (2004). ग्राफ सिद्धांत की पुस्तिका. CRC Press. p. 35. ISBN 978-1-58488-090-5.

[FOOTNOTEBenderWilliamson2010148-4] Bender & Williamson 2010, p. 148.

[5] See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.

[FOOTNOTEBenderWilliamson2010149-6] Bender & Williamson 2010, p. 149.

[7] Graham et al., p. 5.

[FOOTNOTEBenderWilliamson2010161-8] 8.0 ^8.1 Bender & Williamson 2010, p. 161.

[9] Strang, Gilbert (2005), Linear Algebra and Its Applications (4th ed.), Brooks Cole, ISBN 978-0-03-010567-8

[10] Lewis, John (2013), Java Software Structures (4th ed.), Pearson, p. 405, ISBN 978-0133250121

[11] Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). असतत गणित की नींव (International student ed.). Boston: PWS-KENT Pub. Co. p. 463. ISBN 978-0-53492-373-0. एक वेटेड ग्राफ़ एक ग्राफ़ है जिसमें एक संख्या w(e), जिसे उसका वेट कहा जाता है, प्रत्येक किनारे e को निर्दिष्ट किया जाता है।</ रेफरी> इस तरह के वजन हाथ में समस्या के आधार पर उदाहरण के लिए लागत, लंबाई या क्षमता का प्रतिनिधित्व कर सकते हैं। इस तरह के ग्राफ़ कई संदर्भों में उत्पन्न होते हैं, उदाहरण के लिए सबसे छोटी पथ समस्याओं जैसे ट्रैवलिंग सेल्समैन की समस्या।
रेखांकन के प्रकार

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

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

नियमित ग्राफ

Main article: Regular graph

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

पूरा ग्राफ

Main article: Complete graph

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

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

जुड़ा हुआ ग्राफ

Main article: Connectivity (graph theory)

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

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

Main article: Bipartite graph

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

पथ ग्राफ

Main article: Path graph

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

प्लानर ग्राफ

Main article: Planar graph

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

चक्र ग्राफ

Main article: Cycle graph

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

पेड़

Main article: Tree (graph theory)

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

पॉलीट्री

Main article: Polytree

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

उन्नत कक्षाएं

अधिक उन्नत प्रकार के रेखांकन हैं:

पीटरसन ग्राफ और इसके सामान्यीकरण;

सही रेखांकन;

कोग्राफ;

कॉर्डल रेखांकन;

बड़े ग्राफ ऑटोमोर्फिज्म के साथ अन्य ग्राफ़: वर्टेक्स-सकर्मक ग्राफ|वर्टेक्स-ट्रांसिटिव, चाप-सकर्मक ग्राफ|आर्क-ट्रांसिटिव, और दूरी-सकर्मक ग्राफ;

दृढ़ता से नियमित रेखांकन और उनके सामान्यीकरण दूरी-नियमित रेखांकन।

रेखांकन के गुण

See also: Glossary of graph theory and Graph property

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

उदाहरण

छह शीर्षों और सात किनारों वाला एक ग्राफ
* आरेख शीर्षों के साथ ग्राफ का एक योजनाबद्ध प्रतिनिधित्व है $V=\{1,2,3,4,5,6\}$ और किनारों $E=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}.$
कंप्यूटर विज्ञान में, निर्देशित रेखांकन का उपयोग ज्ञान (जैसे, वैचारिक ग्राफ), परिमित राज्य मशीनों और कई अन्य असतत संरचनाओं का प्रतिनिधित्व करने के लिए किया जाता है।

एक सेट एक्स पर एक बाइनरी रिलेशन आर एक निर्देशित ग्राफ को परिभाषित करता है। X का एक तत्व x, X के एक तत्व y का प्रत्यक्ष पूर्ववर्ती है यदि और केवल यदि xRy।

एक निर्देशित ग्राफ ट्विटर जैसे सूचना नेटवर्क को मॉडल कर सकता है, जिसमें एक उपयोगकर्ता दूसरे का अनुसरण करता है।<ref name="snatwitter">Grandjean, Martin (2016). "ट्विटर का एक सोशल नेटवर्क विश्लेषण: डिजिटल मानविकी समुदाय का मानचित्रण". Cogent Arts & Humanities. 3 (1): 1171458. doi:10.1080/23311983.2016.1171458.

[14] पीटरसन ग्राफ और इसके सामान्यीकरण;

[15] सही रेखांकन;

[16] कोग्राफ;

[17] कॉर्डल रेखांकन;

[18] बड़े ग्राफ ऑटोमोर्फिज्म के साथ अन्य ग्राफ़: वर्टेक्स-सकर्मक ग्राफ|वर्टेक्स-ट्रांसिटिव, चाप-सकर्मक ग्राफ|आर्क-ट्रांसिटिव, और दूरी-सकर्मक ग्राफ;

[19] दृढ़ता से नियमित रेखांकन और उनके सामान्यीकरण दूरी-नियमित रेखांकन।

[20] कंप्यूटर विज्ञान में, निर्देशित रेखांकन का उपयोग ज्ञान (जैसे, वैचारिक ग्राफ), परिमित राज्य मशीनों और कई अन्य असतत संरचनाओं का प्रतिनिधित्व करने के लिए किया जाता है।

[21] एक सेट एक्स पर एक बाइनरी रिलेशन आर एक निर्देशित ग्राफ को परिभाषित करता है। X का एक तत्व x, X के एक तत्व y का प्रत्यक्ष पूर्ववर्ती है यदि और केवल यदि xRy।

[22] एक निर्देशित ग्राफ ट्विटर जैसे सूचना नेटवर्क को मॉडल कर सकता है, जिसमें एक उपयोगकर्ता दूसरे का अनुसरण करता है।<ref name="snatwitter">Grandjean, Martin (2016). "ट्विटर का एक सोशल नेटवर्क विश्लेषण: डिजिटल मानविकी समुदाय का मानचित्रण". Cogent Arts & Humanities. 3 (1): 1171458. doi:10.1080/23311983.2016.1171458.

[twitterwtf-12] Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web. doi:10.1145/2488388.2488433.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Anonymous

Search

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

Namespaces

More

Page actions

Contents

परिभाषाएँ

ग्राफ

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

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

भारित ग्राफ

ग्राफ संचालन

सामान्यीकरण

यह भी देखें

टिप्पणियाँ

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

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

नियमित ग्राफ

पूरा ग्राफ

परिमित ग्राफ

जुड़ा हुआ ग्राफ

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

पथ ग्राफ

प्लानर ग्राफ

चक्र ग्राफ

पेड़

पॉलीट्री

उन्नत कक्षाएं

रेखांकन के गुण

उदाहरण

संदर्भ

अग्रिम पठन

इस पेज में लापता आंतरिक लिंक की सूची

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

परिभाषाएँ

ग्राफ

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

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

भारित ग्राफ

ग्राफ संचालन

सामान्यीकरण

यह भी देखें

टिप्पणियाँ

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

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

नियमित ग्राफ

पूरा ग्राफ

परिमित ग्राफ

जुड़ा हुआ ग्राफ

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

पथ ग्राफ

प्लानर ग्राफ

चक्र ग्राफ

पेड़

पॉलीट्री

उन्नत कक्षाएं

रेखांकन के गुण

उदाहरण

संदर्भ

अग्रिम पठन

इस पेज में लापता आंतरिक लिंक की सूची

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories