Нахождение кликового покрытия графа

Допустим, есть черный ящик (/алгоритм), который дает мне клик графа. Можно ли как-то найти обложку клики оттуда?

Интуитивное представление о том, что я пытаюсь найти, дано на картинке. Я пытаюсь найти часть черного ящика. Пожалуйста, не стесняйтесь, если необходимы дополнительные разъяснения. У меня есть идея, которая обновляет граф, удаляя ребра клик. Я не знаю, насколько хорошо это сработает. Ждем любых других идей.

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


algorithm clique
person Rajat    schedule 04.08.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

http://mathworld.wolfram.com/CliqueCoveringNumber.html

Удаление ребер вам не поможет, так как в новом графе может отсутствовать клика, которая использовалась бы для решения покрытия.

    B
  / | \
A   |  D
  \ | /
    C

У вас есть 2 максимальных клики, ABC и BCD, если вы начали с ABC и удалили его ребра AB AC и BC, ваш алгоритм не смог бы найти клику BCD.

Вам понадобятся все максимальные клики графа, прежде чем вы попытаетесь вычислить число кликовых покрытий.

AllCliques = GetAllCliques()
MaximalCliques = AllCliques
For Each ckA in MaximalCliques
  For Each ckB in MaximalCliques.Excluding(ckA)
    If all vertices in ckA are in ckB Then MaximalCliques.Remove(ckA)
    If all vertices in ckB are in ckA Then MaximalCliques.Remove(ckB)
Return MaximalCliques

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

MinCover = MaximalCliques.Count
For Each ckList in Permute(MaximalCliques)
  Cover = 0
  TestSet = Graph.Vertices
  For Each ck in ckList
    TestSet.Remove(ck.Vertices)
    Cover = Cover + 1
    If TestSet.Count = 0 Then Break
  If Cover < MinCover Then MinCover = Cover
Return MinCover
person Louis Ricci    schedule 04.08.2015