Đồ thị: tìm bồn rửa dưới O (| V |) - hoặc không thể hiển thị nó ở

Question

Tôi có biểu đồ có n nút dưới dạng ma trận kề kề.

Có thể phát hiện bồn rửa dưới thời gian O(n) không?

Nếu có, làm cách nào? Nếu không, làm thế nào để chúng tôi chứng minh điều đó?

Đỉnh chìm là một đỉnh có cạnh tới từ các nút khác và không có cạnh ngoài.

Answer 1

Giả sử đến trái rằng có tồn tại một thuật toán truy vấn ít hơn (n-2)/2 cạnh, và để cho các đối thủ trả lời những thắc mắc tùy tiện. Theo nguyên tắc Pigeonhole, tồn tại (ít nhất) hai nút v, w không phải là điểm cuối của bất kỳ cạnh nào được truy vấn. Nếu thuật toán xuất ra v, thì đối thủ làm cho nó sai bằng cách đặt vào mọi cạnh với sink w, và tương tự nếu thuật toán xuất ra w.

Answer 2

Trong trường hợp đồ thị được chỉ dẫn chung, không, và tôi không nghĩ rằng nó cần bằng chứng chính thức. Tốt nhất, phát hiện một bồn rửa yêu cầu bạn hoặc là xác định các nút và kiểm tra xem nó không có cạnh đi, hoặc kiểm tra tất cả các nút khác và thấy rằng không ai trong số họ có kết nối đến từ nó. Trong thực tế, bạn kết hợp hai trong một thuật toán loại bỏ, nhưng không có phím tắt.

Nhân tiện, có sự bất đồng về định nghĩa của bồn rửa chén. Nó không phải là bình thường để yêu cầu tất cả các nút khác kết nối với bồn rửa, bởi vì bạn có thể có nhiều bồn rửa. Ví dụ, hàng dưới cùng in this diagram là tất cả các bồn rửa và hàng trên cùng là tất cả các nguồn. Tuy nhiên, nó cho phép bạn giảm độ phức tạp xuống O (n). Xem here cho một số cuộc thảo luận hơi bị cắt xén.

Answer 3

This page trả lời câu hỏi chính xác của bạn. Thuật toán thời gian tuyến tính là

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" 

Answer 4

Tôi đã làm việc về vấn đề này và tôi tin rằng điều này làm nó:

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|) 
********************/ 

}

Answer 5

Reading vào liên kết được cung cấp bởi SPWorley Tôi đã nhắc nhở về algo cây giải cho việc tìm kiếm các yếu tố tối thiểu trong một dãy số. Nút ở trên cùng của cây là phần tử tối thiểu. Vì thuật toán trong liên kết cũng nói về sự cạnh tranh giữa hai nút (v, w) được thành công bởi w nếu v-> w bằng v.Chúng ta có thể sử dụng một thuật toán tương tự như tìm yếu tố tối thiểu để tìm ra cái bồn rửa. Tuy nhiên, một nút được trả về không phụ thuộc vào sự tồn tại của một bồn rửa. Mặc dù, nếu một bồn rửa tồn tại, nó luôn luôn được trả về. Do đó, cuối cùng chúng ta phải kiểm tra xem nút trả về có phải là một cái chìm hay không.

//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 

Answer 6

Tôi đã tìm ra giải pháp cho điều này.

Tôi giả sử mảng được khởi tạo với tất cả 0 (nếu không N cần được điền bằng 0) và M là ma trận kề cho biểu đồ. Tôi cho n là số nút (n = | V |).

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 

Tại sao điều này làm việc (không chính thức chứng minh): Bất kỳ nút với bất kỳ cạnh đi từ nó không phải là một bồn rửa phổ quát. Vì vậy, nếu M [i, j] là 1 cho bất kỳ j, tôi không thể là một bồn rửa.

Nếu M [i, j] là 0 cho bất kỳ i nào, thì tôi không có cạnh j, và j không thể là bồn rửa chung.

A 1 tại N [i] chỉ định rằng tôi biết đó không phải là bồn rửa và bất kỳ nút nào mà tôi biết không phải là bồn rửa có thể bị bỏ qua cả i và j. Tôi dừng lại khi một trong hai exeeds n.

Bằng cách này tôi tiếp tục kiểm tra bất kỳ nút nào, mà tôi vẫn không biết không phải là bồn rửa, cho đến khi 1 hoặc 0 bồn rửa có thể vẫn còn.

Do đó, bất kỳ nút nào vẫn là 0 ở cuối vòng lặp phải là bồn rửa và sẽ chỉ có 1 hoặc 0 trong số đó.

Tại sao nó là O (n): Điều này luôn tăng hoặc là i hoặc j. Nó dừng lại khi exeeds n. Như vậy trường hợp xấu nhất cho vòng lặp là 2n. Công việc trong vòng lặp là hằng số. Vòng lặp cuối cùng là trường hợp xấu nhất n. Do đó thuật toán là O (3n) = O (n).

Giải pháp này dựa trên ý tưởng về vấn đề người nổi tiếng, đó là cách xem xét cùng một vấn đề.

Answer 7

Có rất nhiều thuật toán cho thấy cách tìm bồn rửa phổ trong O (n) nhưng chúng rất phức tạp và không thể dễ dàng hiểu được. Tôi đã tìm thấy nó trên internet trong giấy cho thấy làm thế nào để tìm thấy một bồn rửa phổ quát trong O (n) rất thuận lợi.

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 

Bằng cách này, bạn sẽ kết thúc với nút chìm trong SINK được đặt trong thời gian "n-1". đó là thời gian O (n).