Как найти треугольник внутри графика?

Вот упражнение в Руководстве по разработке алгоритмов.

Рассмотрим задачу определения, является ли заданный неориентированный граф G = (V, E) содержит треугольник или цикл длины 3.

(a) Дайте O (| V | ^ 3), чтобы найти треугольник, если он существует.

(b) Улучшить ваш алгоритм работает во времени O (| V | · | E |). Вы можете предположить | V | ≤ | E |.

Обратите внимание, что эти границы дают вам время для преобразования между матрица смежности и представления списка смежности G.

Вот мои мысли:

(a) Если граф задан как список смежности, я могу преобразовать список в матрицу через O (| V | ^ 2). то я делаю:

for (int i = 0;i < n;i++) 
   for (int j = i+1;j < n;j++) 
   if (matrix[i][j] == 1) 
      for (int k = j+1;k < n;k++) 
         if (matrix[i][k] == 1 && matrix[j][k] == 1)
             return true;

Это должно дать O (| V | ^ 3), чтобы проверить треугольник.

(б) Мое первое интуитивное заключается в том, что если граф задан как список смежности, тогда я сделаю bfs. Всякий раз, когда найден перекрестный край, например, if y-x is a cross edge, тогда я будет check whether parent[y] == parent[x], if true, then a triangle is found.

Может ли кто-нибудь сказать мне, правильно ли мое мышление или нет?

Также для этого (б) я не уверен в его сложности. Должно ли это быть O (| V | + | E |), правильно?

Как я могу сделать это в O (| V | * | E |)?

Ответы

Ответ 1

Возможное решение O(|V||E|) - та же идея грубой силы в (a):

for each edge (u, v):
  for each vertex w:
     if (v, w) is an edge and (w, u) is an edge:
          return true
return false

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

Пример счетчика для решения BFS:

       A
     / | \
    /  |  \
   B   C   D
   |   |   |
   |   |   |
   F---G---H
   |       |
   ---------
    (F, H) is also an edge

Обратите внимание, что father[F] != father[G] != father[H], таким образом, алгоритм вернет false - но тем не менее (F, G, H) является допустимым решением!

Ответ 2

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

Наивное матричное умножение занимает время O(n^3), но есть быстрые алгоритмы умножения матрицы, которые работают лучше. Одним из наиболее известных является алгоритм Coppersmith-Winograd, который работает в O(n^2.4) времени. Это означает, что алгоритм выглядит примерно так:

Используйте O(V^2) время для преобразования в матрицу смежности.
Используйте O(V^2.4) время для вычисления квадрата матрицы смежности.
Используйте O(V^2) время для проверки матриц для совпадения ненулевых записей.
Индекс строки и столбца, в котором вы находите совпадающие ненулевые записи в (если они есть), указывает вам два задействованных узла.
Используйте O(V) время, чтобы сузить третий node общий для обоих известных узлов.

Таким образом, в целом это занимает время O(V^2.4); точнее, требуется, однако, длинное матричное умножение. Вы можете динамически переключаться между этим алгоритмом и алгоритмом if-any-edge-end-points-have-a-common-neighbour который объясняет в своем ответе, чтобы улучшить это до O(V min(V^1.4, E)).

Здесь бумага, которая углубляется в проблему.

Это какая-то опрятная, как зависимость от теоретических открытий. Если гипотезы о матричном умножении, фактически являющиеся квадратичными, оказываются истинными, тогда вы получите очень хорошую временную привязку O(V^2) или O(V^2 log(V)) или что-то в этом роде. Но если квантовые компьютеры будут работать, мы сможем сделать даже лучше, чем это (что-то вроде O(V^1.3))!

Ответ 3

Вот что я думаю:

Решение origianl BFS неверно, как указано выше. Но мы можем изменить DFS. Назначьте номера посетимым узлам, посетив каждую вершину в DFS. Теперь, если мы достигнем вершины (в вопросе я увидел кросс-ребра, их нет в неориентированном графе), мы проверяем его список смежности и предположим, что одна вершина обнаружена (но не обработана, не может быть), тогда мы проверяем ее число, Если разность равна 2, то существует цикл длины 3.

Ответ 4

Мне действительно нравится решение матричного умножения, обсуждаемое в этом сообщении в блоге.

Пусть a = матрица смежности

Смежности в матрице a * a (a2), умноженные, являются числами двухмерных путей
Примыкания в a2 * умноженная матрица - это числа трехмерных путей

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