मेरे पास n नोड्स आसन्नता मैट्रिक्स के रूप में ग्राफ है।ग्राफ: ओ (| वी |) से कम में एक सिंक ढूंढें - या दिखाएं कि यह नहीं किया जा सकता है
क्या O(n) से कम समय में एक सिंक का पता लगाना संभव है?
यदि हां, तो कैसे? यदि नहीं, हम इसे कैसे साबित करते हैं?
सिंक वर्टेक्स एक वर्टेक्स है जिसमें आने वाले किनारों को अन्य नोड्स और कोई आउटगोइंग किनारों से नहीं है।
विपरीत एक एल्गोरिथ्म है कि तुलना में (n-2)/2 किनारों कम प्रश्नों मौजूद है करने के लिए मान लीजिए, और विरोधी मनमाने ढंग से इन प्रश्नों का जवाब देना है। कबूतर सिद्धांत द्वारा, वहां मौजूद हैं (कम से कम) दो नोड्स वी, डब्ल्यू जो कि किसी किनारे की पूछताछ का अंत बिंदु नहीं है। यदि एल्गोरिदम v बना देता है, तो विरोधी इस सिंक डब्ल्यू के साथ हर किनारे डालकर गलत बनाता है, और इसी तरह अगर एल्गोरिदम आउटपुट डब्ल्यू करता है।
इसे कुछ केस विश्लेषण के साथ एन -1 में सुधार किया जा सकता है। – Dave
सामान्य निर्देशित ग्राफ के मामले में, नहीं, और मुझे नहीं लगता कि इसे औपचारिक प्रमाण की आवश्यकता है। सबसे अच्छा, एक सिंक का पता लगाने के लिए आपको नोड की पहचान करने की आवश्यकता होती है और जांच की जाती है कि इसमें कोई आउटगोइंग किनार नहीं है, या हर दूसरे नोड का निरीक्षण करें और देखें कि उनमें से कोई भी कनेक्शन नहीं आ रहा है। अभ्यास में, आप दोनों को उन्मूलन एल्गोरिदम में जोड़ते हैं, लेकिन कोई शॉर्टकट नहीं है।
वैसे, सिंक की परिभाषा पर असहमति है। सिंक से कनेक्ट होने वाले अन्य सभी नोड्स की आवश्यकता सामान्य नहीं है, क्योंकि आपके पास एकाधिक सिंक हो सकते हैं। उदाहरण के लिए, नीचे पंक्ति in this diagram सभी सिंक हैं, और शीर्ष पंक्ति सभी स्रोत हैं। हालांकि, यह आपको जटिलता को कम करने की अनुमति देता है (एन)। कुछ थोड़ा गड़बड़ चर्चा के लिए here देखें।
This page अपने सटीक प्रश्न का उत्तर दें। रैखिक समय एल्गोरिथ्म
def find-possible-sink(vertices):
if there's only one vertex, return it
good-vertices := empty-set
pair vertices into at most n/2 pairs
add any left-over vertex to good-vertices
for each pair (v,w):
if v -> w:
add w to good-vertices
else:
add v to good-vertices
return find-possible-sink(good-vertices)
def find-sink(vertices):
v := find-possible-sink(vertices)
if v is actually a sink, return it
return "there is no spoon^H^H^H^Hink"
वह पृष्ठ दिखाता है कि ओ (एन) – Mark
में इसे कैसे करें, आखिरी वाला शानदार है! –
मैं इस समस्या पर काम कर रहा है और मैं ऐसा करता मानना है कि यह:
int graph::containsUniversalSink() {
/****************************************************************
Returns: Universal Sink, or -1 if it doesn't exist
Paramters: Expects an adjacency-matrix to exist called matrix
****************************************************************/
//a universal sink is a Vertex with in-degree |V|-1 and out-degree 0
//a vertex in a graph represented as an adjacency-matrix is a universal sink
//if and only if its row is all 0s and its column is all 1s except the [i,i] entry - path to itself (hence out-degree |V|-1)
//for i=0..|V|-1, j=0..|V|-1
//if m[i][j]==0 then j is not universal sink (unless i==j) - column is not all 1s
//if m[i][j]==1 then i is not universal sink - row is not all 0s
int i=0,j=1;
while (i<numVertices && j<numVertices) {
if (j>i && matrix[i][j]==true) {
//we found a 1, disqualifying vertex i, and we're not in the last row (j>i) so we move to that row to see if it's all 0s
i=j;
if (j<numVertices-1) {
//if the row we're moving to is not the last row
//we want to start checking from one element after the identity element
//to avoid the possibility of an infinite loop
j++;
}
continue;
}
if (j==numVertices-1 && matrix[i][j]==false) {
//the last element in a row is a 0
//thus this is the only possible universal sink
//we have checked the row for 0s from i+1 (or i if we're in the last row) to numVertices-1 (inclusive)
//we need to check from 0 to i (inclusive)
for (j=0; j<i+1; j++) {
if (matrix[i][j]==true || (matrix[j][i]==false && i!=j)) {
//this row is not all 0s, or this column is not all 1s so return -1 (false)
return -1;
}
}
//row is all 0s, but we don't know that column is all 1s
//because we have only checked the column from 0 to i (inclusive), so if i<numVertices-1
//there could be a 0 in the column
//so we need to check from i+1 to numVertices-1 (inclusive)
for (j=i+1; j<numVertices; j++) {
if (matrix[j][i]==false) {
return -1;
}
}
//if we get here we have a universal sink, return it
return i;
}
j++;
}
//if we exit the loop there is no universal sink
return -1;
/********************
Runtime Analysis
The while loop will execute at most |V| times: j is incremented by 1 on every iteration
If we reach the end of a row - this can only happen once - then the first for loop will
execute i times and the second will execute numVertices-i times, for a combined numVertices iterations
So we have 2|V| loop executions for a run-time bound of O(|V|)
********************/
}
SPWorley द्वारा प्रदान की लिंक पढ़ना मैं में न्यूनतम तत्व को खोजने के लिए टूर्नामेंट पेड़ algo की याद दिला रहा था संख्याओं की एक सरणी। पेड़ के शीर्ष पर नोड एक न्यूनतम तत्व है। चूंकि लिंक में एल्गोरिदम भी दो नोड्स (वी, डब्लू) के बीच प्रतिस्पर्धा के बारे में बोलता है, जो वी द्वारा सफल होता है अगर अन्यथा v द्वारा। हम एक सिंक को खोजने के लिए न्यूनतम तत्व खोजने के समान एल्गोरिदम का उपयोग कर सकते हैं। हालांकि, एक सिंक के अस्तित्व के बावजूद एक नोड वापस किया जाता है। हालांकि, अगर एक सिंक मौजूद है तो यह हमेशा वापस आ जाता है। इसलिए, हमें अंततः यह जांचना है कि लौटा हुआ नोड एक सिंक है।
//pseudo code
//M -> adjacency matrix
int a=0
for(int i=1;i<vertices;++i)
{
if(M[a,i]) a=i;
}
//check that a is sink by reading out 2V entries from the matrix
return a; //if a is a sink, otherwise -1
मैंने इसका समाधान निकाला है।
मुझे लगता है कि सरणी सभी 0 के साथ शुरू की जाती है (अन्यथा एन को 0 से भरा होना चाहिए) और एम ग्राफ के लिए आसन्नता मैट्रिक्स है। मैं n नोड्स की संख्या होने दें (एन = | वी |)।
j,i = 1;
N = new int[n]
while (j <= n && i <= n) {
if (N[i] == 1) {
i++
} else if (N[j] == 1) {
j++;
} else if (M[i,j] == 1) {
N[i] = 1
i++
} else if (i == j) {
j++
} else {
N[j] = 1
j++
}
}
for (z = 1 to n) {
if (N[z] == 0) {
return z
}
}
return NULL
क्यों इस काम करता है (नहीं औपचारिक प्रमाण): से जा रहा है किसी भी किनारों के साथ किसी भी नोड एक सार्वभौमिक सिंक नहीं है। इस प्रकार, यदि एम [i, j] किसी भी जे के लिए 1 है, तो मैं एक सिंक नहीं हो सकता।
यदि एम [i, j] किसी के लिए 0 है, तो मेरे पास जम्मू नहीं है, और जे सार्वभौमिक सिंक नहीं हो सकता है।
एन पर एक 1 [i] यह निर्दिष्ट करता है कि मुझे पता है कि यह एक सिंक नहीं है, और मुझे पता है कि कोई भी नोड एक सिंक नहीं है I और j दोनों पर छोड़ दिया जा सकता है। जब मैं एन से बाहर निकलता हूं तो मैं रुक जाता हूं।
इस तरह से मैं किसी भी नोड्स को जांचता रहता हूं, कि मुझे अभी भी पता नहीं है कि 1 या 0 संभव सिंक बने रहें।
इस प्रकार लूप के अंत में 0 अभी भी कोई भी नोड सिंक होना चाहिए, और उनमें से केवल 1 या 0 होगा।
यह ओ (एन): यह हमेशा या तो जे या बढ़ाता है। यह बंद हो जाता है जब या तो ex exeds। इस प्रकार लूप के लिए सबसे खराब मामला 2 एन है। लूप में काम स्थिर है। अंतिम पाश सबसे खराब मामला है। इसलिए एल्गोरिदम ओ (3 एन) = ओ (एन) है।
यह समाधान सेलिब्रिटी समस्या के विचार पर आधारित है, जो एक ही समस्या पर विचार करने का एक तरीका है।
ऐसे कई एल्गोरिदम हैं जो दिखाते हैं कि ओ (एन) में सार्वभौमिक सिंक कैसे ढूंढें लेकिन वे बहुत जटिल हैं और आसानी से नहीं समझा जा सकता है। मैंने इसे पेपर में इंटरनेट पर पाया है जो दिखाता है कि ओ (एन) में एक सार्वभौमिक सिंक को आसानी से कैसे ढूंढें।
1) first create a "SINK" set consisting of all vertices of the graph also
create an adjacency list of the graph.
2) now choose first 2 elements of the set.
3) if(A(x,y)==1){
remove x; // remove x from "SINK" set.
}else{
remove y; } //remove y from "SINK" set.B
इस अलगो द्वारा आप "एन -1" समय में अपने सिंक सेट में सिंक नोड के साथ समाप्त हो जाएंगे। वह ओ (एन) समय है।
क्या आपका मतलब ओ (ई) समय है? आपको शायद कुछ मामलों के लिए सभी किनारों का निरीक्षण करना होगा, और किनारों का # एन^2 तक है। –
नहीं, मेरा मतलब है ओ (| वी |) - आपको सभी किनारों का निरीक्षण करने की आवश्यकता नहीं है। – flybywire