Как найти клики формула

Напомним, что клика
– это максимальный по включению вершин
полный подграф графа. В оптимизационной
форме задача о клике выглядит следующим
образом:

Дан граф G = (V, E).
Необходимо найти наибольшую клику графа
(клику графа с наибольшим для этого
графа числом вершин).

Используем обозначение
ϕ(G) – размер наибольшей клики в графе G.
Тогда задачу о клики можно переформулировать
в форме распознавания следующим образом:

Дан граф G = (V, E) и целое
число b > 0. Правда ли, что ϕ(G) ≥ b.

То есть необходимо
ответить на вопрос, существует ли в
графе в графе G полный подграф с b
вершинами.

Докажем N P -полноту
задачи о клике, сведя к ней известную
нам N P – полную задачу о выполнимости.

ВЫПОЛНИМОСТЬ ∝
КЛИКА.

Покажем, что задача
о выполнимости сводится за полиномиальное
время к задаче о клике.

Пусть нам поставлена
следующая задача о выполнимости: дана
конъюнктивная нормальная форма A = D1 ∧
D2 ∧
… ∧
Dk, где Di – дизъюнкт, i = 1, k. Построим
граф G = (V, E) следующим образом:
V (G) = {(α, i) | α – литерал в Di}, E(G) = {((α,
i), (β, j)) | i /= j, α /= β}.

1)Пусть A выполнима.
Значит на определенном наборе значений
переменных A = 1. Тогда в каждом дизъюнкте
Di найдется хотя бы один литерал αi = 1.
Рассмотрим вершины (αi, i) и (αj , j) при
i /= j. Поскольку на выбранном наборе
значений переменных αi = 1 и αj = 1, то αi /=
αj . Следовательно, вершины (αi, i) и (αj ,
j) соединены ребром в графе G. Таким
образом, множество вершин {(αi, i) | i = 1, k}
порождает полный подграф в графе G.

2) Пусть теперь в графе
G есть клика размера k с вершинами (α1,
1), (α2, 2), …(αk, k). Тогда αi /= αj , ∀i,
j = 1, k. Следовательно, можно таким
образом подобрать значения переменных,
чтобы все αi принимали значение 1
одновременно. Следовательно, A – выполнима.

Итак, мы показали, что
формула A является выполнимой тогда и
только тогда, когда в графе G имеется
клика размера k.

Осталось заметить,
что построение графа G можно выполнить
за полиномиальное время от размера
СКНФ A.

Переформулированная
в форме распознавания задача о клике
принадлежит классу NP , так как, если
ответ на задачу “да” и нам дано
множество вершин, образующих полный
подграф в графе G, мы можем за полиномиальное
время проверить, правда ли каждая из
этих вершин смежная с каждой. Задача о
клике является NP – полной
задачей.

1. Алгоритмы поиска клики

Поскольку задача о
клике является NP – полной
задачей, эффективного алгоритма поиска
Клики, скорее всего, нет. По крайней
мере, пока не доказано, что P=NP.
Однако всегда можно перебрать все
подмножества размера k
во множестве вершин V и
проверить, есть ли среди них клика. Для
этого потребуется Ω(k^2*сочетания
из V
по k)
действий (V
– число вершин в графе). При любом
фиксированном k
эта величина полиноминально зависит
от размера графа G.
Однако в общей постановке задачи k
может быть любым числом, не превосходящим
|V|,
и алгоритм не является полиноминальным.

Алгоритм
Брона – Кербоша.

Одним из самых быстрых
алгоритмов поиска клики был признан
алгоритм Брона – Кербоша. Разработанный
голландскими математиками Броном и
Кербошем в 1973 году.

Алгоритм использует
тот факт, что всякая клика в графе
является его максимальным по включению
полным подграфом. Начиная с одиночной
вершины (образующей полный подграф),
алгоритм на каждом шаге пытается
увеличить уже построенный полный
подграф, добавляя в него вершины из
множества кандидатов. Высокая скорость
обеспечивается отсечением при переборе
вариантов, которые заведомо не приведут
к построению клики, для чего используется
дополнительное множество, в которое
помещаются вершины, которые уже были
использованы для увеличения полного
подграфа.

Алгоритм оперирует
тремя множествами вершин графа:

Множество compsub —
множество, содержащее на каждом шаге
рекурсии полный подграф для данного
шага. Строится рекурсивно.

Множество candidates —
множество вершин, которые могут увеличить
compsub

Множество not — множество
вершин, которые уже использовались для
расширения compsub на предыдущих шагах
алгоритма.

Алгоритм является
рекурсивной процедурой, применяемой к
этим трем множествам.

ПРОЦЕДУРА extend
(candidates, not):

1 ПОКА candidates НЕ пусто
И not НЕ содержит вершины, СОЕДИНЕННОЙ
СО ВСЕМИ вершинами из candidates, ВЫПОЛНЯТЬ:

2 Выбираем вершину v
из candidates и добавляем ее в compsub

3 Формируем new_candidates
и new_not, удаляя из candidates и not вершины, не
СОЕДИНЕННЫЕ с v

4 ЕСЛИ
new_candidates и new_not пусты

5 ТО
compsub – клика

6 ИНАЧЕ
рекурсивно вызываем
extend (new_candidates, new_not)

7 Удаляем v из compsub и
candidates, и помещаем в not

Вычислительная
сложность линейна относительно количества
клик в графе. В
работе ученых Стэндфордского университета
«The
worst-case
time
complexity
for
generating
all
maximal
cliques
and
computational
experiments»
(Худшая по времени сложность для
вычисления максимальных кликов и
вычислительные эксперименты) было
показано, что в
худшем случае алгоритм работает
за O(3^n/3),
где n — количество вершин в графе.

Список
использованной литературы.

Соседние файлы в предмете Дискретная математика

• #
• #
• #
• #
• #
• #

Алгоритм грубой силы находит 4-клику в 7-вершинном графе (дополнение 7 -vertex граф путей ) систематической проверки всех C (7,4) = 35 4-вершинных подграфов на полноту.

В информатике задача клики – это вычислительная задача поиска клик (подмножества вершин, все смежные друг с другом, также называемые полные подграфы ) в графе. Он имеет несколько различных формулировок в зависимости от того, какие клики и какую информацию о них следует искать. Общие формулировки проблемы клики включают поиск максимальной клики (клики с максимально возможным дополнительным вершин), поиск клики максимального веса в взвешенном графе, перечисление всех максимальных клик (клики, которые не могут быть увеличены), и решение задачи принятия решения проверки того, содержит ли граф клику, превышающую заданный размер.

Проблема с кликами возникает в следующих реальных условиях. Рассмотрим социальную сеть, где вершины графа представить людей, а ребра графа представить собой общих знакомых. Затем клика представляет собой подмножество людей, которые знают друг друга. Наряду с мобильными телефонами проблема также имеет множество приложений в биоинформатике и вычислительной химии.

. Большинство версий проблемы клики сложны. Проблема решения клики – это НП-полная (одна из 21 НП-полная проблема Карпа ). Проблема поиска максимального клики является как трудноразрешимым с фиксированным параметром, так и трудно аппроксимировать. Кроме перечисления всех максимальных клик может потребовать экспоненциального времени, поскольку существуют графы с экспоненциально большим количеством максимальных клик. Следовательно, большая часть теории клики посвящена определенным проблемам типов графов, которые допускают более эффективные алгоритмы, или установлению вычислительной сложности проблемы общей сложности в различных моделях вычислений.

Чтобы найти максимальную клику, можно систематически проверять все подмножества, но такой вид перебора слишком трудоемок, чтобы быть практичным для сетей, более нескольких десятков вершин.. Хотя для этой проблемы известен алгоритм с полиномиальным временем, известны более эффективные алгоритмы , чем поиск методом перебора. Например, алгоритм Брона – Кербоша можно использовать для перечисления всех максимальных клик в наихудшее оптимальное время, а также можно перечислить их за полиномиальное время для каждой клики.

Содержание

• 1 и приложения
• 2 Определения
• 3 Алгоритмы
  • 3.1 Поиск единственной максимальной истории клики
  • 3.2 Клики фиксированного размера
  • 3.3 Список всех максимальных клик
  • 3.4 Нахождение максимальных клик в произвольных графах
  • 3.5 Специальные классы графов
  • 3.6 Алгоритмы аппроксимации
• 4 Нижние оценки
  • 4.1 NP-полнота
  • 4.2 Сложность схемы
  • 4.3 Сложность дерева решений
  • 4.4 Сложность с фиксированными регулируется
  • 4.5 Твердость приближения
• 5 Примечания
• 6 Ссылки
  • 6.1 Обзоры и учебники
  • 6.2 Популярная пресса
  • 6.3 Исследовательские статьи

История и применение

Изучение полных подграфов в математике предшествовало терминологии «клика». Например, полные подграфы появились в математической литературе в теоретико-графической переформулировке теории Рамсея, выполненной Erds Szekeres (1935). Но термин «клика» и проблема алгоритмического перечисления клик пришли из социальных наук, где полные подграфы используются для моделирования социальных клик, групп людей, которые все знают друг друга. Люс и Перри (1949) использовали графы для моделирования социальных сетей и адаптировали терминологию социальных наук к теории графов. Они первыми назвали полные подграфы «кликами». Первым алгоритмом решения проблемы клики является алгоритмом Harary Ross (1957), который руководствовался социологическим приложением. Исследователи социальных наук также определили различные типы клик и максимальных клик в социальных сетях, «сплоченные подгруппы» людей или субъектов в сети, все из разных видов взаимосвязи. Многие из этих обобщенных понятий клик также можно, построив неориентированный граф, ребра которого включают связанные пары акторов из социальной сети, а применив алгоритм для проблемы клик к этому графу.

Работа Глобальной системы, многие другие разработали алгоритмы различных версий проблемы клики. В 1970-х годах исследователи начали изучать эти алгоритмы с точки зрения анализа наихудшего случая. См. Например, Tarjan Trojanowski (1977), ранняя работа по наихудшему случаю сложности задачи о максимальной клике. Также в 1970-х годах, начиная с работ Кука (1971) и Карпа (1972), исследователи начали использовать теорию НП-полноты и изучены с ней неразрешимости. результаты, чтобы дать математическое объяснение воспринимаемой сложности проблемы клики. В 1990-х годах была опубликована серия революционных статей, начинающаяся с Feige et al. (1991) и описанные в The New York Times показали, что (при условии P ≠ NP ) невозможно даже точно приблизительно определить проблему. и качественно.

Алгоритмы поиска кликовались в химии для поиска химических веществ, которые соответствуют структуре, и для моделирования стыковки молекул и сайтов связывания химических факторов. Их также можно использовать для поиска похожих структур в разных молекулах. В приложении этих приложений формируется граф, каждая вершина которого представляет собой согласованные пару элементов, по одному от каждой из двух молекул. Две вершины соединяются ребром, если совпадения, они соответствуют, совпадают друг с другом. Совместимость может означать, например, расстояние между атомами в двух молекулах равны с точностью до некоторого заданного допуска. Клика на этом графике представляет собой набор совпадающих пар элементов, в которых все совпадения совпадают друг с другом. Частным случаем этого метода является использование модульного произведения графов для проблем поиска предельного общего общего подграфа двух графов к задаче поиска максимального клики в их продукт.

В автоматической генерации тестовой таблицы поиск кликов может помочь ограничить размер тестового набора. В биоинформатике алгоритмы поиска кликов использовались для вывода эволюционных деревьев, предсказания белковых структур и поиска связующих кластеров белков. Список клик в графе зависимостей – важный шаг в аналитических случайных процессах. Вике гипотеза Келлера о прямом разбиении гиперкубов была опровергнута Lagarias Shor (1992), которые использовали алгоритм поиска кликов на соответствующий граф, чтобы найти контрпример.

Определения

Показанный граф имеет одну максимальную клику, треугольник {1,2,5}, и еще четыре максимальных клики, пары {2,3}, {3,4}, {4,5} и {4,6}.

неориентированный граф образован конечным набором из вершин и набор неупорядоченных пар вершин, которые называются ребрами. По соглашению, при анализе алгоритмов количество вершин в графе обозначается n, а количество ребер обозначается m. Клика в графе G является полным подграфом графа G. То есть это подмножество K вершин, для каждые две вершины в K являются две конечные точки ребра которых в G. Максимальная клика – это клика, к которой больше нельзя добавить вершины. Для каждой вершины v, которая предотвращает добавление v к клике, должна быть другая вершина w, которая находится в клике и не является максимальной кликой. Максимальная клика – это клика, которая включает в себя возможное возможное количество вершин. Число кликов ω (G) – это количество вершин в максимальной клике изученной группы G.

Былоено несколько совместных задач поиска клик.

• В задаче максимального клики входом является неориентированный график, а на максимальном – максимальный клика на графике. Если имеется несколько максимальных клик, одна из них может быть выбрана произвольно.
• В задаче взвешенной максимальной клики входом является неориентированный граф с весами на его вершинах (или, реже, ребрами), а на выходе это клика с максимальным общим весом. Задача максимальной клики – это частный случай, когда все веса равны. Наряду с проблемой оптимизации суммы весов были изучены и более сложные задачи бикритериальной оптимизации.
• В задаче о максимальном листинге клик вход является неориентированным графом, выходом – список все его максимальные клики. Задача максимального клика может быть решена с использованием в качестве подпрограммы алгоритма для задачи максимального клики, максимальная клика должна быть включена среди всех максимальных клик.
• В задаче k-клик входом является неориентированный граф и число k. Результатом является потеря с k-клика, если она существует, или специальное значение, указывающее, что в противном случае k-клика отсутствует. В некоторых вариантах этой задачи на выходе должны быть все клики размера k.
• В задаче принятия решений о кликах входом является неориентированный граф и число k, а на выходе – логическое значение : true, если граф содержит k-клику, и false в случае.

Первые четыре из этих проблем важны для практических приложений. Проблема решения клики не имеет практического значения; она сформулирована таким образом, чтобы применить теорию НП-полноты к задачам поиска кликов.

Проблема независимого множества друг от друга дополняет друг: клика в G независимым множеством дополнительным графе группы G и наоборот. Следовательно, многие результаты вычислений могут быть одинаково хорошо применены к любой проблеме, а в некоторых исследовательских работах не проводится четкого различия между двумя проблемами. Однако две проблемы имеют разные свойства при применении к ограниченным семействам графов. Например, проблема может быть решена за полиномиальное время для планарных графов, в то время как проблема остается сложной NP-сложной для плоских графов.

Алгоритмы

Нахождение единственного максимального клика

A максимальное клика, иногда называемая максимальной по включению, – это клика, не входящая в большую клику. Следовательно, каждая клика содержит в максимальной клике. Максимальные клики могут быть очень маленькими. Граф может содержать немальную клику с множеством вершин и отдельную клику размера 2, которая является максимальной. Хотя максимальная (т. Е. На наибольшая) клика обязательно максимальна, обратное неверно. Есть несколько типов графов, в максимальной максимальной клика максимальна; это дополнения к хорошо покрытым графам, в которых каждый максимальный набор максимален. Однако другие графы имеют максимальные клики, которые не являются максимальными.

Единственная максимальная скорость может быть найдена с помощью простого клика жадного алгоритма. Начиная с произвольной клики (например, любую отдельную вершину или даже пустого множества), увеличивайте текущую клику по одной вершине за раз, перебирая оставшиеся вершины графа. Для вершины v, которая исследует этот цикл, добавляет v к каждой вершине, если она уже находится в клике, и отбросьте v в случае. Этот алгоритм работает за линейное время. Из-за простоты поиска максимальных клик и их самого небольшого размера больше внимания было уделено гораздо более сложной алгоритмической проблемы поиска максимальной или иной большой клики, чем проблема поиска одной максимальной клики. Однако в некоторых исследованиях параллельных алгоритмов изучалась проблема поиска максимальной клики. В частности, проблема поиска лексикографически первой максимальной клики (найденной с помощью алгоритма выше) оказалась полной для класса функций с полиномиальным временем. Этот результат означает, что проблема вряд ли будет разрешима в рамках параллельного класса сложности NC.

Клики фиксированного размера

Можно проверить, содержит ли граф G клику с k вершинами, и найти любую такую ​​клику, которая содержит, используя алгоритм грубой силы. Этот алгоритм исследует каждый подграф с k вершинами и проверяет, образует ли он клику. Это занимает время O (n k), что выражается с помощью нотации большого O. Это потому, что нужно проверить O (n) подграфов, каждый из которых имеет O (k) ребер, наличие которых в G необходимо проверить. Таким образом, проблема может быть решена за полиномиальное время всякий раз, когда k является фиксированной константой. Однако, когда k не имеет фиксированного значения, но вместо этого может изменяться как часть входных данных для задачи, время является экспоненциальным.

Простейший нетривиальный случай поиска клики – это поиск треугольника в графике или, что то же самое, определение, является ли график без треугольников. В графе G с m ребрами может быть более (m) треугольников (с использованием большой тета-записи не, чтобы указать, что эта граница жесткая). Худший случай для этой формулы имеет место, когда G сама является кликой. Следовательно, алгоритмы для перечисления всех треугольников должны занимать по крайней мере Ω (м) время в худшем случае (с использованием нотации большого омеги ), и известны алгоритмы, которые соответствуют этой временной границе. Например, Chiba Nishizeki (1985) описывают алгоритм, который сортирует вершины в порядке наивысшей степени к наименьшей, а затем выполняет итерацию по каждой вершине v в отсортированном списке, ища треугольники, которые включают v и не включают включить любую предыдущую вершину в список. Для этого алгоритма помечает всех соседей v, просматривает все ребра, инцидентные соседние v, выводя треугольник для каждого ребра, имеющего две конечные точки, удаляет метки и удаляет v из графа. Как показывают авторы, время для этого алгоритма пропорционально графа (обозначается a (G), умноженной на количество ребер, которое равно O (m a (G)). Древовидность древовидность не превосходит O (m), этот алгоритм работает за время O (m). В более общем смысле, все клики с k вершинами могут быть с помощью одного алгоритма, который требует времени, умноженному количеству ребер, умноженному на древовидность в степени (k – 2). Для графов с постоянной древовидностью, таких как планарные графы (или вообще графы из любого нетривиального семейства второстепенных замкнутых графов ) этот алгоритм занимает время O (m), что является оптимальным, поскольку он линейен по размеру входных данных.

Если нужен только один треугольник или гарантия, что график не содержит треугольников, возможны более быстрые алгоритмы. Как отмечают Itai Rodeh (1978), граф содержит треугольник тогда и только тогда, когда его матрица взаимосвязей и квадратные матрицы, содержащие ненулевые элементы в одной и той же ячейке. Следовательно, методы быстрого матричного умножения, такие как алгоритм Копперсмита – Винограда, могут правила для поиска треугольников за время O (n). Алон, Юстер и Цвик (1994) использовали быстрое матричное умножение для улучшения алгоритма O (m) для поиска треугольников до O (m). Эти алгоритмы, основанные на быстром умножении матриц, также были расширены для поиска задач k-клик для больших значений k.

Список всех максимальных клик

По результатам Moon Moser (1965), каждый граф с n вершинами имеет не более 3 максимальных клик. Их можно перечислить с помощью ма Брона – Кербоша, рекурсивной процедуры обратного алгоритма из Bron Kerbosch (1973). Основная рекурсивная подпрограмма этой имеет три аргумента: частично построенную (не максимальную) клику, набор вершин процедур кандидатов, которые добавлены в клику, и другой набор вершин, которые не следует добавлять (потому что это приведет к в уже найденную клику). Алгоритм пытается добавить вершины-кандидаты одну за другой в частичную клику, выполняя рекурсивный вызов для каждой из них. После проверки каждой из этих вершин он перемещает ее в набор вершин, которые больше не нужно сообщений. Можно показать, что варианты этого алгоритма имеют время работы O (3) в наихудшем случае, количеству кликов, которые, возможно, потребуется указать. Следовательно, это обеспечивает наихудшее оптимальное решение проблемы перечисления всех максимальных клик. Кроме того, широко сообщалось, что алгоритм Брон-Кербоша на практике работает быстрее, чем его альтернативы.

Однако, когда количество клик значительно меньше, чем в худшем случае, другие алгоритмы могут быть предпочтительнее. Как Tsukiyama et al. (1977) показал, что также можно перечислить все максимальные клики в графе за время, полиномиальное на сгенерированную клику. Такой алгоритм, как их, в котором время работы зависит от размера вывода, известен как алгоритм, чувствительный к выводу. Их алгоритм основан на следующих двух наблюдениях, связывающих максимальные клики данного графа G с максимальными кликами графа G v, образованными удалением произвольной вершины v из G:

• Для каждой максимальной клики K графа G v, либо K продолжает образовывать максимальную клику в G, либо K ⋃ {v} образует максимальную клику в G. Следовательно, G имеет по крайней мере столько же максимальных клик, сколько G v.
• Каждая максимальная клика клика в G, не содержащая v, является максимальной кликой в ​​G v, и каждая максимальная клика в G, которая действительно содержит v, может быть образована из максимальной клики K в G v путем добавления v и удаления несоседей v из K.

Используя эти наблюдения, они могут сгенерировать все максимальные клики в G с помощью рекурсивного алгоритма, который выбирает вершину v произвольно, а затем для каждой максимальной клики K в G v выводит как K, так и клику, образованную добавлением v к K и удалив не соседей v. Однако некоторые кл ики G могут быть сгенерированы таким образом из более чем одной родительской клики G v, поэтому они удаляют дубликаты, выводя клику в G только тогда, когда ее родительский элемент в G v лексикографически максимален среди всех возможных родительских клик. На основе этого принципа они показывают, что все максимальные клики в G могут быть сгенерированы за время O (mn) для каждой клики, где m – количество ребер в G, а n – количество вершин. Chiba Nishizeki (1985) улучшают это до O (ma) на клику, где a – древовидность данного графа. Макино и Уно (2004) предлагают альтернативный алгоритм, чувствительный к выходу, основанный на быстром умножении матриц. Johnson Yannakakis (1988) показывают, что можно даже перечислить все максимальные клики в лексикографическом порядке с полиномиальной задержкой на клику. Однако выбор порядка важен для эффективности этого алгоритма: для обратного этого порядка не существует алгоритма с полиномиальной задержкой, если P = NP.

На основе этого результата можно перечислите все максимальные клики за полиномиальное время для семейств графов, в которых количество клик полиномиально ограничено. Эти семейства включают хордовые графы, полные графы, графы без треугольников, интервальные графы, графы ограниченной прямоугольности <248.>и планарные графы. В частности, планарные графы имеют O (n) клик не более постоянного размера, которые могут быть перечислены за линейное время. То же самое верно для любого семейства графов, которое является как разреженным, (имеющимколичество ребер, не превышающее константу, умноженную на количество вершин), так и закрытым при операции взятия подграфов.

Нахождение максимальных клик в произвольных графах

Можно найти максимальную клику или кликовое число произвольного n-вершинного графа за время O (3) = O (1.4422) используя один из вышеупомянутых алгоритмов, чтобы перечислить все максимальные клики в графе и вернуть самую большую. Однако для этого варианта проблемы клики возможны лучшие временные рамки для наихудшего случая. Алгоритм Tarjan Trojanowski (1977) решает эту проблему за время O (2) = O (1.2599). Это рекурсивная схема вызова обратного вызова, аналогичная схема алгоритма Брона – Кербоша, но можно исключить некоторые рекурсивные, когда можно показать, что клики, обнаруженные в вызове, будут неоптимальными. Цзянь (1986) улучшил время до O (2) = O (1,2346), а Робсон (1986) улучшил его до O (2) = O (1,2108), при счет большего использования пространства. Алгоритм Робсона сочетает в себе аналогичную схему поиска с возвратом (с более сложным анализом случаев) и технику >, в которой оптимальное решение вычисляется для всех малых связанных подграфов дополнительного графа. Эти частичные решения используются для сокращения рекурсии с возвратом. Самый быстрый алгоритм, известный сегодня – это усовершенствованная версия этого метода, разработанная Робсоном (2001), который работает за O (2) = O (1.1888).

Также были проведены обширные исследования эвристические алгоритмы для решения проблем с максимальным числом кликов без выполнения наихудшего случая, основанные на таких методах, как ветвление и граница, локальный поиск, жадные алгоритмы и программирование в ограничениях. Нестандартные вычислительные методологии, которые были предложены для поиска клик, включают ДНК-вычисление и адиабатическое квантовое вычисление. Проблема максимальной клики была предметом задачи реализации, спонсируемой DIMACS в 1992–1993 годах, и общедоступного набора графиков, используемых в качестве эталонов для этой задачи.

Специальные классы графов

В этом графе перестановок максимальные клики соответствуют наиболее длинным убывающим подпоследовательностям (4,3,1) и (4,3,2) определяющую перестановки.

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

Совершенные графы определенным тем своимством, что их число клики равно их хроматическому этому, и что это равенство выполняется также в каждом из их индуцированных подграфов. Для идеальных графов можно найти максимальную клику за полиномиальное время, используя алгоритм, основанный на полуопределенном программировании. Однако этот метод сложный и не является комбинаторным, и для многих подклассов совершенных графов были разработаны специализированные алгоритмы поиска клик. В дополнительных графах из двудольных графов, теорема Кенига позволяет достичь максимальной клики с использованием методов сопоставления. В другом классе совершенных графов, графах перестановок, максимальная клика является самой длинной убывающей подпоследовательностью перестановки, определяющей граф, и может быть найдена с использованием алгоритмов самой длинной убывающей подпоследовательности.. И наоборот, каждый случай самой длинной проблемы может быть описан эквивалентно как проблема поиска максимальной клики в графе перестановок. Even, Pnueli Lempel (1972) предоставляет альтернативный квадратичный алгоритм для достижения клики в графах сопоставимости, более широкого класса совершенных графов, который включает графы перестановок как частный случай. В хордовых графах максимальные клики можно найти, перечислив вершины в порядке исключения и проверив клику найти добавлений каждой вершины в этом порядке.

В некоторых случаях эти алгоритмы могут быть расширены и другие несовершенные классы графов. Например, в круговом графе добавление каждой вершины является графом перестановок, поэтому максимальную клику в круговом графе можно найти, применяя алгоритм графа перестановок к каждой окрестности. Аналогично, в единичном дисковом графе (с геометрическим представлением) алгоритм с полиномиальным временем для максимальных клик, основанный на применении алгоритма дополнений двудольных графов к общим группам пар вершин.

Алгоритмическая проблема поиска максимальной клики в случайном графе, взятом из модели Эрдеша – Реньи (в которой каждое ребро проявляется с вероятностью 1/2, независимо от других краев) был предложен Карпом (1976). Максимальный клика в случайном графе имеет максимальный размер с высокой вероятностью, ее можно найти путем перебора в ожидаемое время 2. Это квазиполиномиальная временная граница. Хотя число кликов таких графов обычно очень близко к 2 log 2 n, простые жадные алгоритмы, а также более сложные методы рандомизированной аппроксимации находят только клики с размером log 2. сущ., Вдвое меньше. Количество максимальных клик в таких графах с высокой вероятностью экспоненциально в logn, что не позволяет методам, перечисляющим все максимальные клики, работать за полиномиальное время. Из-за этой проблемы несколько авторов исследовали проблему установленной клики, проблему клики на случайных графах, которые были увеличены за счет добавления больших клик. В то время как спектральные методы и полуопределенное программирование могут обнаруживать скрытые клики размера Ω (√n), в настоящее время не известны алгоритмы полиномиального времени для обнаружения клик размера o (√n) ( выраженные с помощью небольшой нотации ).

Алгоритмы аппроксимации

Несколько авторов рассмотрели алгоритмы который аппроксимации, которые пытаются найти клику или независимый набор, хотя и не максимальным, имеет размер как Можно ближе максимума, которая не имеет смысла для дополнительных кликов, также есть работа над алгоритмами приближения, которые не используют такие предположения разреженности.

Feige (2004) имеет алгоритм полиномиального времени, который находит клику размера Ω ((log n / log log n)) в любом графе, который имеет номер клики Ω (n / logn) для любого константа k. Используя этот алгоритм, когда кликовое число заданного входного графа находится между n / log n и n / logn, sw желая использовать другой алгоритм Boppana Halldórsson (1992) для графов с более высокими номерами кликов, и выбирая клику с двумя вершинами, если оба алгоритма ничего не находят, Фейдж обеспечивает приближение алгоритма, который находит клику с числом вершин в пределах множителя O (n (log log n) / logn) от максимума. Хотя коэффициент приближения этого алгоритма слабым, на сегодняшний день он является наиболее известным. Результаты по жесткости приближения, описанные ниже, предполагают, что не может быть никакого алгоритма аппроксимации с коэффициентом аппроксимации, значительно меньшим, чем линейный.

Нижние границы

NP-полнота

Экземпляр удовлетворяемости 3-CNF (x ∨ x ∨ y) ∧ (~ x ∨ ~ y ∨ ~ y) ∧ (~ x ∨ y ∨ y) сводится к Clique. Зеленые вершины образуют 3-клику и соответствуют удовлетворительному назначению.

Проблема решения клики: НП-полная. Это была одна из оригинальной 21 задачи Ричарда Карпа, показанной NP-полной в его статье 1972 года «Сводимость среди комбинаторных проблем». Эта проблема также упоминалась в статье Стивена Кука, вводящей теорию NP-полных задач. Из-за сложности решения проблема поиска максимальной клики также является сложной NP-сложной. Если бы можно было ее решить, можно было бы решить проблему Решение, сравнивая размер максимального клика с параметром размера, заданным в качестве входных данных в задаче решения.

Доказательство NP-полноты Карпа является редукцией из булевой задачи выполнимости. В нем описывается, как преобразовать булевы формулы в конъюнктивной нормальной форме (CNF) в эквивалентные примеры максимальной клики. Выполнимость, в свою очередь, была доказана NP-полная в теореме Кука – Левина. Из заданной формулы CNF Карп формирует граф, у которого есть вершина для каждой пары (v, c), где v – переменная или ее отрицание, а c – часть формулы, содержащая v. Две из этих вершин соединены ребро, если они содержат совместимые присвоения количество для разных предложений. То есть, есть ребро от (v, c) до (u, d), когда c ≠ d и u и v не имеют отрицаний друг друга. Если k обозначает количество пунктов в формуле CNF, то клики с k вершинами в этом графе обеспечивают последовательные способы присвоения значений истинности некоторые из его числа, чтобы удовлетворить формулу. Следовательно, формула выполнима тогда и только тогда, когда существует k-вершинная клика.

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

Сложность схемы

наличие Монотонная схема для обнаружения k-клики в графе с n вершинами для k = 3 и n = 4. Каждый вход в схему кодирует или отсутствие определенного (красного) ребра в графе. Схема использует один внутренний логический элемент и обнаружение каждой потенциальной k-клики.

Вычислительная сложность этой задачи клики к привела, что ее использовали для нескольких нижних границ в схемы. Существование клики данного размера – это означает, что она будет существовать в любом суперграфе. Чтобы решить проблему принятия решений о клике для данного фиксированного размера клики, это свойство является существующим существующим монотонным механизмом, использующим только элементы и элементы и или элементы. Однако можно доказать, что размер этой схематической суперполиномиальной функции количества вершин и размера клики, экспоненциальной от кубического корня из числа вершин. Даже если разрешено небольшое количество элементов НЕ, сложность остается суперполиномиальной. Кроме того, используется глубина монотонной схемы для задач клики, использующая вентиль с ограниченным разветвлением на входе, должна быть по крайней мере полиномом от размера клики.

Сложность дерева решений

Простое дерево решений для обнаружения наличия 3-клики в 4-вершинном графе. В нем используется до 6 вопросов типа «Существует ли красный край?», Соответствующих оптимальной границе n (n – 1) / 2.

(детерминированная) сложность дерева решений определения свойство графа – это количество вопросов вида «Есть ли ребро между вершиной u и вершиной v?» на которые нужно ответить в худшем случае, чтобы определить, обладает ли граф определенным свойством. То есть это минимальная высота логического дерева решений для проблемы. Можно задать n (n – 1) / 2 возможных вопроса. Следовательно, любое свойство графа может быть определено с помощью не более n (n – 1) / 2 вопросов. Также можно определить сложность случайного и квантового дерева решений свойства, ожидаемое количество вопросов (для входных данных наихудшего случая), на которые должен ответить рандомизированный или квантовый алгоритм, чтобы правильно определить, имеет ли данный граф свойство.

Поскольку свойство содержать клику является монотонным, оно покрывается гипотезой Андераа – Карпа – Розенберга, которая утверждает, что сложность детерминированного дерева решений для определения любого нетривиального монотонного Свойство графа равно n (n – 1) / 2. Для произвольных свойств монотонного графа эта гипотеза остается недоказанной. Однако для детерминированных деревьев решений и для любого k в диапазоне 2 ≤ k ≤ n было показано, что свойство содержать k-клику имеет сложность дерева решений ровно n (n – 1) / 2 Боллобасом ( 1976). Детерминированные деревья решений также требуют экспоненциального размера для обнаружения клик или большого полиномиального размера для обнаружения клик ограниченного размера.

Гипотеза Андераа – Карпа – Розенберга также утверждает, что сложность рандомизированного дерева решений нетривиальных монотонных функций равна Θ (п). Гипотеза снова остается недоказанной, но была разрешена для свойства содержать k клику при 2 ≤ k ≤ n. Известно, что это свойство имеет рандомизированную сложность дерева решений Θ (n). Для квантовых деревьев решений наиболее известной нижней границей является Ω (n), но для случая k ≥ 3 не известен алгоритм сопоставления.

Сложность с фиксированным параметром

Параметризованная сложность – это Теоретическая сложность исследование задач, которые естественным образом снабжены малым целочисленным параметром k и для которых проблема становится более сложной с увеличением k, например, поиск k-клик в графах. Задача называется решаемой с фиксированными параметрами, если существует алгоритм для ее решения на входах размера n и функция f, такая, что алгоритм выполняется за время f (k) n. То есть ее можно решить с фиксированным параметром, если ее можно решить за полиномиальное время для любого фиксированного значения k и, более того, если показатель степени полинома не зависит от k.

Для поиска клик с k вершинами, алгоритм поиска методом перебора имеет время работы O (nk). Показатель степени n зависит от k, этот алгоритм не является управляемым с фиксированными параметрами. Хотя его можно улучшить с помощью быстрого умножения матриц, время выполнения по-прежнему имеет экспоненту, линейную по k.Таким образом, хотя время выполнения алгоритмов для задач клики является полиномиальным для любого фиксированного k, этих алгоритмов недостаточно для фиксированного сговорчивость. Дауни и Товарищи (1995) определили иерархию параметризованных задач, иерархию W, которая, по их предположениям, не управляемые алгоритмов с фиксированными функциями. Они доказали, что то же самое, клика сложно для первого уровня этой иерархии, W [1]. Таким образом, согласно их гипотезе, у клики нет алгоритма с фиксированными опасностями. Этот продукт служит для использования в качестве доказательства W [1] -твердости многих других способов, аналогом теоремы Кука – Левина для параметризованной сложности.

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

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

Жесткость аппроксимации

График отношений совместимости между 2-битными образцами 3-битных строк доказательства. Каждая максимальная клика (треугольник) на этом графике представляет все способы выбора одной 3-битной строки. Доказательство невозможности аппроксимации проблемы включает индуцированные подграфы аналогичным образом графов для большего числа битов.

Слабые результаты, намекающие на то, что проблема клики может быть трудно аппроксимировать, были известны давно. Garey Johnson (1978) заметили, что из-за того, что кликовое число принимает малые целые значения и NP-сложно вычислить, оно не может иметь полностью схему аппроксимации с полиномиальным временем. Если бы было слишком точное число приближение, округление его значения до целого числа дало бы точное число клики. Однако мало что было известно до начала 1990-х годов, когда несколько авторов начали устанавливать связь между приближением максимальных клик и вероятностно проверяемых доказательств. Они использовали эти связи, чтобы доказать трудность аппроксимации результатов для задачи о максимальной клике. После многих улучшений этих результатов теперь известно, что для каждого действительного числа ε>0 не может быть алгоритма полиномиального времени, который аппроксимирует максимальную клику с точностью до множителя лучше, чем O (n), если только P = NP.

Грубая идея этих результатов несовместимости в том, чтобы сформировать граф, представляющий систему вероятностно проверяемых доказательств для NP-полной проблемы, такая как проблема логической выполнимости. В вероятностно проверяемой системе доказательств доказательства битов. Экземпляр проблемы выполнимости должен иметь действительное доказательство тогда, когда оно выполнимо. Доказательство проверяет алгоритмом, который после вычислений за полиномиальное время выполнения задачи выполняет выбор для проверки небольшое количество случайно выбранных позиций доказательства. В этой выборке битов имеются значения, которые могут быть проверены, либо проверены, либо отклонены от других битов. Ложноотрицательные результаты не допускаются: всегда приниматься доказательство. Однако иногда может быть ошибочно принято недействительное доказательство. Для каждого недействительного доказательства того, что проверяющий его примет, должна быть низкой.

Чтобы преобразовать вероятностно проверяемую систему доказательств этого типа в проблеме клики, нужно сформировать граф с вершиной для каждого возможного принимающего прогона. средства проверки. То есть вершина определяется одним из проверяющих выборов наборов для проверки и битовыми значениями для тех позиций, которые заставили бы проверяющую принять доказательство. Он может быть представлен частичным словом с 0 или 1 в каждой исследуемой позиции и символом подстановки в каждой оставшейся позиции. В этом графе две вершины являются соответствующими, если соответствующие две принимающие серии видят одинаковые битовые значения в каждой позиции, которые они исследуют. Действующая или недействительная строка доказательства соответствует клике, набору принимающих прогонов, которые видят эти доказательства, и все максимальные клики проходят таким образом. Одна из этих клик велика тогда и только тогда, когда она проверяет доказательства, принимает многие средства проверки. Если будет принят все исходные доказательства, выполненные экземпляром. Однако, если исходный экземпляр не является выполненным, тогда все строки доказательства не исполняемой, каждая строка доказательства только небольшое количество запусков программы проверки, которые ошибочно принимают ее, и все клики небольшие. Следовательно, если бы можно было проводить полиномиальное различие между графами, имеющими большие клики и графами, в которых все клики малы, или если бы можно было точно аппроксимировать проблему кликов, то применение этого приближения к графам, созданным из экземпляров выполнимости, выполненным экземпляры отличать от неудовлетворительных случаев. Однако это невозможно, если P = NP.

Примечания

Ссылки

Обзоры и учебники

Популярная пресса

Исследовательские статьи

Как посчитать количество кликов

Средняя сумма, которую вы платите за клик пользователя по вашему объявлению. Она рассчитывается путем деления общей стоимости кликов на их общее количество. Средняя цена за клик вычисляется на основе фактической цены за клик (реальной суммы, которую вы заплатили за клик по объявлению).

Как рассчитать количество показов

В маркетинге рекламу с оплатой за 1000 показов принято обозначать как CPM (аббр. от Cost per mille). Калькулятор поможет рассчитать модель показов по формуле: CPM = (Стоимость размещения рекламы/Количество показов объявления) * 1000.

Как посчитать процент кликабельности

Уровень кликабельности принято считать в процентах за определенный отрезок времени либо за установленное число показов. Чтобы узнать CTR рекламы, нужно просто поделить количество кликов на количество показов рекламы в системе, а полученный результат умножить на 100.

Как сделать CTR

Как посчитать CTR

CTR рассчитывается как соотношение количества кликов к общему числу показов рекламного объявления или баннера. Данная величина измеряется в процентах. Например, сумма показов рекламы равна 1000. При этом 60 пользователей перешло на сайт.

Как считать CRT

Формула расчета: CTR = количество кликов / количество показов * 100%. Принцип действия: Это первичная метрика, демонстрирующая соотношение показов рекламного объявления и кликов на него.

Как рассчитать цену за клик

Рассчитать цену клика можно по следующей формуле:

• СРС = СРМ / (1000*CTR),
• где СРС — стоимость за клик;
• СРМ — стоимость показа;
• CTR — соотношение кликов по отношению к показам.

Чем отличается CTR от кликабельности

CTR показывает, насколько реклама интересна аудитории тех площадок, где она размещена. Показатель кликабельности полезно отслеживать, чтобы: Сэкономить.

Как высчитать процент количества

Сколько процентов составляет одно число от другого числа

Чтобы вычислить процентное отношение чисел, нужно одно число разделить на другое и умножить на 100%.

Что такое CTR и Cr

Разница между CR и CTR

CTR («click-through rate» коэффициент кликабельности) — соотношение переходов с рекламного объявления к количеству его показов. Коэффициент кликабельности можно назвать частным случаем CR. По сути CTR — это конверсия показов рекламного объявления — в клики по нему.

Какой хороший показатель CTR

Хорошим считается CTR от 4 до 9%, в среднем 5%.

Как увеличить количество кликов

Повышение качества контекстной рекламы:

• постарайтесь повысить CTR своих слов. Подбирайте только самые эффективные ключевые слова, которые будут ориентированы на максимально целевую аудиторию.
• повышайте CTR ваших объявлений.
• используйте только качественные ключевые слова.
• оставляйте историю ключевых слов.

Что такое процент кликов по показанным значкам

О чем свидетельствует процент кликов по показанным значкам и что на него влияет? Этот показатель говорит о том, в скольких процентах случаев, увидев значок, зрители переходили к просмотру видео.

Как посчитать прогноз CTR

Как посчитать CTR

CTR сайта в поисковой выдаче = (количество переходов по запросу / количество показов сайта по этому запросу) * 100.

Что такое CA CRT

Ca. crt — файл публичного сертификата ЦС.

Что такое кодировка der

DER (отличительные правила кодирования) это двоичная кодировка для X. 509 сертификаты и закрытые ключи.

Как сделать сертификат PEM

Чтобы создать сертификат, воспользуйтесь методом create для ресурса Certificate.Создание пользовательского самоподписанного сертификата:

• Выберите способ добавления Файл.
• Нажмите кнопку Выбрать файл. В открывшемся окне выберите файл самоподписанного сертификата cert. pem.
• Нажмите кнопку Добавить.

Что такое 1000 показов

CPM — оплата за тысячу показов (в интернет-рекламе). Аббревиатура происходит от лат. Cost per Millenium, что в переводе означает «цена за тысячу». Модель используется в интернет-маркетинге наряду с другими: CPC (цена за клик) и CPA (цена за совершенное действие).

Что лучше CPC или CPM

Специалисты рекомендуют использовать Cost Per Click, если компания может сформировать действительно интересный для аудитории офер, который будет активно генерировать конверсии. Если предложений слишком много и для каждого невозможно создать уникальный баннер или объявление, то лучше использовать модель Cost Per Mille.

Как рассчитать CPM формула

Формула CPM = стоимость размещения рекламы / прогноз по количеству просмотров * 1 000 показов. Рекламодателям необходимо следить за CTR — кликабельностью объявлений.

Какой CR считается хорошим

При этом хорошим показателем для компании средних размеров будет 700-1000 кликов. После этого сравнивают CR и выбирают оффер или СТА с большей конверсией. сколько посетителей за этот же период времени совершили на странице целевое действие (заказ).

Какой должен быть CTR в Таргете

CTR в 0.65-0.8% — хороший показатель для таргетированной рекламы ВК. CTR в 0.4-0.55% — средний показатель. CTR контекста должен быть в пределах 2-4%.

Что дает высокий CTR

Чем выше показатель ctr, тем ниже цену вы платите за клик, тем выше места Вы занимаете в поисковой выдаче. А при низком ctr Ваши объявления могут перестать показываться как неэффективные либо Вы будете оплачивать достаточно высокие ставки, попадая на низкие позиции.

Чем меньше CTR тем лучше

Если CTR ниже 5 %, но не меньше 2 %, то этот показатель ниже среднего. Все объявления, которые имеют менее 2 %, считаются малоэффективными. А при совсем низких показателях (менее 0,5 %) «Яндекс» и Google могут самостоятельно остановить показы. Если кликабельность, наоборот, больше 10 % — это отлично.

Что делать если низкий CTR

Есть несколько советов как увеличить CTR:

• Используйте рекламные записи с кнопкой и рекламные записи формата Карусель.
• Используйте призывы к действию в тексте и на изображениях.
• Сегментируйте аудиторию и сравните показатели CTR в разных сегментах.

Какой CTR считается хорошим в гугле

Какой CTR считается хорошим

Как из CER сделать Pfx

Как самому создать сертификат из cer

Чтобы получить pfx-файл сертификата, нужно ввести в OpenSSL команду: openssl pkcs12 -export -out domain. name. pfx -inkey domain.

Что такое PEM файл

Файл PEM — это файл сертификата безопасности, который используется для установления безопасного канала связи между веб-сервером и браузером. Он имеет кодировку Base64 и может содержать закрытый ключ, сертификат сервера и/или комбинацию других сертификатов.

Для чего нужен сертификат SSL

Использование SSL гарантирует, что данные, передаваемые между пользователями и веб-сайтами или между двумя системами, невозможно прочитать сторонним лицам или системам. SSL использует алгоритмы для шифрования передаваемых данных, что не позволяет злоумышленникам считать их при передаче через зашифрованное соединение.

Что такое цена за клик

Максимальная цена за клик — это наибольшая сумма, которую вы готовы заплатить за нажатие на объявление. Как правило, рекламодатели платят меньше. Окончательная сумма, которую вы заплатите, называется фактической ценой за клик. Стоимость нажатия никогда не превышает установленное вами значение максимальной цены за клик.

Сколько платят за 1000 показов

Если вы заработали примерно 0,15 доллара США за 25 просмотров страницы, доход за тысячу показов страницы будет составлять (0,15 / 25) * 1000, то есть 6 долларов США.

Что такое Срм в Таргете

CPM (Cost Per Mille) — это модель оплаты рекламы, при которой цена размещения рассчитывается за тысячу показов объявления.

Сколько должен быть стр

Таблица средних значений CTR

Какой должна быть цена за клик

1) Нормальная цена за клик 5-15 рублей; 2) Цена клика зависит от многих факторов: размер аудитории, качество аудитории, вашего предложения, качества картинки/видео и тд; 3) Не нужно смотреть просто на цифры! Нужно смотреть на эффективность рекламы.

Что такое CPC в рекламе

CPC (cost per click) — это цена клика, сумма, которую рекламодатель платит контекстной системе за клик по объявлению, сделанный пользователем.

Что значит цена за 1000 показов

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

Как посчитать количество показов зная CTR

CTR рассчитывается как количество кликов по объявлению, разделенное на число показов: клики ÷ показы = CTR. Например, при 5 кликах и 100 показах CTR равен 5 %. Отдельные показатели СTR рекламы, ключевых слов и бесплатно размещенной информации о товаре можно найти в аккаунте.

Как рассчитать стоимость показов

Что запомнить про CPM:

• CPM — стоимость тысячи показов рекламного объявления.
• Для модели Cost Per Mille важны показы, а не действия пользователей.
• Формула CPM = стоимость размещения рекламы / прогноз по количеству просмотров * 1 000 показов.
• Рекламодателям необходимо следить за CTR — кликабельностью объявлений.

Оставить отзыв (1)

• Как высчитать количество кликов
• Как рассчитать стоимость кликов
• Как узнать количество кликов по ссылке

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 27 ноября 2019 года; проверки требуют 5 правок.

Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.^[1]

Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера.

NP-полнота[править | править код]

NP-полнота задачи о клике следует из NP-полноты задачи о независимом множестве вершин.
Легко показать, что необходимым и достаточным условием для существования клики размера k является наличие независимого множества размера не менее k в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.

Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ».^[2]

Алгоритмы[править | править код]

Как и для других NP-полных задач, эффективного алгоритма для поиска клики заданного размера на данный момент не найдено. Полный перебор всех возможных подграфов размера k с проверкой того, является ли хотя бы один из них полным, — неэффективен, поскольку полное число таких подграфов в графе с v вершинами равно биномиальному коэффициенту

Другой алгоритм работает так: две клики размера n и m «склеиваются» в большую клику размера n+m, причём кликой размера 1 полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причём последние уже не могут быть «склеены» между собой.

Доказано, что, при условии неравенства классов P и NP, не существует полиномиального аппроксимационного алгоритма с абсолютной ошибкой равной произвольному . Рассмотрим граф и – прямое произведение графа и клики размера . Очевидно, что кликовое число графа будет равно . Предположим, что существует аппроксимационный алгоритм с абсолютной ошибкой равной . Тогда подадим на вход граф и при условии получим . Пусть – клики графов вида , где . Заметим справедливость неравенства и подставим его в вышеописанное неравенство следующим образом: . После преобразования получим , а значит, существует такое, что и, следовательно, задача о клике разрешима за полиномиальное время, что противоречит условию о неравенстве классов P и NP.

См. также[править | править код]

• Алгоритм Брона — Кербоша — быстрое нахождение всех клик

Примечания[править | править код]

Литература[править | править код]

• Cook, Stephen A. (1971). “The Complexity of Theorem-Proving Procedures”. Proceedings of the Third Annual ACM Symposium on Theory of Computing. Shaker Heights, Ohio. pp. 151–158. Архивировано из оригинала 2006-05-03. Дата обращения 2007-06-11. Архивная копия от 3 мая 2006 на Wayback Machine
• Garey, Michael R. & Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 A1.2: GT19, pg.194.

Ссылки[править | править код]

• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring