В теории графов , раздел математики, A т - biclique свободные графики представляют собой график , который не имеет 2 т -vertex полного двудольного графа K т , т как подграф. Семейство графов является бикликовым, если существует такое число t , что все графы в семействе не имеют t- бикликов. Семейства графов без бикликов образуют один из наиболее общих типов семейства разреженных графов . Они возникают в задачах инцидентности в дискретной геометрии , а также используются в параметризованной сложности .
Характеристики
Разреженность
Согласно теореме Кевари – Соша – Турана , любой t -бикликовый граф с n- вершинами имеет O ( n 2 - 1 / t ) ребер, что значительно меньше, чем у плотного графа . [1] И наоборот, если семейство графов определяется запрещенными подграфами или замкнуто при операции взятия подграфов и не включает плотные графы произвольно большого размера, оно должно быть t -бикликово-свободным для некоторого t , иначе оно бы включают большие плотные полные двудольные графы.
В качестве нижней грани , Эрдёш, Хайнал & Луна (1964) высказала предположение , что каждый максимальная т -biclique свободного двудольный граф (один , к которому не больше краев не могут быть добавлены без создания т -biclique) имеет , по меньшей мере , ( т - 1) ( n + m - t + 1) ребер, где n и m - количество вершин по обе стороны от его двудольного деления. [2]
Отношение к другим типам семейства разреженных графов
Граф с вырождением d обязательно является ( d + 1) -бикликвным. Кроме того, любое нигде не плотное семейство графов не имеет бикликов. В более общем смысле, если существует граф с n- вершинами, который не является 1-мелким минором любого графа в семействе, то семейство должно быть n -бикликово-свободным, потому что все графы с n- вершинами являются 1-мелкими минорами K п , п . Таким образом, семейства графов без бикликов объединяют два самых общих класса разреженных графов. [3]
Приложения
Дискретная геометрия
В дискретной геометрии многие типы графов инцидентностей обязательно не имеют бикликов. В качестве простого примера, график инцидентностей между конечным набором точек и прямых на евклидовой плоскости обязательно не имеет подграфа K 2,2 . [4]
Параметризованная сложность
Графы без бикликов использовались в параметризованной сложности для разработки алгоритмов, эффективных для разреженных графов с достаточно малыми значениями входных параметров. В частности, нахождение доминирующего набора размера k на t- образных графиках без перекосов является управляемым с фиксированным параметром при параметризации k + t , даже несмотря на то, что есть веские доказательства того, что это невозможно с использованием одного k в качестве параметра. Аналогичные результаты верны для многих вариантов задачи о доминирующем множестве. [3] Также возможно проверить, может ли один доминирующий набор размера не больше k быть преобразован в другой с помощью цепочки вставок и удалений вершин, сохраняя доминирующее свойство, с той же параметризацией. [5]
Рекомендации
- ^ Kővári, T .; Т. Сос, В .; Туран, П. (1954), "Об одной проблеме К. Заранкевича" (PDF) , Colloquium Math. , 3 : 50–57, MR 0065617. Эта работа касается количества ребер в двудольных графах без бикликов, но стандартное применение вероятностного метода переносит ту же оценку на произвольные графы.
- ^ Erds, P .; Хайнал, А .; Луна, JW (1964), "Проблема в теории графов" (PDF) , Американский Математический Месячный , 71 : 1107-1110, DOI : 10,2307 / 2311408 , MR 0170339.
- ^ а б Телле, Ян Арне; Вилланджер, Ингве (2012), «FPT-алгоритмы для доминирования в графах без бикликов», у Эпштейна, Лия; Ferragina, Паоло (ред.), Алгоритмы - ESA 2012: 20 Ежегодный европейский симпозиум, Любляна, Словения, 10-12 сентября, 2012, Труды , Lecture Notes в области компьютерных наук , 7501 ., Springer, С. 802-812, DOI : 10.1007 / 978-3-642-33090-2_69.
- ^ Каплан, Хаим; Матушек, Иржи ; Шарир, Мика (2012), «Простые доказательства классических теорем в дискретной геометрии с помощью метода полиномиального разбиения Гута – Каца», Дискретная и вычислительная геометрия , 48 (3): 499–517, arXiv : 1102.5391 , doi : 10.1007 / s00454- 012-9443-3 , MR 2957631. См., В частности, лемму 3.1 и замечания после леммы.
- ^ Локштанов Даниил; Mouawad, Amer E .; Панолан, Фахад; Рамануджан, MS; Саураб, Сакет (2015), «Реконфигурация на разреженных графах», в Дене, Франк; Мешок, Йорг-Рюдигер ; Стеге, Ульрике (ред.), Алгоритмы и структуры данных: 14-й Международный симпозиум, WADS 2015, Виктория, Британская Колумбия, Канада, 5-7 августа 2015 г., Proceedings (PDF) , Lecture Notes in Computer Science, 9214 , Springer, pp. 506-517, Arxiv : 1502.04803 , DOI : 10.1007 / 978-3-319-21840-3_42 , архивируются от оригинала (PDF) на 2017-11-13 , извлекаются 2017-05-24.