10

隣接行列nとしてノードを持つグラフがあります。

シンクを短時間で検出することは可能O(n)ですか?

はいの場合、どのように？いいえの場合、それをどのように証明しますか?

シンク頂点は、他のノードからの入力エッジを持ち、出力エッジを持たない頂点です。

4

7 に答える 7

10

SPWorley が提供するリンクを読んで、数値の配列の最小要素を見つけるためのトーナメント ツリー アルゴリズムを思い出しました。ツリーの一番上のノードは最小要素です。リンク内のアルゴリズムは、2 つのノード (v,w) 間の競合についても説明しているため、v->w の場合は w が成功し、それ以外の場合は 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
于 2012-04-16T07:40:23.427 に答える
7

このページはあなたの正確な質問に答えます。線形時間アルゴリズムは

   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"
于 2009-05-11T11:24:16.337 に答える
3

逆に、(n-2)/2 よりも少ないエッジを照会するアルゴリズムが存在し、敵対者がこれらの照会に任意に回答できるようにするとします。ピジョンホールの原理により、(少なくとも) 2 つのノード v、w が存在し、それらはクエリされたエッジのエンドポイントではありません。アルゴリズムが v を出力する場合、敵対者は、シンク w を持つすべてのエッジを配置することによってそれを誤ります。アルゴリズムが w を出力する場合も同様です。

于 2009-05-15T23:48:46.617 に答える
1

私はこの問題に取り組んできましたが、これでうまくいくと思います：

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

}

于 2011-01-21T01:26:57.040 に答える
1

一般的な有向グラフの場合は、いいえ、正式な証明は必要ないと思います。せいぜい、シンクを検出するには、ノードを特定して発信エッジがないことを確認するか、他のすべてのノードを調べて、そこからの接続がないことを確認する必要があります。実際には、除去アルゴリズムで 2 つを組み合わせますが、近道はありません。

ところで、シンクの定義については意見の相違があります。複数のシンクを持つことができるため、他のすべてのノードをシンクに接続する必要があるのは通常ではありません。たとえば、この図の一番下の行はすべてシンクで、一番上の行はすべてソースです。ただし、複雑さを O(n) に減らすことができます。少し歪んだ議論については、こちらを参照してください。

于 2009-05-11T11:19:10.060 に答える