Графики: найдите раковину меньше, чем O (| V |) - или покажите, что это невозможно

Question

У меня есть график с n узлами в виде матрицы смежности .

Можно ли обнаружить раковину менее чем за O(n) раз?

Если да, то как? Если нет, то как мы это докажем?

Sink vertex - это вершина, у которой есть входящие ребра из других узлов и нет исходящих ребер.

Answer 1

Читая ссылку, предоставленную SPWorley, мне напомнили о алгоритме дерева турниров для поиска минимального элемента в массиве чисел. Узел в верхней части дерева является минимальным элементом. Так как алгоритм в ссылке также говорит о конкуренции между двумя узлами (v, w), за которой следует w, если v-> 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

Answer 2

Эта страница отвечает на ваш точный вопрос. Алгоритм линейного времени равен

   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 3

Предположим противное, что существует алгоритм, который запрашивает меньше (n-2) / 2 ребер, и позволяет противнику произвольно отвечать на эти запросы. В соответствии с принципом голубиных отверстий существуют (по крайней мере) два узла v, w, которые не являются конечной точкой любого запрашиваемого ребра. Если алгоритм выдает v, то противник делает это неправильно, вставляя каждое ребро с приемником w, и аналогично, если алгоритм выдает w.

Answer 4

Существует так много алгоритмов, которые показывают, как найти универсальный приемник в O (n), но они настолько сложны и не могут быть легко поняты. Я нашел его в интернете на бумаге, которая показывает, как найти универсальный приемник в O (n) очень плавно.

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

По этому алгоритму вы получите узел приемника в вашем SINK, установленный за время "n-1". это O (N) время.

Answer 5

Я нашел решение этой проблемы.

Я предполагаю, что массивы инициализируются со всеми 0 (в противном случае N должен быть заполнен 0), и что M является матрицей смежности для графа. Я позволил n быть числом узлов (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

Почему это работает (не формальное доказательство): Любой узел с любыми ребрами, идущими от него, не является универсальным приемником. Таким образом, если M [i, j] равно 1 для любого j, я не могу быть стоком.

Если M [i, j] равно 0 для любого i, то у i нет ребра для j, и j не может быть универсальным стоком.

1 в N [i] обозначает, что я знаю, что это не приемник, и любой узел, который я знаю, не является приемником, может быть пропущен как для i, так и для j. Я останавливаюсь, когда либо превышает n.

Таким образом, я продолжаю проверять любые узлы, которые, как я до сих пор не знаю, не является приемником, пока не останется 1 или 0 возможных приемников.

Таким образом, любой узел, который все еще равен 0 в конце цикла, должен быть приемником, и их будет только 1 или 0.

Почему это O (n): Это всегда увеличивает или я или j. Останавливается, когда либо превышает n. Таким образом, наихудший случай для цикла - 2n. Работа в цикле постоянна. Последний цикл - наихудший случай n. Следовательно, алгоритм O (3n) = O (n).

Это решение основано на идее проблемы знаменитости, которая является способом рассмотрения той же проблемы.

Answer 6

Я работал над этой проблемой, и я считаю, что это делает это:

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 7

В случае общего ориентированного графа нет, и я не думаю, что ему нужны формальные доказательства. В лучшем случае для обнаружения приемника необходимо либо идентифицировать узел и проверить, что у него нет исходящих ребер, либо проверить каждый второй узел и убедиться, что ни у одного из них нет соединений, исходящих от него. На практике вы комбинируете два в алгоритме исключения, но ярлыка нет.

Кстати, есть разногласия по поводу определения раковины. Обычно все другие узлы подключаются к приемнику, поскольку у вас может быть несколько приемников. Например, нижний ряд на этой диаграмме - это все приемники, а верхний ряд - все источники. Однако это позволяет снизить сложность до O (n). См. здесь для немного искаженного обсуждения.