Граф без биклик
В теории графов , разделе математики, без t -биклик граф — это граф, который не имеет K t , t ( полный двудольный граф с 2t вершинами) в качестве подграфа . Семейство графов является безбикликой, если существует число t такое, что все графы в семействе t -свободны от биклик. Семейства графов без биклик образуют один из наиболее общих типов семейств разреженных графов . Они возникают в задачах инцидентности в дискретной геометрии , а также используются в параметризованной сложности .
Характеристики
[ редактировать ]Разреженность
[ редактировать ]Согласно теореме Кёвари–Соша–Турана , каждый граф с n -вершинами и t -бикликами имеет O ( n 2 − 1/ т ) ребер, значительно меньше, чем в плотном графе . было бы [1] И наоборот, если семейство графов определяется запрещенными подграфами или замкнуто относительно операции взятия подграфов и не включает в себя плотные графы сколь угодно большого размера, то оно должно быть t -бикликой для некоторого t , иначе оно включало бы большие плотные графы полные двудольные графы.
В качестве нижней границы Эрдеш , Хайнал и Мун (1964) предположили, что каждый максимальный двудольный граф без t -биклик (тот, к которому нельзя добавить больше ребер без создания t -биклики) имеет по крайней мере ( t - 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]
Ссылки
[ редактировать ]- ^ Ковари, Т.; Т. Сос, В .; Туран, П. (1954), «К проблеме К. Заранкевича» (PDF) , Коллоквиум Math. , 3 : 50–57, МР 0065617 . Эта работа касается количества ребер в двудольных графах без биклик, но стандартное применение вероятностного метода переносит ту же оценку на произвольные графы.
- ^ Эрдеш, П .; Хайнал, А. ; Мун, Дж.В. (1964), «Проблема теории графов» (PDF) , The American Mathematical Monthly , 71 : 1107–1110, doi : 10.2307/2311408 , MR 0170339 .
- ^ Jump up to: а б Телле, Ян Арне; Вилланджер, Ингве (2012), «Алгоритмы FPT для доминирования в графах без биклик», в Эпштейне, Лия; Феррагина, Паоло (ред.), Алгоритмы - ESA 2012: 20-й ежегодный европейский симпозиум, Любляна, Словения, 10–12 сентября 2012 г., Труды , Конспекты лекций по информатике , том. 7501, Springer, стр. 802–812, номер документа : 10.1007/978-3-642-33090-2_69 .
- ^ Каплан, Хаим; Матушек, Иржи ; Шарир, Миха (2012), «Простые доказательства классических теорем в дискретной геометрии с помощью метода полиномиального разделения Гута – Каца», Discrete and Computational Geometry , 48 (3): 499–517, arXiv : 1102.5391 , doi : 10.1007/s00454- 012-9443-3 , МР 2957631 . См., в частности, лемму 3.1 и замечания, следующие за леммой.
- ^ Локштанов Даниил; Муавад, Амер Э.; Панолан, Фахад; Рамануджан, М.С.; Саураб, Сакет (2015), «Реконфигурация разреженных графов», Дене, Франк; Зак, Йорг-Рюдигер ; Стеге, Ульрике (ред.), Алгоритмы и структуры данных: 14-й международный симпозиум, WADS 2015, Виктория, Британская Колумбия, Канада, 5–7 августа 2015 г., Материалы (PDF) , Конспекты лекций по информатике, том. 9214, Springer, стр. 506–517, arXiv : 1502.04803 , doi : 10.1007/978-3-319-21840-3_42 , заархивировано из оригинала (PDF) 13 ноября 2017 г. , получено 24 мая 2017 г.