График без биклик - Biclique-free graph
В теории графов , раздел математики, A т - biclique свободные графики представляют собой график , который не имеет 2 т -vertex полного двудольного графа K т , т как подграф. Семейство графов является бикликовым, если существует такое число t , что все графы в семействе не имеют t- бикликов. Семейства графов без бикликов образуют один из наиболее общих типов семейства разреженных графов . Они возникают в задачах инцидентности в дискретной геометрии , а также используются в параметризованной сложности .
Свойства
Разреженность
Согласно теореме Кевари – Соша – Турана , любой t -бикликовый граф с n- вершинами имеет O ( n 2 - 1 / t ) ребер, что значительно меньше, чем у плотного графа . И наоборот, если семейство графов определяется запрещенными подграфами или замкнуто относительно операции взятия подграфов и не включает плотные графы произвольно большого размера, оно должно быть t -биклико-свободным для некоторого t , иначе оно будет включать большие плотные полные двудольные графы.
В качестве нижней грани , Эрдёш, Хайнал & Луна (1964) высказала предположение , что каждый максимальная т -biclique свободного двудольный граф (один , к которому не больше краев не могут быть добавлены без создания т -biclique) имеет , по меньшей мере , ( т - 1) ( n + m - t + 1) ребер, где n и m - количество вершин по обе стороны от его двудольного деления.
Отношение к другим типам семейства разреженных графов
Граф с вырождением d обязательно будет ( d + 1) -бикликвным. Кроме того, любое нигде не плотное семейство графов не имеет бикликов. В более общем смысле, если существует граф с n- вершинами, который не является 1-мелким минором любого графа в семействе, то семейство должно быть n -бикликово-свободным, потому что все графы с n- вершинами являются 1-мелкими минорами K п , п . Таким образом, семейства графов без бикликов объединяют два самых общих класса разреженных графов.
Приложения
Дискретная геометрия
В дискретной геометрии многие типы графов инцидентностей обязательно не имеют бикликов. В качестве простого примера, график инцидентностей между конечным набором точек и прямых на евклидовой плоскости обязательно не имеет подграфа K 2,2 .
Параметризованная сложность
Графы без бикликов использовались в параметризованной сложности для разработки алгоритмов, эффективных для разреженных графов с достаточно небольшими значениями входных параметров. В частности, нахождение доминирующего набора размера k на t -бикликовых графиках можно решить с фиксированным параметром, если параметризовать его с помощью k + t , даже несмотря на то, что есть веские доказательства того, что это невозможно с использованием одного k в качестве параметра. Аналогичные результаты верны для многих вариаций задачи о доминирующем множестве. Также можно проверить, может ли один доминирующий набор размера не более k быть преобразован в другой с помощью цепочки вставок и удалений вершин с сохранением доминирующего свойства с той же параметризацией.