Турнирный график

Question

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

Структура данных - матрица смежности.

Какой алгоритм для определения, является ли график турнирным графиком?

Answer 1

В матрице смежности есть n ^ 2 записей, и вам нужна информация, которая есть во всех записях, чтобы решить проблему. (Вам нужны цифры 1, чтобы проверить, что правильные ребра существуют, и цифры 0, чтобы проверить, что задних ребер не существует.) Таким образом, поскольку вы должны прочитать как минимум N ^ 2 записей из матрицы, общая проблема должна занять хотя бы O (N ^ 2) раз.

Относительно попыток поиска в BFS: если ваш обход занимает O (n ^ 2) - что это и произойдет, из-за необходимости искать ребра в матрице смежности - тогда не имеет значения, является ли проверка на уровне ребра постоянной время, общий алгоритм все еще O (n ^ 2).

Еще один способ взглянуть на эту проблему: поскольку число ребер равно количеству возможных пар вершин, будет n * (n-1) / 2 ребер, что равно O (n ^ 2) , Ваш обход - O (V + E), то есть O (n + n ^ 2) и, следовательно, O (n ^ 2).

Поскольку наилучшим временем для этого алгоритма является O (n ^ 2), вы также можете просто перебрать верхнюю правую половину матрицы (выше диагонали) и проверить, что для каждого из этих элементов либо ) это 1, или б) его транспонированный эквивалент равен 1.

Answer 2

Добавить к комментарию tonfa:

Краткое описание : алгоритм "для каждого i ≠ j, проверьте, чтобы на графике было точно одно из (i, j) и (j, i)", является асимптотически оптимальным.

Подробнее: Чтобы просто прочитать в матрице смежности, вам понадобится время Ω (n ² ). Таким образом, нет способа решить эту проблему за o (n ² ) время. Но давайте проигнорируем ввод.

Предположим, что матрица уже находится в памяти. Чтобы убедиться, что неориентированная версия вашего графа завершена, вы должны каким-то образом определить, что для каждого i ≠ j хотя бы одно из ребер (i, j) и (j, i) находится в вашем графе. Поскольку у вас есть только граф смежности, это означает, что вам придется в какой-то момент посетить хотя бы один из (i, j) или (j, i) для каждого i ≠ j. Нет другого способа гарантировать полноту. Для проверки потребуется n (n + 1) / 2 = O (n ² ) шагов.

Answer 3

Редактировать: пропущена часть, где график был завершен.

Если M - это ваша матрица смежности, Mt - это транспонированная матрица, ~M - это матрица со всеми инвертированными «битами», а A^B - это бит xor побитово между двумя матрицами. 1007 *

Тогда матрица турнирная, если:

~(M^Mt) = I