algorithm
न्यूनतम वर्टेक्स कवर के लिए बहुपद-टाइम बाउंड एल्गोरिदम
खोज…
परिचय
यह जुड़ा हुआ अप्रत्यक्ष ग्राफ का न्यूनतम शीर्ष कवर प्राप्त करने के लिए एक बहुपद एल्गोरिथ्म है। इस एल्गोरिथ्म की समय जटिलता हे (n2) है
पैरामीटर
| परिवर्तनशील | अर्थ |
|---|---|
| जी | इनपुट संयुक्त राष्ट्र के निर्देशित ग्राफ से जुड़ा हुआ है |
| एक्स | सिरों का सेट |
| सी | अंतिम सेट कोने में |
टिप्पणियों
इस एल्गोरिथ्म में पहली बात यह है कि इसकी डिग्री के अनुसार अवरोही क्रम में सॉर्ट किए गए ग्राफ़ के सभी कोने प्राप्त करने के लिए।
उसके बाद आप उन पर पुनरावृत्ति करते हैं और प्रत्येक को अंतिम कोने सेट में जोड़ते हैं, जिसमें इस सेट में कोई निकटवर्ती शीर्ष नहीं होता है।
अंतिम अवस्था में अंतिम छोरों पर पुनरावृति होती है और इस पंक्ति में उन सभी लंबों को हटाते हैं जिनके पास आसन्न कोने में से एक है।
एल्गोरिथ्म छद्म कोड
एल्गोरिथ्म PMinVertexCover (ग्राफ जी)
इनपुट जुड़ा ग्राफ जी
आउटपुट न्यूनतम वर्टेक्स कवर सेट सी
Set C <- new Set<Vertex>()
Set X <- new Set<Vertex>()
X <- G.getAllVerticiesArrangedDescendinglyByDegree()
for v in X do
List<Vertex> adjacentVertices1 <- G.getAdjacent(v)
if !C contains any of adjacentVertices1 then
C.add(v)
for vertex in C do
List<vertex> adjacentVertices2 <- G.adjacentVertecies(vertex)
if C contains any of adjacentVertices2 then
C.remove(vertex)
return C
C, ग्राफ G का न्यूनतम शीर्ष आवरण है
हम अपनी डिग्री के अनुसार कोने की छँटाई के लिए बाल्टी के प्रकार का उपयोग कर सकते हैं क्योंकि डिग्री का अधिकतम मूल्य (n-1) है जहाँ n, कोने की संख्या है तो छँटाई की समय जटिलता O (n) होगी