पथ ग्राफ
Path graph | |
---|---|
Vertices | n |
Edges | n − 1 |
Radius | ⌊n / 2⌋ |
Diameter | n − 1 |
Automorphisms | 2 |
Chromatic number | 2 |
Chromatic index | 2 |
Spectrum | |
Properties | Unit distance Bipartite graph Tree |
Notation | Pn |
Table of graphs and parameters |
ग्राफ़ सिद्धांत के गणित क्षेत्र में, पथ ग्राफ़ (या रेखीय ग्राफ़) एक ग्राफ़ (असतत गणित) होता है जिसके शीर्षों (ग्राफ़ सिद्धांत) को क्रम v1, v2, …, vn में सूचीबद्ध किया जा सकता है जैसे कि किनारे (ग्राफ सिद्धांत) {vi, vi+1} होते हैं जहाँ i = 1, 2, …, n − 1. समतुल्य रूप से, कम से कम दो शीर्षों वाला पथ जुड़ा हुआ है और इसमें दो टर्मिनल शीर्ष (कोने जिनके डिग्री (ग्राफ सिद्धांत) 1 है) हैं, जबकि अन्य सभी (यदि कोई हो) की डिग्री 2 है।
पथ अधिकांश अन्य ग्राफ़ के सबग्राफ के रूप में उनकी भूमिका में महत्वपूर्ण होते हैं, जिस स्थिति में उन्हें उस ग्राफ़ में पथ कहा जाता है। एक पथ एक ट्री (ग्राफ सिद्धांत) का एक विशेष रूप से सरल उदाहरण है, और वास्तव में पथ वास्तव में ऐसे ट्री हैं जिनमें कोई शीर्ष 3 या अधिक डिग्री नहीं है। पथों के अलग संघ को रेखीय वन कहा जाता है।
पथ (ग्राफ सिद्धांत) की मूलभूत अवधारणाएँ हैं, जिनका वर्णन अधिकांश ग्राफ़ सिद्धांत ग्रंथों के परिचयात्मक खंडों में किया गया है। उदाहरण के लिए, बॉन्डी और मूर्ति (1976), गिबन्स (1985), या डायस्टेल (2005) देखें।
डायकिन आरेखों के रूप में
बीजगणित में, पथ ग्राफ टाइप A के डायनकिन आरेख के रूप में दिखाई देते हैं। जैसे, वे टाइप A की जड़ प्रणाली और टाइप A के वेइल समूह को वर्गीकृत करते हैं, जो सममित समूह है।
यह भी देखें
- पथ (ग्राफ सिद्धांत)
- कमला का ट्री
- पूरा ग्राफ
- शून्य ग्राफ
- पथ अपघटन
- चक्र (ग्राफ सिद्धांत)
संदर्भ
- Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. North Holland. pp. 12–21. ISBN 0-444-19451-7.
{{cite book}}
: CS1 maint: url-status (link) - Diestel, Reinhard (2005). Graph Theory (3rd ed.). Graduate Texts in Mathematics, vol. 173, Springer-Verlag. pp. 6–9. ISBN 3-540-26182-6.