ग्राफ सिद्धांत

This article is about किनारों से जुड़े शीर्षों का समूह. For गणितीय कार्यों के ग्राफ़, see किसी फलन का ग्राफ़. For अन्य उपयोग, see ग्राफ़ (बहुविकल्पी).

ग्राफ का ग्राफ आरेखण।

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

परिभाषाएँ

Further information: ग्राफ़ सिद्धांत की शब्दावली

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

ग्राफ

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

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

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

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

किनारे $\{x,y\}$ में , शिखर $x$ तथा $y$ को किनारे का अंतिम बिंदु कहा जाता है। कहा जाता है कि किनारा $x$ तथा $y$ को जोड़ता है और $x$ और $y$ पर आपतित होता है $y$ शीर्ष ग्राफ़ में मौजूद हो सकता है और किनारे से संबंधित नहीं हो सकता है। ऊपर दी गई परिभाषा के अनुसार ाधिक किनारों की अनुमति नहीं है, दो या दो से अधिक किनारे हैं जो ही दो शीर्षों में सम्मिलित होते हैं।

अनेक किनारों की अनुमति देने वाले शब्द के और सामान्य अर्थ में, ग्राफ आदेशित ट्रिपल $G=(V,E,\phi )$ है जिसमे

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

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

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

$V$ तथा $E$ सामान्यतः सीमित होने के लिए लिया जाता है, और अनंत ग्राफ के लिए अनेक प्रसिद्ध परिणाम सत्य नहीं हैं (या बल्कि भिन्न हैं) क्योंकि अनेक तर्क अनंत ग्राफ़ में विफल होते हैं। इसके अतिरिक्त, $V$ अधिकांशतः खाली नहीं माना जाता है, किन्तु $E$ खालीसमुच्चय होने की अनुमति है। ग्राफ का क्रम है $|V|$, इसके शीर्षों की संख्या। ग्राफ का आकार $|E|$ है , इसके किनारों की संख्या। किसी शीर्ष की डिग्री या संयोजकता उस पर आपतित किनारों की संख्या है, जहां लूप को दो बार गिना जाता है। किसी ग्राफ़ की डिग्री उसके शीर्षों की अधिकतम डिग्री होती है।

'n' क्रम के अप्रत्यक्ष सरल ग्राफ में, प्रत्येक शीर्ष की अधिकतम डिग्री n − 1 है और ग्राफ का अधिकतम आकार n(n − 1)/2 है .

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

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

Main article: निर्देशित ग्राफ

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

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

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

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

अस्पष्टता से बचने के लिए, इस प्रकार की वस्तु को सटीक रूप से निर्देशित सरल ग्राफ़ कहा जा सकता है। समुच्चय सिद्धांत और ग्राफ सिद्धांत में, ${\displaystyle V^{n}}$ V के तत्वों के n-टुपल्स के समुच्चय को दर्शाता है, अर्थात, n तत्वों के क्रमबद्ध अनुक्रम जो आवश्यक रूप से भिन्न नहीं हैं।

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

अनेक किनारों की अनुमति देने वाले शब्द के और सामान्य अर्थ में, निर्देशित ग्राफ $G=(V,E,\phi )$ आदेशित ट्रिपल है जिसमे

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

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

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

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

अनुप्रयोग

2013 की गर्मियों में महीने के समय विकिपीडिया संपादकों (किनारे) द्वारा विभिन्न विकिपीडिया भाषा संस्करणों (कोने) में योगदान करके बनाया गया नेटवर्क ग्राफ।

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

कंप्यूटर विज्ञान

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

भाषाविज्ञान

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

भौतिकी और रसायन विज्ञान

रसायन विज्ञान और भौतिकी में अणुओं का अध्ययन करने के लिए ग्राफ सिद्धांत का भी उपयोग किया जाता है। संघनित पदार्थ भौतिकी में, परमाणुओं की टोपोलॉजी से संबंधित ग्राफ-सैद्धांतिक गुणों पर आंकड़े त्र करके समष्टि सिम्युलेटेड परमाणु संरचनाओं की त्रि-आयामी संरचना का मात्रात्मक अध्ययन किया जा सकता है। इसके अतिरिक्त, फेनमैन आरेख क्वांटम क्षेत्र सिद्धांत को ऐसे रूप में सारांशित करता है जिसे प्रयोगात्मक संख्याओं के साथ निकट संपर्क में समझना है। रसायन विज्ञान में ग्राफ अणु के लिए प्राकृतिक मॉडल बनाता है, जहां शिखर परमाणुओं और किनारों को रासायनिक बंधनों का प्रतिनिधित्व करते हैं। यह दृष्टिकोण विशेष रूप से आणविक संरचनाओं के कंप्यूटर प्रसंस्करण में उपयोग किया जाता है, अणु संपादक से डेटाबेस खोज तक। सांख्यिकीय भौतिकी में, रेखांकन प्रणाली के अंतःक्रियात्मक भागों के साथ-साथ इस तरह की भौतिक प्रक्रिया की गतिशीलता के मध्यस्थानीय कनेक्शन का प्रतिनिधित्व कर सकता है। प्रणाली में इसी तरह, कम्प्यूटेशनल तंत्रिका विज्ञान ग्राफ़ में मस्तिष्क क्षेत्रों के मध्य कार्यात्मक कनेक्शन का प्रतिनिधित्व करने के लिए उपयोग किया जा सकता है जो विभिन्न संज्ञानात्मक प्रक्रियाओं को जन्म देने के लिए बातचीत करते हैं, जहां शिखर मस्तिष्क के विभिन्न क्षेत्रों का प्रतिनिधित्व करते हैं और किनारे उन क्षेत्रों के मध्य कनेक्शन का प्रतिनिधित्व करते हैं। ग्राफ़ सिद्धांत विद्युत नेटवर्क के विद्युत मॉडलिंग में महत्वपूर्ण भूमिका निभाता है, यहाँ, नेटवर्क संरचनाओं के विद्युत गुणों को प्राप्त करने के लिए भार तार खंडों के प्रतिरोध से जुड़े होते हैं। झरझरा माध्यम के सूक्ष्म पैमाने के चैनलों का प्रतिनिधित्व करने के लिए ग्राफ़ का भी उपयोग किया जाता है, जिसमें कोने छिद्रों का प्रतिनिधित्व करते हैं और किनारे छिद्रों को जोड़ने वाले छोटे चैनलों का प्रतिनिधित्व करते हैं। रासायनिक ग्राफ सिद्धांत आणविक ग्राफ का उपयोग मॉडल अणुओं के साधन के रूप में करता है। चरण संक्रमण और महत्वपूर्ण घटनाओं का अध्ययन करने और समझने के लिए ग्राफ और नेटवर्क उत्कृष्ट मॉडल हैं। नोड्स या किनारों को हटाने से महत्वपूर्ण संक्रमण होता है जहां नेटवर्क छोटे समूहों में टूट जाता है जिसका चरण संक्रमण के रूप में अध्ययन किया जाता है। इस टूटने का अध्ययन परकोलेशन सिद्धांत के माध्यम से किया जाता है।

सामाजिक विज्ञान

समाजशास्त्र में ग्राफ थ्योरी: जैकब एल. मोरेनो सोशियोग्राम (1953)।

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

जीव विज्ञान

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

समष्टि संबंधों के साथ डेटासेट का मॉडल और विश्लेषण करने के लिए ग्राफ़ का सामान्यतः आणविक जीव विज्ञान और जीनोमिक्स में भी उपयोग किया जाता है। उदाहरण के लिए, ग्राफ़-आधारित पद्धतियों का उपयोग अधिकांशतः ल-कोशिका_विश्लेषण ट्रांस्क्रिप्टोमिक्स| ल-कोशिका ट्रांस्क्रिप्टोम विश्लेषण में सेल-प्रकारों में साथ 'क्लस्टर' कोशिकाओं के लिए किया जाता है। अन्य उपयोग जैविक मार्ग में जीन या प्रोटीन को मॉडल करना और उनके मध्यसंबंधों का अध्ययन करना है, जैसे कि चयापचय मार्ग और जीन नियामक नेटवर्क। विकासवादी ट्री, पारिस्थितिक नेटवर्क और जीन अभिव्यक्ति पैटर्न के पदानुक्रमित क्लस्टरिंग को भी ग्राफ संरचनाओं के रूप में दर्शाया गया है।

ग्राफ सिद्धांत का उपयोग कनेक्टोमिक्स में भी किया जाता है; तंत्रिका तंत्र को ग्राफ के रूप में देखा जा सकता है, जहां नोड्स न्यूरॉन्स हैं और किनारे उनके मध्यके कनेक्शन हैं।

गणित

गणित में, रेखांकन ज्यामिति और टोपोलॉजी के कुछ हिस्सों जैसे गाँठ सिद्धांत में उपयोगी होते हैं। बीजगणितीय ग्राफ सिद्धांत का समूह सिद्धांत के साथ घनिष्ठ संबंध है। बीजगणितीय ग्राफ सिद्धांत को गतिशील प्रणालियों और समष्टिता सहित अनेक क्षेत्रों में प्रयुक्त किया गया है।

अन्य विषय

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

इतिहास

कोनिग्सबर्ग ब्रिज की समस्या

लियोनहार्ड यूलर द्वारा कोनिग्सबर्ग के सात पुलों पर लिखा गया और 1736 में प्रकाशित पेपर को ग्राफ सिद्धांत के इतिहास में पहला पेपर माना जाता है। यह पेपर, साथ ही नाइट के दौरे पर एलेक्जेंडर-थियोफाइल वेंडरमोंड द्वारा लिखित, गॉटफ्रीड विल्हेम लीबनिज द्वारा प्रारंभ किए गए विश्लेषण साइटस के साथ आगे बढ़ा। ऑगस्टिन-लुई कॉची द्वारा उत्तल बहुफलक के किनारों, शीर्षों और चेहरों की संख्या से संबंधित यूलर के सूत्र का अध्ययन और सामान्यीकरण किया गया था। और साइमन एंटोनी जीन ल'हुइलियर|ल'हुइलियर, और टोपोलॉजी के रूप में ज्ञात गणित की शाखा की शुरुआत का प्रतिनिधित्व करता है।

कोनिग्सबर्ग के पुलों पर यूलर के पेपर के सदी से भी अधिक समय के पश्चात् और जब जोहान बेनेडिक्ट लिस्टिंग टोपोलॉजी की अवधारणा को प्रस्तुत कर रहा था, आर्थर केली का नेतृत्व अंतर कलन से उत्पन्न होने वाले विशेष विश्लेषणात्मक रूपों में विशेष वर्ग के ग्राफ, ट्री (ट्री) का अध्ययन करने के लिए किया गया था। ग्राफ सिद्धांत) एस। इस अध्ययन के सैद्धांतिक रसायन शास्त्र के लिए अनेक निहितार्थ थे। उन्होंने जिन विधियों का उपयोग किया, वह मुख्य रूप से विशेष गुणों वाले ग्राफ़ की गणना से संबंधित थीं। गणनात्मक ग्राफ सिद्धांत तब केली के परिणामों और 1935 और 1937 के मध्यजॉर्ज पोल्या | पोल्या द्वारा प्रकाशित मौलिक परिणामों से उत्पन्न हुआ। इन्हें 1959 में निकोलस गवर्नमेंट डी ब्रुजन द्वारा सामान्यीकृत किया गया था। केली ने रासायनिक संरचना के समकालीन अध्ययनों के साथ ट्रीों पर अपने परिणामों को जोड़ा। गणित के विचारों का रसायन विज्ञान के साथ विलय प्रारंभ हुआ जो ग्राफ सिद्धांत की मानक शब्दावली का हिस्सा बन गया है।

विशेष रूप से, शब्द ग्राफ जेम्स जोसेफ सिल्वेस्टर द्वारा 1878 में प्रकृति (पत्रिका) में प्रकाशित पेपर में प्रस्तुत किया गया था, जहां वह क्वांटिक इनवेरिएंट्स और बीजगणित और आणविक आरेखों के सह-वेरिएंट के मध्य सादृश्य बनाता है:

[…] प्रत्येक अपरिवर्तनीय और सह-परिवर्त इस प्रकार अगस्त केकुले|केकुलियन आरेख या केमिकोग्राफ के समान ग्राफ द्वारा व्यक्त किया जा सकता है। [...] मैं रेखांकन के ज्यामितीय गुणन के लिए नियम देता हूं, अर्थात इन-या सह-संस्करणों के उत्पाद के लिए ग्राफ बनाने के लिए जिनके भिन्न-भिन्न ग्राफ दिए गए हैं। […] (इटैलिक मूल रूप में)।

ग्राफ सिद्धांत पर पहली पाठ्यपुस्तक डेन्स कोनिग द्वारा लिखी गई थी, और 1936 में प्रकाशित हुई थी। 1969 में प्रकाशित फ्रैंक हैरिस की अन्य पुस्तक को विश्वभर में इस विषय पर निश्चित पाठ्यपुस्तक माना गया, और गणितज्ञों, रसायनज्ञों, इलेक्ट्रिकल इंजीनियरों और सामाजिक वैज्ञानिकों को दूसरे से बात करने में सक्षम बनाया। हैरी ने जॉर्ज पोल्या पुरस्कार|पोल्या पुरस्कार के लिए सभी रॉयल्टी दान कर दी। ग्राफ सिद्धांत में सबसे प्रसिद्ध और उत्तेजक समस्याओं में से चार रंग की समस्या है: क्या यह सच है कि समतल में खींचे गए किसी भी नक्शे में उसके क्षेत्रों को चार रंगों से रंगा जा सकता है, इस तरह से कि किन्हीं दो क्षेत्रों की आम सीमा भिन्न-भिन्न होती है रंग की? यह समस्या पहली बार 1852 में फ्रांसिस गुथरी द्वारा प्रस्तुत की गई थी और इसका पहला लिखित रिकॉर्ड उसी वर्ष विलियम रोवन हैमिल्टन को संबोधित ऑगस्टस डी मॉर्गन के पत्र में है। अनेक गलत प्रमाण प्रस्तावित किए गए हैं, जिनमें केली, अल्फ्रेड केम्पे और अन्य सम्मिलित हैं। पीटर टैट (भौतिक विज्ञानी), पर्सी जॉन हेवुड, फ्रैंक पी. रैमसे और ह्यूगो हैडविगर द्वारा इस समस्या के अध्ययन और सामान्यीकरण ने इच्छानुसार जीनस (गणित) के साथ सतहों पर एम्बेडेड ग्राफ के रंगों के अध्ययन का नेतृत्व किया। टैट के पुनर्रचना ने समस्याओं का नया वर्ग उत्पन्न किया, गुणनखंडन समस्याएँ, विशेष रूप से जूलियस पीटरसन और डेन्स कोनिग|कोनिग द्वारा अध्ययन किया गया। रंगों पर राम्से के कार्य और विशेष रूप से 1941 में पाल तुरान द्वारा प्राप्त किए गए परिणाम ग्राफ सिद्धांत की और शाखा, चरम ग्राफ सिद्धांत के मूल में थे।

चार रंगों की समस्या सदी से भी अधिक समय तक अनसुलझी रही। 1969 में हेनरिक हेश ने कंप्यूटर का उपयोग करके समस्या को हल करने के लिए विधि प्रकाशित की। केनेथ एपल और वोल्फगैंग हेकेन द्वारा 1976 में निर्मित कंप्यूटर एडेड प्रूफ हेश द्वारा विकसित निर्वहन की धारणा का मौलिक उपयोग करता है। प्रमाण में कंप्यूटर द्वारा 1,936 विन्यासों के गुणों की जाँच करना सम्मिलित था, और इसकी समष्टिता के कारण उस समय इसे पूरी तरह से स्वीकार नहीं किया गया था। बीस साल पश्चात् नील रॉबर्टसन (गणितज्ञ), पॉल सेमोर (गणितज्ञ), डैनियल पी. सैंडर्स और रॉबिन थॉमस (गणितज्ञ) द्वारा केवल 633 विन्यासों पर विचार करने वाला सरल प्रमाण दिया गया था। 1860 और 1930 से टोपोलॉजी के स्वायत्त विकास ने केमिली जॉर्डन, काज़िमिर्ज़ कुराटोव्स्की और हस्लर व्हिटनी के कार्यों के माध्यम से निषेचित ग्राफ सिद्धांत को वापस लाया। ग्राफ सिद्धांत और टोपोलॉजी के सामान्य विकास का अन्य महत्वपूर्ण कारक आधुनिक बीजगणित की विधिों के उपयोग से आया है। इस तरह के उपयोग का पहला उदाहरण भौतिक विज्ञानी गुस्ताव किरचॉफ के काम से आता है, जिन्होंने 1845 में विद्युत परिपथ में वोल्टेज और विद्युत प्रवाह की गणना के लिए किरचॉफ के परिपथ कानूनों को प्रकाशित किया था।

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

प्रतिनिधित्व

ग्राफ सम्बन्ध का सार है जो कि प्रकृति में उभरता है; इसलिए, इसे निश्चित प्रतिनिधित्व के साथ नहीं जोड़ा जा सकता है। जिस तरह से इसका प्रतिनिधित्व किया जाता है, वह सुविधा की डिग्री पर निर्भर करता है, ऐसा प्रतिनिधित्व जो निश्चित अनुप्रयोग के लिए प्रदान करता है। सबसे सामान्य प्रतिनिधित्व दृश्य होता हैं, जिसमें, सामान्यतः, कोने खींचे जाते हैं और किनारों से जुड़े होते हैं, तथा सारणीबद्ध, जिसमें तालिका की पंक्तियाँ ग्राफ़ के अंदर कोने के मध्य संबंधों के बारे में जानकारी प्रदान करती हैं।

विजुअल: ग्राफ ड्राइंग

Main article: ग्राफ़ आरेखण

रेखांकन सामान्यतः प्रत्येक शीर्ष के लिए बिंदु या वृत्त खींचकर और किनारे से जुड़े होने पर दो कोने के मध्य रेखा खींचकर प्रदर्शित किया जाता है। यदि ग्राफ को निर्देशित किया जाता है, तब दिशा को तीर खींचकर संकेत दिया जाता है। यदि ग्राफ को भारित किया जाता है, तब तीर पर भार जोड़ा जाता है।

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

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

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

सर्कल पैकिंग प्रमेय, प्रतिच्छेदन ग्राफ और आसन्न आव्युह के अन्य विज़ुअलाइज़ेशन सहित कोने और किनारों से दूर ग्राफ को देखने के लिए अन्य विधिें हैं।

सारणीबद्ध: ग्राफ डेटा संरचनाएं

Main article: ग्राफ़ (सार डेटा प्रकार)

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

सूची संरचनाओं में किनारे की सूची, कोने के जोड़े की सरणी, और आसन्न सूची सम्मिलित है, जो भिन्न-भिन्न प्रत्येक शीर्ष के पड़ोसियों को सूचीबद्ध करती है: किनारे की सूची की तरह, प्रत्येक शीर्ष में सूची होती है कि यह किस कोने के निकट है।

आव्युह संरचनाओं में घटना आव्युह, 0 और 1 का आव्युह सम्मिलित है, जिनकी पंक्तियाँ कोने का प्रतिनिधित्व करती हैं और जिनके स्तंभ किनारों का प्रतिनिधित्व करते हैं, और आसन्न आव्युह, जिसमें पंक्तियों और स्तंभों दोनों को कोने से अनुक्रमित किया जाता है। दोनों ही स्थितियों में 1 दो आसन्न वस्तुओं को संकेत करता है और 0 दो गैर-आसन्न वस्तुओं को संकेत करता है। तथा डिग्री आव्युह कोने की डिग्री को संकेत करता है। लाप्लासियन आव्युह आसन्न आव्युह का संशोधित रूप है जिसमें कोने के डिग्री (ग्राफ सिद्धांत) के बारे में जानकारी सम्मिलित है, और कुछ गणनाओं में उपयोगी है जैसे कि ग्राफ के स्पन्निंग ट्री की संख्या पर किरचॉफ के प्रमेय। दूरी आव्युह, आसन्न आव्युह की तरह, इसकी पंक्तियों और स्तंभों दोनों को वर्टिकल द्वारा अनुक्रमित किया जाता है, किन्तु प्रत्येक सेल में 0 या 1 रखने के अतिरिक्त इसमें दो कोने के मध्य सबसे छोटे पथ की लंबाई होती है।

समस्याएं

गणना

ग्राफ़िकल गणन पर बड़ा साहित्य है: विशिष्ट शर्तबं को पूरा करने वाले ग्राफ़ की गिनती की समस्या। इनमें से कुछ काम हैरी और पामर (1973) में पाए जाते हैं।

सबग्राफ, प्रेरित सबग्राफ और माइनर

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

• सबसे बड़ा पूर्ण सबग्राफ ढूँढना क्लिक समस्या (एनपी-पूर्ण) कहलाता है।

सब ग्राफ समरूपता समस्या विशेष स्थितियां ग्राफ आइसोमोर्फिज्म समस्या है। यह पूछता है कि क्या दो ग्राफ आइसोमॉर्फिक हैं। यह ज्ञात नहीं है कि क्या यह समस्या एनपी-पूर्ण है, और न ही इसे बहुपद समय में हल किया जा सकता है।

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

• सबसे बड़ा एजलेस प्रेरित सबग्राफ या स्वतंत्रसमुच्चय (ग्राफ सिद्धांत) ढूँढना स्वतंत्रसमुच्चय समस्या (एनपी-पूर्ण) कहा जाता है।

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

• ग्राफ़ प्लानर ग्राफ़ है यदि इसमें नाबालिग के रूप में न तब पूरा द्विदलीय ग्राफ़ K होता है_3,3 (तीन कुटीर समस्या देखें) और न ही पूरा ग्राफ के₅.

समान समस्या, उपखंड नियंत्रण समस्या, दिए गए ग्राफ के उपखंड (ग्राफ सिद्धांत) के रूप में निश्चित ग्राफ को खोजना है। ग्राफ का उपखंड (ग्राफ सिद्धांत) या होमोमोर्फिज्म (ग्राफ सिद्धांत) कुछ (या नहीं) किनारों को उपविभाजित करके प्राप्त किया गया कोई भी ग्राफ है। उपखंड नियंत्रण ग्राफ़ गुणों से संबंधित है जैसे कि प्लानेरिटी (ग्राफ़ सिद्धांत)। उदाहरण के लिए, Kuratowski's theorem|Kuratowski's Theorem कहता है:

• ग्राफ प्लेनर ग्राफ है यदि इसमें उपखंड के रूप में न तब पूर्ण द्विदलीय ग्राफ K है_3,3 न ही पूरा ग्राफ K₅.

उपखंड रोकथाम में और समस्या केल्मन्स-सीमोर अनुमान है:

• प्रत्येक के-वर्टेक्स-कनेक्टेड ग्राफ़|5-वर्टेक्स-कनेक्टेड ग्राफ़ जो कि प्लानर ग्राफ़ नहीं है, में 5-वर्टेक्स पूर्ण ग्राफ़ के होमोमोर्फिज़्म (ग्राफ़ सिद्धांत) सम्मिलित है₅.

समस्याओं का अन्य वर्ग उस सीमा से संबंधित है जिस तक ग्राफ़ की विभिन्न प्रजातियां और सामान्यीकरण उनके बिंदु-हटाए गए उप-अनुच्छेदों द्वारा निर्धारित किए जाते हैं। उदाहरण के लिए:

• पुनर्निर्माण अनुमान

ग्राफ रंग

Main article: ग्राफ़ रंग

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

• चार रंग प्रमेय
• शक्तिशाली सही ग्राफ प्रमेय
• एर्डोस-फैबर-लोवाज़ अनुमान
• कुल रंग, जिसे मेसीमाी बेहज़ाद का अनुमान (अनसुलझा) भी कहा जाता है
• सूची बढ़त-रंग (अनसुलझा)
• हैडविगर अनुमान (ग्राफ सिद्धांत) (अनसुलझी)

सदस्यता औरीकरण

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

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

मार्ग की समस्याएं

• हैमिल्टनियन पथ समस्या
• न्यूनतम फैलाव वाला ट्री
• मार्ग निरीक्षण समस्या (जिसे चीनी डाकिया समस्या भी कहा जाता है)
• कोनिग्सबर्ग के सात पुल
• सबसे छोटा रास्ता समस्या
• स्टेनर का ट्री
• तीन-कॉटेज की समस्या
• ट्रैवलिंग सेल्समैन की समस्या (एनपी-हार्ड)

नेटवर्क प्रवाह

विशेष रूप से प्रवाह नेटवर्क की विभिन्न धारणाओं से संबंधित अनुप्रयोगों से उत्पन्न होने वाली अनेक समस्याएं हैं, उदाहरण के लिए:

• मैक्स फ्लो मिन कट प्रमेय

दृश्यता की समस्या

• संग्रहालय रक्षक समस्या

समस्याओं को कवर करना

ग्राफ़ में समस्याओं को कवर करने से वर्टिकल/सबग्राफ के उपसमुच्चय पर विभिन्न समुच्चय कवर समस्या का उल्लेख हो सकता है।

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

अपघटन की समस्या

अपघटन, ग्राफ़ के किनारे समुच्चय को विभाजित करने के रूप में परिभाषित किया गया है (विभाजन के प्रत्येक भाग के किनारों के साथ जितने आवश्यक हो उतने कोने के साथ), अनेक प्रकार के प्रश्न हैं। अधिकांशतः, समस्या यह है कि ग्राफ को निश्चित ग्राफ के उप-अनुच्छेदों में आइसोमोर्फिक में विघटित करना है; उदाहरण के लिए, हैमिल्टनियन चक्रों में पूर्ण ग्राफ को विघटित करना। अन्य समस्याएं ग्राफ़ के वर्ग को निर्दिष्ट करती हैं जिसमें दिए गए ग्राफ़ को विघटित किया जाना चाहिए, उदाहरण के लिए, चक्रों का वर्ग या पूर्ण ग्राफ़ K_n को विघटित करना में n − 1 निर्दिष्ट ट्री, क्रमशः, 1, 2, 3, ..., n − 1 किनारों।

अध्ययन की गई कुछ विशिष्ट अपघटन समस्याओं में सम्मिलित हैं:

• वृक्षारोपण, जितना संभव हो उतने जंगलों में अपघटन
• साइकिल डबल कवर, प्रत्येक किनारे को ठीक से दो बार कवर करने वाले चक्रों के संग्रह में अपघटन
• किनारे का रंग, जितना संभव हो उतना कम मिलान (ग्राफ थ्योरी) में अपघटन
• ग्राफ गुणनखंडन, दी गई डिग्री के नियमित सबग्राफ में नियमित ग्राफ का अपघटन

ग्राफ वर्ग

अनेक समस्याओं में ग्राफ़ के विभिन्न वर्गों के सदस्यों को चित्रित करना सम्मिलित है। ऐसे प्रश्नों के कुछ उदाहरण नीचे हैं:

• ग्राफ गणना वर्ग के सदस्यों
• निषिद्ध ग्राफ़ लक्षण वर्णन के संदर्भ में वर्ग की विशेषता
• वर्गों के मध्यसंबंधों का पता लगाना (उदाहरण के लिए रेखांकन की संपत्ति दूसरे को दर्शाती है)
• कक्षा में निर्णय समस्या सदस्यता के लिए कुशल एल्गोरिदम ढूँढना
• वर्ग के सदस्यों के लिए प्रतिनिधित्व (गणित) ढूँढना

यह भी देखें

• नामित रेखांकन की गैलरी
• ग्राफ सिद्धांत की शब्दावली
• ग्राफ सिद्धांत विषयों की सूची
• ग्राफ थ्योरी में अनसुलझी समस्याओं की सूची
• गणित में प्रकाशनों की सूची या ग्राफ सिद्धांत

संबंधित विषय

• बीजगणितीय ग्राफ सिद्धांत
• उद्धरण ग्राफ
• वैचारिक ग्राफ
• डेटा संरचना
• विसंधित-सेट डेटा संरचना
• दोहरे चरण का विकास
• वास्तविक ग्राफ
• अस्तित्वगत ग्राफ
• ग्राफ बीजगणित
• ग्राफ ऑटोमोर्फिज्म
• ग्राफ रंगना
• ग्राफ डेटाबेस
• ग्राफ (डेटा संरचना)
• ग्राफ ड्राइंग
• ग्राफ समीकरण
• ग्राफ पुनर्लेखन
• ग्राफ सैंडविच समस्या
• ग्राफ संपत्ति
• चौराहे का ग्राफ
• नाइट की यात्रा
• तार्किक ग्राफ
• पाश (ग्राफ सिद्धांत)
• नेटवर्क सिद्धांत
• शून्य ग्राफ
• कंकड़ गति की समस्या
• टपकन
• बिल्कुल सही ग्राफ
• क्वांटम ग्राफ
• यादृच्छिक नियमित रेखांकन
• सिमेंटिक नेटवर्क
• वर्णक्रमीय ग्राफ सिद्धांत
• मजबूत नियमित रेखांकन
• सममित रेखांकन
• सकर्मक कमी
• ट्री (डेटा संरचना)

एल्गोरिदम

• बेलमैन-फोर्ड एल्गोरिथम
• बोरव्का का एल्गोरिथम
• पहले चौड़ाई खोजो
• गहराई-पहली खोज
• दिज्क्स्ट्रा का एल्गोरिथ्म
• एडमंड्स-कार्प एल्गोरिथ्म
• फ्लोयड-वॉर्शल एल्गोरिथम
• फोर्ड-फुलकर्सन एल्गोरिथम
• होपक्रॉफ्ट-कार्प एल्गोरिथम
• हंगेरियन एल्गोरिथम
• कोसरजू का एल्गोरिदम
• क्रुस्कल का एल्गोरिदम
• निकटतम पड़ोसी एल्गोरिथ्म
• नेटवर्क सिंप्लेक्स एल्गोरिथम
• प्लानेरिटी परीक्षण # एल्गोरिदम
• प्राइम का एल्गोरिदम
• पुश-रीलेबल अधिकतम प्रवाह एल्गोरिथ्म
• टार्जन का दृढ़ता से जुड़ा हुआ घटक एल्गोरिथम
• सामयिक छँटाई

उपक्षेत्र

• बीजगणितीय ग्राफ सिद्धांत
• ज्यामितीय ग्राफ सिद्धांत
• एक्सट्रीमल ग्राफ थ्योरी
• रैंडम ग्राफ
• सामयिक ग्राफ सिद्धांत

गणित के संबंधित क्षेत्र

• साहचर्य
• समूह सिद्धांत
• गांठ सिद्धांत
• रैमसे सिद्धांत

सामान्यीकरण

• हाइपरग्राफ
• सार सरल जटिल

प्रमुख ग्राफ सिद्धांतकार

• नोगा अलोन|अलोन, नोगा
• क्लाउड बर्ज | बर्ज, क्लाउड
• बेला बोल्लोबस|बोलोबास, बेला
• जॉन एड्रियन बॉन्डी|बॉन्डी, एड्रियन जॉन
• ग्राहम ब्राइटवेल|ब्राइटवेल, ग्राहम
• मारिया चुडनोवस्की|चुडनोवस्की, मारिया
• फैन चुंग | चुंग, फैन
• गेब्रियल एंड्रयू डिराक | डिराक, गेब्रियल एंड्रयू
• एड्जर डब्ल्यू. डिज्कस्ट्रा|डिज्कस्ट्रा, एडजर डब्ल्यू।
• पॉल एर्डोस|एर्डोस, पॉल
• लियोनहार्ड यूलर|यूलर, लियोनहार्ड
• राल्फ फौड्री|फौद्री, राल्फ
• हर्बर्ट फ्लीश्चनर | फ्लेशनर, हर्बर्ट
• मार्टिन चार्ल्स गोलम्बिक | गोलम्बिक, मार्टिन
• रोनाल्ड ग्राहम|ग्राहम, रोनाल्ड
• फ्रैंक हैरी|हैरी, फ्रैंक
• पर्सी जॉन हीवुड|हीवुड, पर्सी जॉन
• एंटन कोटज़िग|कोटज़िग, एंटोन
• डेन्स कोनिग|कोनिग, डेनेस
• लास्ज़्लो लोवाज़|लाज़्लो, लास्ज़्लो
• यू.एस.आर. मूर्ति|मूर्ति, यू.एस.आर.
• जारोस्लाव नेसेट्रिल|नेसेट्रिल, जारोस्लाव
• अल्फ्रेड रेनी|रेनी, अल्फ्रेड
• गेरहार्ड रिंगेल|रिंगेल, गेरहार्ड
• नील रॉबर्टसन (गणितज्ञ) | रॉबर्टसन, नील
• पॉल सीमोर (गणितज्ञ) | सीमोर, पॉल
• बेनी सुदाकोव|सुदाकोव, बेनी
• एंड्रे स्ज़ेमेरीडी|ज़ेमेरीडी, एंड्रे
• रॉबिन थॉमस (गणितज्ञ) | थॉमस, रॉबिन
• कार्स्टन थॉमसन | थॉमसन, कार्स्टन
• पाल तुरान | तुरान, पाल
• डब्ल्यू.टी. टुट्टे|टुट्टे, डब्ल्यू.टी.
• हस्लर व्हिटनी|व्हिटनी, हस्लर

संदर्भ

• Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability.
• Claude, Claude (1958). Théorie des graphes et ses applications. Paris: Dunod. English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.
• Biggs, N.; Lloyd, E.; Wilson, R. (1986). Graph Theory, 1736–1936. Oxford University Press.
• Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Springer. ISBN 978-1-84628-969-9.
• Bollobás, Béla; Riordan, O. M. (2003). Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)) (1st ed.). Weinheim: Wiley VCH.
• Chartrand, Gary (1985). Introductory Graph Theory. Dover. ISBN 0-486-24775-9.
• Deo, Narsingh (1974). Graph Theory with Applications to Engineering and Computer Science (PDF). Englewood, New Jersey: Prentice-Hall. ISBN 0-13-363473-6.
• Gibbons, Alan (1985). Algorithmic Graph Theory. Cambridge University Press.
• Golumbic, Martin (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press.
• Harary, Frank (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley.
• Harary, Frank; Palmer, Edgar M. (1973). Graphical Enumeration. New York, New York: Academic Press.
• Mahadev, N. V. R.; Peled, Uri N. (1995). Threshold Graphs and Related Topics. North-Holland.
• Newman, Mark (2010). Networks: An Introduction. Oxford University Press.
• Kepner, Jeremy; Gilbert, John (2011). Graph Algorithms in The Language of Linear Algebra. Philadelphia, Pennsylvania: SIAM. ISBN 978-0-898719-90-1.

बाहरी संबंध

• "Graph theory", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Graph theory tutorial
• A searchable database of small connected graphs
• Image gallery: graphs at the Wayback Machine (archived February 6, 2006)
• Concise, annotated list of graph theory resources for researchers
• rocs — a graph theory IDE
• The Social Life of Routers — non-technical paper discussing graphs of people and computers
• Graph Theory Software — tools to teach and learn graph theory
• Online books, and library resources in your library and in other libraries about graph theory
• A list of graph algorithms with references and links to graph library implementations

ऑनलाइन पाठ्यपुस्तकें

• कॉम्बिनेटोरियल ऑप्टिमाइजेशन प्रॉब्लम्स में फेज ट्रांजिशन, सेक्शन 3: इंट्रोडक्शन टू ग्राफ्स (2006) हार्टमैन और वीग द्वारा
• डिग्राफ: थ्योरी एल्गोरिद्म्स एंड एप्लीकेशन 2007 जोर्जेन बैंग-जेन्सेन और ग्रेगरी गुटिन द्वारा
• ग्राफ थ्योरी, रेइनहार्ड डायस्टेल द्वारा