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

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

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

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

Определение

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

Примеры

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

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

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

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

• Учитывая двудольный граф, проверка того, содержит ли он полный двудольный подграф K _{i , i} для параметра  i, является NP-полной задачей. ^[8]
• Планарный граф не может содержать K _3,3 в качестве минора ; внешнепланарный граф не может содержать K _3,2 в качестве минора (это не достаточные условия планарности и внешнепланарности, но необходимые). И наоборот, каждый непланарный граф содержит либо K _3,3 , либо полный граф K ₅ в качестве минора; это теорема Вагнера . ^[9]
• Любой полный двудольный граф. Kn _{, n} — граф Мура , a ( 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 соответственно.
• Полный двудольный граф ^Km , _{n имеет} mn − ^{1 nm} − ¹ _{остовных} деревьев . ^[13]
• Полный двудольный граф K _{m , n} имеет максимальное паросочетание размера min { m , n }.
• Полный двудольный граф Kn _{, n} имеет правильную n -раскраску ребер _, соответствующую латинскому квадрату . ^[14]
• Каждый полный двудольный граф является модульным графом : каждая тройка вершин имеет медиану, принадлежащую кратчайшим путям между каждой парой вершин. ^[15]

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

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

Рекомендации

1. Бонди, Джон Адриан ; Мурти, USR (1976), Теория графов с приложениями, Северная Голландия, стр. 5, ISBN 0-444-19451-7.
2. Diestel, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN 3-540-26182-6. Электронное издание, стр. 17.
3. Кнут, Дональд Э. (2013), «Две тысячи лет комбинаторики», Уилсон, Робин; Уоткинс, Джон Дж. (ред.), Комбинаторика: древнее и современное , Oxford University Press, стр. 7–37, ISBN 0191630624.
4. Прочтите, Рональд С.; Уилсон, Робин Дж. (1998), Атлас графиков , Clarendon Press, стр. 2, 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-полноты , WH Freeman , p. 196, ISBN 0-7167-1045-5.
9. Дистель 2005, с. 105
10. Биггс, Норман (1993), Алгебраическая теория графов, Cambridge University Press, стр. 181, ISBN 9780521458979.
11. Боллобас, Бела (1998), Современная теория графов, Тексты для выпускников по математике , том. 184, Спрингер, с. 104, ISBN 9780387984889.
12. Боллобас (1998), с. 266.
13. Юнгникель, Дитер (2012), Графики, сети и алгоритмы, Алгоритмы и вычисления в математике, том. 5, Спрингер, с. 557, ISBN 9783642322785.
14. Дженсен, Томми Р.; Тофт, Бьерн (2011), Проблемы раскраски графов, Серия Уайли по дискретной математике и оптимизации, том. 39, Уайли, с. 16, ISBN 9781118030745.
15. Бандельт, H.-J.; Дельманн, А.; Шютте, Х. (1987), «Абсолютные ретракты двудольных графов», Discrete Applied Mathematics , 16 (3): 191–215, doi : 10.1016/0166-218X(87)90058-8 , MR  0878021.