Проблема алгоритма

Question

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

В задаче k вход является неориентированным графом и числом k, а выход - размером clof k, если таковой существует (или, иногда, всем cl размера k)

Answer 1

Предположим без ограничения общности, что узлы графа идентифицируются целыми числами от 0 до N-1 (без потери общности, потому что если каждый узел должен нести другую информацию, вы можете иметь массив / вектор / список из объектов N узлов, и принять эти целые числа как индексы в рассматриваемом массиве). Связность графа может быть обозначена, например, отображением каждого узла на набор, который является непосредственными соседями узла.

Чтобы проверить соединение, а не непосредственную смежность, вам скорее понадобится другое отображение - транзитивное замыкание отображения непосредственных соседей. Конечно, есть хорошие алгоритмы для этого (см., Например, исходный код Python для пакета networkx), но грубый метод просто начнется с копирования непосредственного сопоставления смежности в сопоставление соединения, а затем итеративно расширяет наборы до одной итерации. больше не расширяет набор.

Например, пример грубой силы на Python 2.6:

import copy

def transitive_closure(immediate_neighbors):
  result = copy.deepcopy(immediate_neighbors)
  changes = True
  while changes:
    changes = False
    for node in result:
      newset = set(result[node])
      for neighbor in result[node]:
        newset.update(result[neighbor])
      if newset != result[node]:
        changes = True
        result[node] = newset
  return result

immediate = {0:[1,2], 1:[0], 2:[0], 3:[4], 4:[3]}
connections = transitive_closure(immediate)
for node in sorted(connections):
  print node, sorted(connections[node])

печатает:

0 [0, 1, 2]
1 [0, 1, 2]
2 [0, 1, 2]
3 [3, 4]
4 [3, 4]

С connections словарь под рукой, все, что нам нужно сделать, это изучить каждую комбинацию k узлы (например, в Python 2.6 или выше, itertools.combinations(range(N), k) дает нам эти комбинации): это будет клика, если это подмножество (не обязательно правильное подмножество) набора элементов, связанных с любым из его членов.

Так, например, приведенный выше код можно продолжить, чтобы показать все 2-клики:

import itertools
cliques = set()
for somenodes in itertools.combinations(range(5), 2):
  if set(somenodes) <= connections[somenodes[0]]:
    cliques.add(somenodes)
print '%d cliques:' % len(cliques)
for c in sorted(cliques): print ' ', c

который печатает, с данными, использованными в предыдущем примере:

4 cliques:
  (0, 1)
  (0, 2)
  (1, 2)
  (3, 4)

Для подходов без грубой силы я рекомендую снова изучить networkx Исходный код, на который я указал ранее.

Answer 2

Хорошо, нумеруйте вершины 1 ... n и преобразуйте граф в матрицу логической смежности - 1 в точке (i,j), что означает, что i и j связаны. В неориентированном графе матрица должна быть симметричной. Теперь ваша задача сводится к поиску "квадрата" размером k x k со всеми 1 с. "Квадрат" забавен тем, что строки и столбцы не обязательно должны быть смежными друг с другом. Чтобы получить некоторый квадрат, вы начинаете с n строк, n столбцов, удаляете (nk) строк и столбцов - и вуаля! Ты понял.

Теперь каждый уникальный квадрат всех 1 будет соответствовать клике. Чтобы проверить уникальность, представьте квадрат как неизменный кортеж ((i1,j1), (i2, j2) ... (ik,jk)) (нотация Python).

В Python вы можете добавить кортежи в неупорядоченный набор и спросить набор, содержит ли он уже элемент, который мы ищем.