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

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

В математической области теории графов , A полный двудольный граф или biclique представляет собой особый вид двудольного графа , где каждая вершина первого набора соединена с каждой вершиной второго набора. ^{[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]} каждые два графа с одинаковыми обозначениями изоморфны .

Примеры [ править ]

Звезда графов К _1,3 , К _1,4 , К _1,5 , и К _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 в качестве второстепенного (Они не являются достаточными условиями для плоскостности и outerplanarity, но это необходимы). Наоборот, любой неплоский граф содержит либо K _3,3, либо полный граф K ₅ в качестве минора; это теорема Вагнера . ^[9]
• Каждый полный двудольный граф. K _{n , n} - граф Мура и ( n , 4) - клетка . ^[10]
• Полные двудольные графы K _{n , n} и K _{n , n +1} имеют максимально возможное количество ребер среди всех графов без треугольников с одинаковым количеством вершин; это теорема Мантеля . Результат Мантеля был обобщен на k -раздельные графы и графы, которые избегают больших клик в качестве подграфов в теореме Турана , и эти два полных двудольных графа являются примерами графов Турана , экстремальных графов для этой более общей проблемы. ^[11]
• Полный двудольный граф К _{т , п} имеет вершину , охватывающее число от мин { т , п } и кромку , охватывающее число от макса { т , п }.
• Полный двудольный граф K _{m , n} имеет максимальное независимое множество размера max { m , n }.
• Матрица смежности полного двудольного графа K _{т , п} имеет собственные значения √ нм , - √ нм и 0; с кратностью 1, 1 и n + m −2 соответственно. ^[12]
• Лапласиан матрица полного двудольного графа K _{т , п} имеет собственные значения п + т , п , т , и 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]

См. Также [ править ]

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

Ссылки [ править ]