पथ ग्राफ

This article is about रेखांकन का एक परिवार. For मनमाने रेखांकन के भाग के रूप में पथ, see पथ (ग्राफ सिद्धांत).

Not to be confused with पंक्ति ग्राफ.

Path graph
A path graph on 6 vertices
Vertices	n
Edges	n − 1
Radius	⌊n / 2⌋
Diameter	n − 1
Automorphisms	2
Chromatic number	2
Chromatic index	2
Spectrum	$\{2\cos \left({\frac {k\pi }{n+1}}\right);$$k=1,\cdots ,n\}$
Properties	Unit distance Bipartite graph Tree
Notation	Pn
Table of graphs and parameters

ग्राफ़ सिद्धांत के गणित क्षेत्र में, पथ ग्राफ़ या रेखीय ग्राफ़ ग्राफ़ (असतत गणित) है जिसका शीर्ष (ग्राफ़ सिद्धांत) क्रम में सूचीबद्ध किया जा सकता है v₁, v₂, …, v_n जैसे किनारे (ग्राफ थ्योरी) हैं {v_i, v_i+1} कहाँ i = 1, 2, …, n − 1. समतुल्य रूप से, कम से कम दो शीर्षों वाला पथ जुड़ा हुआ है और इसमें दो टर्मिनल शिखर हैं (कोने जिनके पास डिग्री (ग्राफ सिद्धांत) 1 है), जबकि अन्य सभी (यदि कोई हो) की डिग्री 2 है।

ग्राफ़ थ्योरी की ग्लोसरी के रूप में उनकी भूमिका में पथ अक्सर महत्वपूर्ण होते हैं # अन्य ग्राफ़ के सबग्राफ़, जिस स्थिति में उन्हें उस ग्राफ़ में पाथ (ग्राफ़ थ्योरी) कहा जाता है। पथ पेड़ (ग्राफ सिद्धांत) का विशेष रूप से सरल उदाहरण है, और वास्तव में पथ वास्तव में ऐसे पेड़ हैं जिनमें कोई शीर्ष 3 या अधिक डिग्री नहीं है। पथों के अलग संघ को रेखीय वन कहा जाता है।

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

डायकिन आरेखों के रूप में

बीजगणित में, पथ ग्राफ टाइप ए के डायनकिन आरेख के रूप में दिखाई देते हैं। जैसे, वे टाइप ए की जड़ प्रणाली और टाइप ए के वेइल समूह को वर्गीकृत करते हैं, जो सममित समूह है।

यह भी देखें

• पथ (ग्राफ सिद्धांत)
• कमला का पेड़
• पूरा ग्राफ
• शून्य ग्राफ
• पथ अपघटन
• चक्र (ग्राफ सिद्धांत)

संदर्भ

• 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.

बाहरी संबंध

• Weisstein, Eric W. "Path Graph". MathWorld.