Русская Википедия:Клика (теория графов)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Значения

Файл:VR complex.svg
Граф с 23 кликами, содержащими 1 вершину (вершины графа), 42 кликами, состоящими из 2 вершин (рёбра графа), 19 кликами, состоящими из 3 вершин (закрашенные треугольники) и двумя кликами, состоящими из 4 вершин (тёмно-синие области).
Шесть рёбер не входят ни в один треугольник и 11 светло-голубых треугольников образуют максимальные клики.
Две тёмно-синие 4-клики являются как наибольшими, так и максимальными, и кликовое число графа равно 4.

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

Хотя изучение полных подграфов началось ещё с формулировки теоремы Рамсея в терминах теории графов Эрдёшем и СекерешемШаблон:Sfn[1]. Термин «клика» пришёл из работы Люка и ПериШаблон:Sfn, использовавших полные подграфы при изучении социальных сетей для моделировании клик людей, то есть групп людей, знакомых друг с другом[2]. Клики имеют много других приложений в науке, и, в частности, в биоинформатике.

Определения

Кликой в неориентированном графе <math>G = (V, E)</math> называется подмножество вершин <math>C \subseteq V</math>, такое что для любых двух вершин в <math>C</math> существует ребро, их соединяющее. Это эквивалентно утверждению, что подграф, порождённый <math>C</math>, является полным.

Максимальная клика или клика, максимальная по включению — это клика, которую нельзя расширить добавлением в неё вершин. Иначе говоря, в данном графе нет клики большего размера, в которую она входит.

Наибольшая клика или клика, максимальная по размеру — это клика максимального размера для данного графа.

Кликовое число <math>\omega(G)</math> графа <math>G</math> — это число вершин в наибольшей клике графа <math>G</math>. Число пересечений графа <math>G</math> — это наименьшее число клик, вместе покрывающих все рёбра графа <math>G</math>.

Противоположное клике понятие — это независимое множество в том смысле, что каждая клика соответствует независимому множеству в дополнительном графе. Задача Шаблон:Не переведено 5 состоит в нахождении как можно меньшего числа клик, содержащих все вершины графа.

Связанный термин — это биклика, полный двудольный подграф. Двудольная размерность графа — это минимальное число биклик, необходимых для покрытия всех рёбер графа.

Математика

Математические результаты относительно клик включают следующие.

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

  • Хордальный граф — это граф, вершины которого могут быть упорядочены в порядке совершенного исключения; порядке, при котором соседи каждой вершины <math>v</math> идут после вершины <math>v</math>.
  • Кограф — это граф, все порождённые подграфы которого имеют свойство, что любая наибольшая клика пересекается с любым наибольшим независимым множеством в единственной вершине.
  • Интервальный граф — это граф, наибольшие клики которого можно упорядочить так, что для любой вершины <math>v</math>, клики, содержащие <math>v</math>, идут последовательно.
  • Рёберный граф — это граф рёбра которого могут быть покрыты кликами без общих рёбер, притом каждая вершина будет принадлежать в точности двум кликам.
  • Совершенный граф — это граф, в котором кликовое число равно хроматическому числу в каждом порождённом подграфе.
  • Расщепляемый граф — это граф, в котором некоторый набор клик содержит по крайней мере одну вершину из каждого ребра.
  • Граф без треугольников — это граф, в котором нет других клик кроме вершин и рёбер.

Кроме того, многие другие математические построения привлекают клики графов. Среди них:

  • Шаблон:Не переведено 5 графа <math>G</math> — это Шаблон:Не переведено 5 <math>X(G)</math> с симплексом для каждой клики в <math>G</math>;
  • Шаблон:Не переведено 5 — это неориентированный граф <math>\kappa(G)</math> с вершинами для каждой клики в графе <math>G</math> и рёбрами, соединяющими две клики, отличающиеся одной вершиной. Этот граф является примером медианного графа и связан с Шаблон:Не переведено 5 на кликах графа — медиана <math>m(A, B, C)</math> трёх клик <math>A</math>, <math>B</math> и <math>C</math> — это клика, вершины которой принадлежат по крайней мере двум кликам из <math>A</math>, <math>B</math> и <math>C</math>[3];
  • Сумма по клике — это метод комбинирования двух графов путём их слияния по клике;
  • Кликовая ширина — это категория сложности графов в терминах минимального числа различных меток вершин, необходимых для построения графа из разрозненных наборов с помощью операций разметки и операций соединения всех пар вершин с одинаковыми метками. Графы с кликовой шириной единица — это в точности разрозненные наборы клик;
  • Число пересечений графа — это минимальное число клик, необходимых для покрытия всех рёбер графа.

Близкая концепция к полным подграфам — это разбиения графов на полные подграфы и полные миноры графа. В частности, Шаблон:Не переведено 5 и теорема Вагнера характеризуют планарные графы путём запрещения полных и полных двудольных подграфов и миноров, соответственно.

Информатика

Шаблон:Main В информатике задача о клике — это вычислительная задача нахождения максимальной клики или клик в заданном графе. Задача является NP-полной, одной из 21 NP-полных задач КарпаШаблон:Sfn. Она также сложна для Шаблон:Не переведено 5 и трудно аппроксимируема. Тем не менее разработано много алгоритмов для работы с кликами, работающих либо за экспоненциальное время (такие как алгоритм Брона — Кербоша), либо специализирующиеся на семействах графов, таких как планарные графы или совершенные графы, для которых задача может быть решена за полиномиальное время.

Бесплатное программное обеспечение для поиска максимальной клики

Ниже приведён список свободно распространяемого программного обеспечение для поиска максимальной клики.

Название Лицензия Язык API Короткое описание
NetworkX BSD Python приближённое решение, смотри процедуру max_cliqueШаблон:Недоступная ссылка
maxClique CRAPL Java точные алгоритмы, реализации DIMACS Шаблон:Wayback
OpenOpt BSD Python точные и приближённые решения, возможность указать рёбра, которые должны быть включены (MCP)

Применение

Много различных задач биоинформатики смоделированы с помощью клик. Например, Бен-Дор, Шамир и ЯхиниШаблон:Sfn моделировали задачу разбиения на группы экспрессии генов как задачу поиска минимального числа изменений, необходимых для преобразования графа данных в граф, сформированный несвязными наборами клик. Танай, Шаран и ШамирШаблон:Sfn обсуждают похожую задачу бикластеризации данных экспрессии генов, в которой кластеры должны быть кликами. СугихараШаблон:Sfn использовал клики для моделирования экологических ниш в пищевых цепях. Дей и СанковШаблон:Sfn описывают задачу описания эволюционных деревьев как задачу нахождения максимальных клик в графе, в котором вершины представляют характеристики, а две вершины соединены ребром, если существует Шаблон:Не переведено 5, комбинирующая эти две характеристики. Самудрала и МолтШаблон:Sfn моделировали предсказание структуры белка как задачу нахождения клик в графе, вершины которого представляют позиции частей белка, а путём поиска клик в схеме Шаблон:Не переведено 5. Спирит и Мирни Шаблон:Sfn нашли кластеры белков, которые взаимодействуют тесно друг с другом и имеют слабое взаимодействие вне кластера. Шаблон:Не переведено 5 — это метод упрощения сложных биологических систем путём нахождения клик и связанных структур в этих системах.

В электротехнике Прихар Шаблон:Sfn использовал клики для анализа коммуникационных сетей, а Паул и Унгер Шаблон:Sfn использовали их для разработки эффективных схем для вычисления частично определённых булевских функций. Клики используются также в Шаблон:Не переведено 5 — большая клика в графе несовместимости возможных дефектов даёт нижнюю границу множества тестовов[4]. Конг и Смит Шаблон:Sfn описывают применение клик для поиска иерархических структур в электрических схемах.

В химии Родес и соавторыШаблон:Sfn использовали клики для описания химических соединений в Шаблон:Не переведено 5, имеющих высокую степень похожести. Кул, Крипен и ФризенШаблон:Sfn использовали клики для моделирования позиций, в которых два химических соединения связываются друг с другом.

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Более ранние работы Казимира КуратовскогоШаблон:Sfn0 по характеризации планарных графов путём запрещения полных и полных двудольных подграфов сформулирована скорее в топологических терминах, а не в терминах теории графов
  2. ↑ О дальнейших работах в области моделирования социальных клик с помощью теории графов смотрите работы АльбыШаблон:Sfn0, Пия Шаблон:Sfn0 и Дориана с ВудардомШаблон:Sfn0
  3. ↑ Шаблон:Статья
  4. ↑ Шаблон:Статья
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Клика_(теория_графов)&oldid=10129822