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

Полный двудольный граф
Полный двудольный граф с m = 5 и n = 3
Вершины	п + м
Края	минута
Радиус	$\left\{{\begin{array}{ll}1&m=1\vee n=1\\2&{\text{otherwise}}\end{array}}\right.$
Диаметр	$\left\{{\begin{array}{ll}1&m=n=1\\2&{\text{otherwise}}\end{array}}\right.$
Обхват	$\left\{{\begin{array}{ll}\infty &m=1\lor n=1\\4&{\text{otherwise}}\end{array}}\right.$
Автоморфизмы	$\left\{{\begin{array}{ll}2m!n!&n=m\\m!n!&{\text{otherwise}}\end{array}}\right.$
Хроматическое число	2
Хроматический индекс	макс { м , п }
Спектр	$\left\{0^{n+m-2},(\pm {\sqrt {nm}})^{1}\right\}$
Обозначения	К { м , п }
Таблица графиков и параметров

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

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

Определение

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

Примеры

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

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

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

Свойства

Пример K _{p , p} полных двудольных графов

К 3,3	К 4,4	К 5,5
3 раскраски краев	4 раскраски краев	5 раскрасок краев
Правильные комплексные многоугольники вида 2{4} p имеют полные двудольные графы с 2 p вершинами (красными и синими) и p 2 2-ребра. Их также можно нарисовать как p -раскраски ребер.

• Учитывая двудольный граф, проверка того, содержит ли он полный двудольный подграф K _{i , i} для параметра i, является NP-полной задачей.
• Планарный граф не может содержать K _3,3 в качестве минора ; внешнепланарный граф не может содержать K _3,2 в качестве минора (это не достаточные условия планарности и внешнепланарности, но необходимые). И наоборот, каждый непланарный граф содержит либо K _3,3 , либо полный граф K ₅ в качестве минора; это теорема Вагнера .
• Любой полный двудольный граф. Kn _{— , n} — граф Мура , а ( n 4) , клетка .
• Полные двудольные графы K _{n , n} и K _{n , n +1} имеют максимально возможное число ребер среди всех графов без треугольников с одинаковым числом вершин; это теорема Мантеля . Результат Мантеля был обобщен на k -дольные графы и графы, которые избегают больших клик в качестве подграфов в теореме Турана , и эти два полных двудольных графа являются примерами графов Турана , экстремальных графов для этой более общей проблемы.
• Полный двудольный граф m _{, n имеет} число покрытия вершин min K { m , n } и число покрытия ребер max m { } , n .
• Полный двудольный граф K _{m , n} имеет максимальное независимое множество размера max { m , n }.
• Матрица смежности полного двудольного графа K _{m , n} имеет собственные значения √ nm , − √ nm и 0; с кратностью 1, 1 и n + m − 2 соответственно.
• Матрица Лапласа полного двудольного графа K _{m , n} имеет собственные значения n + m , n , m и 0; с кратностью 1, m − 1 , n − 1 и 1 соответственно.
• Полный двудольный граф K _{m , n} имеет m ^{п -1} н ^{м −1} охватывающие деревья .
• Полный двудольный граф K _{m , n} имеет максимальное паросочетание размера min { m , n }.
• Полный двудольный граф Kn _{, соответствующую n} имеет правильную n -раскраску ребер, латинскому квадрату .
• Каждый полный двудольный граф является модульным графом : каждая тройка вершин имеет медиану, принадлежащую кратчайшим путям между каждой парой вершин.

См. также

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