Русская Википедия:Число пересечений графа
Шаблон:Не путать Число пересечений графа — наименьшее число элементов в представлении данного графа как графа пересечений конечных множеств, или, эквивалентно, наименьшее число клик, необходимых для покрытия всех рёбер графаШаблон:SfnШаблон:Sfn[1].
Графы пересечений
Пусть Шаблон:Math — Шаблон:Не переведено 5 (позволяется повторение множеств в Шаблон:Math). Тогда граф пересечений Шаблон:Math — это неориентированный граф, имеющий по вершине для каждого члена Шаблон:Math и по ребру между любыми двумя множествами, имеющими непустое пересечение. Любой граф может быть представлен как граф пересеченийШаблон:Sfn. Число пересечений графа — это наименьшее число Шаблон:Math, такое, что существует представление такого типа, для которого объединение множеств Шаблон:Math имеет Шаблон:Math элементовШаблон:Sfn. Задача нахождения представления в виде графа пересечений с заданным числом элементов известна как задача нахождения базиса графа пересеченийШаблон:Sfn.
Покрытия рёбер кликами
Альтернативное определение числа пересечений графа Шаблон:Math — это наименьшее число клик в Шаблон:Math (полных подграфов графа Шаблон:Math), которые покрывают все рёбра Шаблон:Math Шаблон:SfnШаблон:Sfn. Множество клик с таким свойством называется покрытием рёбер кликами, а потому число пересечений иногда называют числом покрытия рёбер кликамиШаблон:Sfn.
Равенство числа пересечений и числа покрытия рёбер кликами доказывается «прямолинейно». В одном направлении, предположим, что Шаблон:Math является графом пересечений семейства Шаблон:Math множеств, объединение Шаблон:Math которых имеет Шаблон:Math элементов. Тогда для любого элемента Шаблон:Math из Шаблон:Math подмножество вершин графа Шаблон:Math, соответствующих множествам, содержащим Шаблон:Math, образуют клику — любые две вершины этого подмножества смежны, поскольку их соответствующие множества имеют непустое пересечение, содержащее Шаблон:Math. Далее — любое ребро в Шаблон:Math содержится в одной из таких клик, поскольку ребро соответствует непустому пересечению, а пересечение не пусто, если оно содержит по меньшей мере один элемент Шаблон:Math. Таким образом, рёбра графа Шаблон:Math могут быть покрыты Шаблон:Math кликами, по одной для каждого элемента Шаблон:Math. В другом направлении, если граф Шаблон:Math можно покрыть Шаблон:Math кликами, то каждая вершина графа Шаблон:Math может быть представлена множеством клик, содержащих вершинуШаблон:Sfn.
Верхние границы
Очевидно, что граф с Шаблон:Math рёбрами имеет число пересечений, не превосходящее Шаблон:Math — любое ребро образует клику, и эти клики вместе покрывают все рёбраШаблон:Sfn.
Также верно, что любой граф с Шаблон:Math вершинами имеет число пересечений, не превосходящее Шаблон:Math. Более строго, рёбра любого графа с Шаблон:Math вершинами могут быть разделены максимум на Шаблон:Math клик, которые являются либо отдельными рёбрами, либо треугольникамиШаблон:SfnШаблон:Sfn. Это обобщает Шаблон:Не переведено 5, утверждающую, что граф без треугольников имеет не более Шаблон:Math рёбер. Для графов без треугольников оптимальное кликовое покрытие рёбер имеет клику для каждого ребра, а потому число пересечений равно числу рёберШаблон:Sfn.
Даже более сильное ограничение возможно, если число рёбер строго больше Шаблон:Math. Пусть p равно числу пар вершин, не соединённых рёбрами заданного графа Шаблон:Math, и пусть Шаблон:Math равно числу, для которого Шаблон:Math. Тогда число пересечений графа Шаблон:Math не превосходит Шаблон:Math Шаблон:SfnШаблон:Sfn.
Графы, являющиеся дополнениями разреженных графов, имеют небольшое число пересечений — число пересечений любого графа Шаблон:Math с Шаблон:Math вершинами i не превосходит Шаблон:Math, где Шаблон:Math — основание натурального логарифма, d максимальная степень дополнительного графа Шаблон:Math Шаблон:Sfn.
Вычислительная сложность
Проверка, что у данного графа Шаблон:Math число пересечений не превосходит заданного числа Шаблон:Math, является NP-полной задачейШаблон:SfnШаблон:SfnШаблон:Sfn. Таким образом, является NP-трудной задачей вычисление числа пересечений заданного графа.
Задача вычисления числа пересечений, однако, является Шаблон:Не переведено 5. То есть существует функция Шаблон:Math такая, что при равенстве числа пересечений числу Шаблон:Math время вычисления этого числа не превосходит произведения Шаблон:Math на полином от n. Это можно показать, если обратить внимание на то, что существует не более Шаблон:Math различных закрытых окрестностей в графе. Две вершины, принадлежащие одному и тому же набору клик, имеют одних и тех же соседей, а тогда граф, образованный выбором одной вершины для каждой закрытой окрестности, имеет то же самое число пересечений, что и исходный граф. Поэтому за полиномиальное время вход может быть сведён к меньшему Шаблон:Не переведено 5 с максимум Шаблон:Math вершинами. Применение алгоритма поиска с возвратом с экспоненциальным временем работы для этого ядра приводит к функции Шаблон:Math, которая является Шаблон:Не переведено 5 от Шаблон:Math Шаблон:Sfn. Двойная экспоненциальная зависимость от Шаблон:Math не может быть сведена к простой экспоненциональной зависимости посредством выделения ядра полиномиального размера, пока полиномиальная иерархия не исчезнетШаблон:Sfn, и если гипотеза об экспоненциальном времени верна, двойной экспонециальной зависимости не избежать, будем мы использовать выделение ядра или нетШаблон:Sfn.
Более эффективные алгоритмы известны для определённых специальных классов графов. Число пересечений интервального графа всегда равно числу максимальных клик графа, которое можно вычислить за полиномиальное времяШаблон:SfnШаблон:Sfn. Более обще — число пересечений хордальных графов может быть вычислено алгоритмом, который строит порядок исключения вершин графа. На каждом шаге для каждой вершины Шаблон:Math образуем клику для вершины Шаблон:Math и её соседей и исключаем вершину, если остаются рёбра, инцидентные Шаблон:Math, но ещё не покрытые кликамиШаблон:Sfn.
См. также
- Двудольная размерность — наименьшее число биклик, необходимых для покрытия рёбер графа
- Задача о кликовом покрытии — NP-полная задача нахождения малого количества клик, покрывающих все вершины графа
Примечания
Литература
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга Как цитировано у Робертса (Шаблон:Harvtxt)
- Шаблон:Статья
- Шаблон:Статья Как процитировано у Робертса (Шаблон:Harvtxt)
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга. Как процитировано у Робертса (Шаблон:Harvtxt)
- Шаблон:Статья
- Шаблон:Книга
Ссылки
