Полный двудольный граф

Двудольный граф, в котором каждый узел 1-го набора связан со всеми узлами 2-го набора.

В математической области теории графов полный двудольный граф или биклика — это особый вид двудольного графа , в котором каждая вершина первого множества соединена с каждой вершиной второго множества. ^{[1] [2]}

Сама теория графов обычно датируется работой Леонарда Эйлера 1736 года о Семи мостах Кёнигсберга . Однако рисунки полных двудольных графов были напечатаны уже в 1669 году в связи с изданием работ Рамона Луллия под редакцией Атанасиуса Кирхера . ^{[3] [4]} Сам Луллий сделал похожие рисунки полных графов тремя столетиями ранее. ^[3]

Определение

Полный двудольный граф — это граф, вершины которого можно разбить на два подмножества V ₁ и V ₂ так, что ни одно ребро не имеет обеих конечных точек в одном и том же подмножестве, и каждое возможное ребро, которое может соединять вершины в разных подмножествах, является частью графа. То есть, это двудольный граф ( V ₁ , V ₂ , E ) такой, что для любых двух вершин v ₁ ∈ V ₁ и v ₂ ∈ V ₂ , v ₁ v ₂ является ребром в E . Полный двудольный граф с разбиениями размера | V ₁ | = m и | V ₂ | = n обозначается K _{m , n} ; ^{[1] [2]} любые два графа с одинаковой нотацией являются изоморфными .

Примеры

Звездные графы K _1,3 , K _1,4 , K _1,5 и K _1,6 .

Полный двудольный граф K _4,7, показывающий, что задача о кирпичном заводе Турана с 4 складскими помещениями (желтые точки) и 7 печами (синие точки) требует 18 пересечений (красные точки)

• Для любого k , K _{≥ 1, k} называется звездой . ^[2] Все полные двудольные графы, являющиеся деревьями, являются звездами.
  • Граф K _1,3 называется клешней и используется для определения графов без клешней . ^[5]
• Граф K _3,3 называется графом утилит . Это использование происходит от стандартной математической головоломки, в которой три утилиты должны быть подключены к трем зданиям; это _{невозможно} решить без пересечений из-за непланарности K 3,3 . ^[6]
• Максимальные биклики, найденные как подграфы орграфа отношения, называются понятиями . Когда решетка формируется путем взятия встреч и соединений этих подграфов, отношение имеет индуцированную решетку понятий . Этот тип анализа отношений называется формальным анализом понятий .

Характеристики

• Для двудольного графа проверка того, содержит ли он полный двудольный подграф K _{i , i} для параметра  i, является NP-полной задачей. ^[8]
• Планарный граф не может содержать K _3,3 в качестве минора ; внешнепланарный граф не может содержать K _3,2 в качестве минора (Это не достаточные условия для планарности и внешнепланарности, но необходимые). Наоборот, каждый непланарный граф содержит либо K _3,3 , либо полный граф K ₅ в качестве минора; это теорема Вагнера . ^[9]
• Каждый полный двудольный граф. K _{n , n} является графом Мура и ( n ,4) - клеткой . ^[10]
• Полные двудольные графы K _{n , n} и K _{n , n +1} имеют максимально возможное число ребер среди всех графов без треугольников с тем же числом вершин; это теорема Мантеля . Результат Мантеля был обобщен на k -дольные графы и графы, которые избегают больших клик как подграфов в теореме Турана , и эти два полных двудольных графа являются примерами графов Турана , экстремальных графов для этой более общей задачи. ^[11]
• Полный двудольный граф K _{m , n} имеет число вершинных покрытий min { m , n } и число реберных покрытий max { m , n } .
• Полный двудольный граф K _{m , n} имеет максимальное независимое множество размера max { m , n }.
• Матрица смежности полного двудольного графа K _{m , n} имеет собственные значения √ nm , − √ nm и 0; с кратностью 1, 1 и n + m − 2 соответственно. ^[12]
• Матрица Лапласа полного двудольного графа K _{m , n} имеет собственные значения n + m , n , m и 0; с кратностями 1, m − 1 , n − 1 и 1 соответственно.
• Полный двудольный граф K _{m , n} имеет m ^{n −1} n ^{m −1} остовных деревьев . ^[13]
• Полный двудольный граф K _{m , n} имеет максимальное паросочетание размера min { m , n }.
• Полный двудольный граф K _{n , n} имеет правильную n -рёберную раскраску, соответствующую латинскому квадрату . ^[14]
• Каждый полный двудольный граф является модулярным графом : каждая тройка вершин имеет медиану, которая принадлежит кратчайшим путям между каждой парой вершин. ^[15]

Смотрите также

• Граф, свободный от биклики , класс разреженных графов, определяемый путем избегания полных двудольных подграфов.
• Граф короны , граф, образованный путем удаления совершенного паросочетания из полного двудольного графа.
• Полный многодольный граф , обобщение полных двудольных графов на более чем два набора вершин.
• Атака бикли

Ссылки

1. Bondy, John Adrian ; Murty, USR (1976), Теория графов с приложениями, North-Holland, стр. 5, ISBN 0-444-19451-7.
2. Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN 3-540-26182-6. Электронное издание, стр. 17.
3. Knuth, Donald E. (2013), «Две тысячи лет комбинаторики», в Wilson, Robin; Watkins, John J. (ред.), Комбинаторика: древняя и современная , Oxford University Press, стр. 7–37, ISBN 0191630624.
4. Рид, Рональд К.; Уилсон, Робин Дж. (1998), Атлас графиков , Clarendon Press, стр. ii, ISBN 9780198532897.
5. Ловас, Ласло ; Пламмер, Майкл Д. (2009), Теория соответствия, Провиденс, Род-Айленд: AMS Chelsea, стр. 109, ISBN 978-0-8218-4759-6, г-н  2536865Исправленное переиздание оригинала 1986 года.
6. Грайс, Дэвид ; Шнайдер, Фред Б. (1993), Логический подход к дискретной математике, Springer, стр. 437, ISBN 9780387941158.
7. Коксетер, Регулярные комплексные многогранники , второе издание, стр.114
8. Гэри, Майкл Р.; Джонсон , Дэвид С. (1979), "[GT24] Сбалансированный полный двудольный подграф", Компьютеры и неразрешимость: Руководство по теории NP-полноты , W. H. Freeman , стр. 196, ISBN 0-7167-1045-5.
9. Дистель 2005, стр. 105
10. Биггс, Норман (1993), Алгебраическая теория графов, Cambridge University Press, стр. 181, ISBN 9780521458979.
11. Боллобаш, Бела (1998), Современная теория графов, Graduate Texts in Mathematics , т. 184, Springer, стр. 104, ISBN 9780387984889.
12. Боллобаш (1998), стр. 266.
13. Юнгникель, Дитер (2012), Графы, сети и алгоритмы, Алгоритмы и вычисления в математике, т. 5, Springer, стр. 557, ISBN 9783642322785.
14. Дженсен, Томми Р.; Тофт, Бьярне (2011), Проблемы раскраски графов, Wiley Series in Discrete Mathematics and Optimization, т. 39, Wiley, стр. 16, ISBN 9781118030745.
15. Бандельт, Х.-Й.; Дальманн, А.; Шютте, Х. (1987), «Абсолютные ретракты двудольных графов», Дискретная прикладная математика , 16 (3): 191–215, doi : 10.1016/0166-218X(87)90058-8 , MR  0878021.