Алгоритм Брона Кербоша для поиска клики - что происходит, когда опорная вершина не существует?

Псевдокод википедии по поиску клики BK с поворотом:

   BronKerbosch2(R,P,X):
   if P and X are both empty:
       report R as a maximal clique
   choose a pivot vertex u in P ⋃ X
   for each vertex v in P \ N(u):
       BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
       P := P \ {v}
       X := X ⋃ {v}

Мне непонятно, что происходит с P, союз X пуст. Поскольку u не определено, продолжает ли функция N(u) как пустое множество (т. е. продолжает для каждой вершины v в P) или возвращается к вызывающей стороне?


graph algorithm clique
person jda    schedule 12.09.2011    source источник

Ответы (2)


arrow_upward
2
arrow_downward

P-объединение X пусто тогда и только тогда, когда и P, и X пусты. Это условие проверяется в строке

if P and X are both empty:

Таким образом, если это условие не выполняется, это означает, что P или X или оба не пусты. Таким образом, в P union X должен быть хотя бы один элемент.

Другими словами: если P union X пуст, мы report R as a maximal clique.

person phimuemue    schedule 12.09.2011

arrow_upward
1
arrow_downward

Неважно, что мы выберем для значения u. Ваше предположение состоит в том, что P union X пусто, что означает, что и P, и X пусты. Итак, давайте на секунду проигнорируем значение u и перейдем к следующей строке, "for each vertex v in P \ N(u):". Поскольку P пусто, то P \ N(u) все равно будет пустым. Так что цикл for будет пропущен несмотря ни на что. Так что, если вам от этого станет лучше, вы можете поместить туда оператор return, но в том виде, в каком он сейчас написан, он все равно остановит выполнение алгоритма.

person Charles G    schedule 02.07.2015