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