Hamiltonian Cycle in Hindi | हैमिल्टोनियन साइकिल क्या है?

हैमिल्टोनियन साइकिल क्या है? (Hamiltonian Cycle in Hindi)

हैमिल्टोनियन साइकिल (Hamiltonian Cycle) एक ग्राफ थ्योरी (Graph Theory) की समस्या है, जिसमें एक ग्राफ (Graph) के सभी वर्टिस (Vertices) को एक बार भ्रमण करने के बाद, प्रारंभिक वर्टेक्स पर वापस लौटने का मार्ग खोजना होता है।

हैमिल्टोनियन साइकिल के नियम (Rules of Hamiltonian Cycle)

• ग्राफ में उपस्थित हर वर्टेक्स को केवल एक बार विजिट करना होता है।
• साइकिल को प्रारंभिक वर्टेक्स (Starting Vertex) पर समाप्त होना चाहिए।
• कोई भी वर्टेक्स दो बार विजिट नहीं किया जा सकता (सिवाय प्रारंभिक वर्टेक्स के)।

हैमिल्टोनियन साइकिल बनाम यूलरियन साइकिल (Hamiltonian Cycle vs Eulerian Cycle)

हैमिल्टोनियन साइकिल खोजने की प्रक्रिया (Algorithm to Find Hamiltonian Cycle)

इस समस्या को बैकट्रैकिंग (Backtracking) तकनीक का उपयोग करके हल किया जाता है।

1. प्रारंभिक वर्टेक्स से यात्रा शुरू करें।
2. अगला संभावित वर्टेक्स खोजें, जो पहले विजिट नहीं किया गया हो।
3. यदि सभी वर्टिस को विजिट किया जा चुका है और अंतिम वर्टेक्स प्रारंभिक वर्टेक्स से जुड़ा है, तो साइकिल बन चुकी है।
4. यदि कोई वैध पथ नहीं मिलता, तो बैकट्रैक करें और अन्य विकल्प आज़माएँ।

हैमिल्टोनियन साइकिल का छद्मकोड (Pseudocode of Hamiltonian Cycle)

bool hamiltonianCycle(graph, path[], pos)
    if pos == N:
        if graph[path[pos-1]][path[0]] == 1:
            return true
        else:
            return false
    for v in 1 to N-1:
        if isSafe(v, graph, path, pos):
            path[pos] = v
            if hamiltonianCycle(graph, path, pos+1) == true:
                return true
            path[pos] = -1  # Backtrack
    return false

हैमिल्टोनियन साइकिल का उदाहरण (Example of Hamiltonian Cycle)

माना कि हमारे पास निम्नलिखित ग्राफ है:

संभावित हैमिल्टोनियन साइकिल:

• A → B → C → D → A
• A → C → B → D → A

हैमिल्टोनियन साइकिल की समय जटिलता (Time Complexity of Hamiltonian Cycle)

• बैकट्रैकिंग एल्गोरिदम: O(N!)
• ब्रूट फोर्स अप्रोच: O(N² × 2^N)

हैमिल्टोनियन साइकिल के अनुप्रयोग (Applications of Hamiltonian Cycle)

• ट्रैवलिंग सेल्समैन प्रॉब्लम (Traveling Salesman Problem - TSP)
• सर्किट डिज़ाइन (Circuit Layout Design)
• नेटवर्क रूटिंग (Network Routing)
• जेनेटिक एल्गोरिदम और ऑप्टिमाइज़ेशन (Genetic Algorithms & Optimization)

निष्कर्ष

हैमिल्टोनियन साइकिल एक महत्वपूर्ण ग्राफ थ्योरी समस्या है, जिसका उपयोग नेटवर्क डिज़ाइन, सर्किट प्लानिंग, और लॉजिस्टिक्स ऑप्टिमाइज़ेशन में किया जाता है। यह एक NP-Complete समस्या है, जिसे बैकट्रैकिंग और अन्य हीयूरिस्टिक तकनीकों का उपयोग करके हल किया जा सकता है।