ग्राफ डिग्री अनुक्रम सत्यापनकर्ता
एर्डोस-गैलाई प्रमेय · हैवेल-हाकिमी एल्गोरिदम · ग्राफ निर्माण
निर्धारित करने के लिए पूर्णांकों का एक अनुक्रम दर्ज करें कि क्या यह एर्डोस-गैलाई प्रमेय (Erdős–Gallai theorem) का उपयोग करके एक वैध ग्राफिकल डिग्री अनुक्रम (graphical degree sequence) है, और फिर हैवेल-हाकिमी के माध्यम से इसका एक ग्राफ प्राप्त करें।
त्वरित उदाहरण (Quick Examples)
जांच और गुण (Checks & Properties)
एर्डोस-गैलाई शर्त तालिका (Erdős–Gallai Condition Table)
प्रत्येक k के लिए, असमानता ∑i=1k di ≤ k(k−1) + ∑i=k+1n min(di, k) लागू होनी चाहिए।
| k | बायाँ भाग: ∑ di | दायाँ भाग: k(k-1)+∑min | संतुष्ट है? |
|---|
हैवेल-हाकिमी निर्माण चरण (Havel-Hakimi Construction Steps)
अवरोही क्रम में व्यवस्थित करें, उच्चतम डिग्री वाले शीर्ष को अगले d शीर्षों से जोड़ें, उसे हटाएं और दोहराएं।
| चरण (Step) | वर्तमान अनुक्रम (Current Sequence) | जोड़े गए किनारे (Edges Added) | शेष अनुक्रम (Remaining) |
|---|
ग्राफ निर्माण — किनारों की सूची (Edge List)
ग्राफ विज़ुअलाइज़ेशन (Graph Visualization)
डिग्री अनुक्रम क्या है?
ग्राफ थ्योरी में, एक डिग्री अनुक्रम (degree sequence) किसी ग्राफ के सभी शीर्षों की डिग्रियों की एक सूची होती है, जिसे आमतौर पर अवरोही क्रम (non-increasing order) में लिखा जाता है। किसी शीर्ष की डिग्री उससे जुड़े किनारों की संख्या होती है।
एर्डोस-गैलाई प्रमेय (Erdős–Gallai Theorem)
एर्डोस-गैलाई प्रमेय (1960 में पॉल एर्डोस और टिबोर गैलाई द्वारा सिद्ध) यह निर्धारित करने का सटीक तरीका प्रदान करता है कि क्या कोई अनुक्रम ग्राफिकल है। एक अनुक्रम d₁ ≥ d₂ ≥ … ≥ dₙ ग्राफिकल है यदि और केवल यदि:
- सम योग: सभी डिग्रियों का योग सम (even) होना चाहिए (Handshaking Lemma)।
- एर्डोस-गैलाई असमानता: प्रत्येक k = 1, 2, …, n के लिए असमानता संतुष्ट होनी चाहिए।
हैवेल-हाकिमी एल्गोरिदम (Havel-Hakimi Algorithm)
हैवेल-हाकिमी एल्गोरिदम एक रचनात्मक दृष्टिकोण प्रदान करता है: यह न केवल ग्राफिकल होने की जाँच करता है बल्कि एक वास्तविक ग्राफ भी बनाता है।
यह प्रक्रिया इस प्रकार है:
- अनुक्रम को अवरोही क्रम में व्यवस्थित करें।
- उच्चतम डिग्री d वाले पहले शीर्ष को चुनें और उसे अगले d शीर्षों से जोड़ें।
- उन d शीर्षों की डिग्री को 1 से घटाएं और पहले शीर्ष को हटा दें।
- यदि कोई डिग्री नकारात्मक हो जाती है, तो अनुक्रम अमान्य है।