पथ (ग्राफ सिद्धांत)

For the family of graphs known as paths, see Path graph.

एक त्रि-आयामी अतिविम ग्राफ़ लाल रंग में हैमिल्टनियन पथ और गहरा काला रंग सबसे लंबा प्रेरित पथ दिखा रहा है।।

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

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

परिभाषाएँ

चाल, निशान, और पथ

• चाल किनारों का एक परिमित या अनंत क्रम है जो शीर्षों के अनुक्रम में शामिल होता है

मान लीजिए कि G = (V, E, ϕ) एक ग्राफ है। एक परिमित चाल किनारों (e1, e2, …, en − 1) का एक क्रम हैजिसके लिए शीर्ष का एक क्रम (v₁, v₂, …, v_n) है जैसे कि ϕ(ei) = {vi, vi 1} के लिए i = 1, 2, …, n − 1. (v1, v2, …, vn) चाल का शीर्ष अनुक्रम है।अगर v1 = vn, चाल बंद है ,अन्यथा यह खुला है। एक अनंत चाल यहाँ वर्णित एक ही प्रकार के किनारों का एक क्रम है, लेकिन कोई पहला या अंतिम शीर्ष नहीं है, और एक अर्ध-अनंत चाल (या किरण) का पहला शीर्ष है लेकिन कोई अंतिम शीर्ष नहीं है।

• निशान एक ऐसा चाल है जिसके सभी किनारे अलग-अलग होते हैं।
• एक पथ एक निशान है जिसमें सभी कोने (और सभी किनारे भी) अलग-अलग हैं।

इसी प्रकार एक निशान या पथ के लिए यदि w = (e1, e2, …, en − 1) शीर्ष अनुक्रम (v1, v2, …, vn) के साथ एक परिमित चाल है, तो w को v1 से vn तक की चाल कहा जाता है। यदि दो अलग-अलग शीर्षों के बीच एक परिमित चाल है तो एक परिमित निशान और उनके बीच एक परिमित पथ भी है।

कुछ लेखकों के लिए यह आवश्यक नहीं है कि पथ के सभी शीर्ष भिन्न हों और इसके बजाय ऐसे पथ को संदर्भित करने के लिए 'सरल पथ' शब्द का उपयोग करें जहां सभी कोने अलग-अलग हों।

एक भारित ग्राफ में प्रत्येक किनारे के साथ एक मान (वजन) को जोड़ता है। भारित ग्राफ़ में चलने (या निशान या पथ) का भार पार किए हुए किनारे के भार का योग होता है। कभी-कभी वजन के स्थान पर लागत या लंबाई शब्दों का प्रयोग किया जाता है।

निर्देशित चाल, निर्देशित निशान, और निर्देशित पथ

• एक निर्देशित चाल किनारा (ग्राफ सिद्धांत) का एक परिमित या अनंत अनुक्रम है जो उसी दिशा में निर्देशित होता है जो शीर्ष (ग्राफ सिद्धांत) के अनुक्रम में शामिल होता है।

मान लीजिए कि G = (V, E, ϕ) एक ग्राफ है। एक परिमित निर्देशित चाल किनारों का एक क्रम है (e₁, e₂, …, e_{n − 1}) जिसके लिए शीर्ष का एक क्रम (v₁, v₂, …, v_n) है जैसे कि ϕ(e_i) = (v_i, v_{i + 1}) के लिए i = 1, 2, …, n − 1. (v₁, v₂, …, v_n) निर्देशित चाल का शीर्ष क्रम है। अगर v1 = vn, निर्देशित चाल बंद है ,अन्यथा यह खुला है। एक अनंत निर्देशित चाल यहाँ वर्णित एक ही प्रकार के किनारों का एक क्रम है, लेकिन कोई पहला या अंतिम शीर्ष नहीं है, और एक अर्ध-अनंत निर्देशित चाल (या किरण) का पहला शीर्ष है लेकिन कोई अंतिम शीर्ष नहीं है।

• एक निर्देशित निशान एक निर्देशित मार्ग है जिसमें सभी किनारे अलग-अलग होते हैं।
• एक निर्देशित पथ एक निर्देशित पथ है जिसमें सभी शीर्ष भिन्न होते हैं।

इसी प्रकार एक निर्देशित निशान या पथ के लिए यदि w = (e1, e2, …, en − 1) शीर्ष अनुक्रम (v1, v2, …, vn) के साथ एक परिमित निर्देशित चाल है, तो w को v1 से vn तक की चाल कहा जाता है। यदि दो अलग-अलग शीर्षों के बीच एक परिमित निर्देशित चाल है तो एक परिमित निर्देशित निशान और उनके बीच एक परिमित निर्देशित पथ भी है।

एक सरल निर्देशित पथ एक ऐसी चाल है जहाँ सभी शीर्ष भिन्न होते हैं।

एक भारित ग्राफ़ निर्देशित ग्राफ़ में प्रत्येक किनारे के साथ एक मान (वजन) को जोड़ता है। भारित निर्देशित ग्राफ़ में एक निर्देशित चाल (या निशान या पथ) का भार अनुप्रस्थ किनारों के भार का योग होता है। कभी-कभी वजन के स्थान पर लागत या लंबाई शब्दों का प्रयोग किया जाता है।

उदाहरण

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

पथ ढूँढना

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

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

यह भी देखें

• ग्राफ सिद्धांत की शब्दावली
• पथ ग्राफ
• बहुभुज श्रृंखला
• सबसे छोटा पथ समस्या
• सबसे लंबी पथ समस्या
• दिज्क्स्ट्रा का कलन विधि
• बेलमैन-फोर्ड कलन विधि
• फ्लोयड-वॉर्शल कलन विधि
• स्वयं से परहेज करना
• सबसे छोटा पथ ग्राफ

संदर्भ

• Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability.
• Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. North Holland. p. 12-21. ISBN 0-444-19451-7.
• Diestel, Reinhard (2005). Graph Theory. Springer-Verlag. pp. 6–9. ISBN 3-540-26182-6.
• Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press. pp. 5–6. ISBN 0-521-28881-9.
• Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (1990). Paths, Flows, and VLSI-Layout. Springer-Verlag. ISBN 0-387-52685-4.