Дан граф
, тогда дополненным графом графа
называется граф
, в котором
,
,
множество ребер полного графа на вершинах
. Нужно осуществить
(поиск в глубину) на графе
, зная граф
,
.
Проблема в том, что
порядка
, тогда
порядка
. Поэтому явно найти ребра
нельзя. Но для любых двух вершин
можно за
узнать есть между ними ребро или нет, например положив ребра в
. Теперь можно осуществить поиск в глубину следующим образом. Начинаем с некоторой вершины, например 1, остальные помечаем как не посещенные. Пусть мы щас находимся в вершине
. Просматриваем не посещенные вершины, если есть ребро из текущей вершины в
(т.е. в графе
нет такого ребра) тогда переходим в текущую, если нет, то пропускаем.
Этот алгоритм осуществляет поиск в глубину. Но я не вижу способа как его реализовать быстрее чем
, где
- количество вершин, в которые можно попасть из стартовой в графе
. Вроде бы можно с таким порядком
. Не могу придумать как. Гугление ничего не дало.
Скажите как можно это сделать или где об этом можно почитать.