Полный двудольный граф - Complete bipartite graph
Полный двудольный граф | |
---|---|
Вершины | п + м |
Края | млн |
Радиус | |
Диаметр | |
Обхват | |
Автоморфизмы | |
Хроматическое число | 2 |
Хроматический индекс | макс { m , n } |
Спектр | |
Обозначение | |
Таблица графиков и параметров |
В математической области теории графов , A полный двудольный граф или biclique представляет собой особый вид двудольного графа , где каждая вершина первого набора соединена с каждой вершиной второго набора.
Сама теория графов обычно начинается с работы Леонарда Эйлера 1736 года о семи мостах Кенигсберга . Однако рисунки полных двудольных графиков были напечатаны уже в 1669 году в связи с изданием произведений Рамона Лулля под редакцией Афанасия Кирхера . Сам Ллулл сделал аналогичные рисунки полных графиков тремя веками ранее.
Определение
Полный двудольный граф представляет собой график, вершины которого можно разбить на два подмножества V 1 и V 2 таким образом, чтобы ни одно ребро не имеет оба конца в том же самом подмножестве, и каждый возможный край , который может соединить вершины в разных подмножеств является частью графа. То есть, это двудольный граф ( V 1 , V 2 , Е ) таким образом, что на каждые две вершины v 1 ∈ V 1 и V 2 ∈ V 2 , V 1 V 2 является ребром в Е . Полный двудольный граф с разбиениями размера | V 1 | = m и | V 2 | = n , обозначается K m, n ; каждые два графа с одинаковыми обозначениями изоморфны .
Примеры
- Для любого k , K 1, k называется звездой . Все полные двудольные графы, являющиеся деревьями, являются звездами.
- Граф K 1,3 называется клешней и используется для определения графов без клешней .
- Граф K 3,3 называется графом полезности . Это использование происходит из стандартной математической головоломки, в которой каждая из трех инженерных сетей должна быть связана с тремя зданиями; невозможно решить без пересечений из - за непланарности из K 3,3 .
- Максимальные биклики, обнаруженные как подграфы орграфа отношения, называются концептами . Когда решетка формируется путем взятия встреч и соединений этих подграфов, отношение имеет решетку индуцированных понятий . Такой тип анализа отношений называется анализом формальных понятий .
Характеристики
К 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 в качестве второстепенного (Они не являются достаточными условиями для плоскостности и outerplanarity, но это необходимы). Наоборот, любой неплоский граф содержит либо K 3,3, либо полный граф K 5 в качестве минора; это теорема Вагнера .
- Каждый полный двудольный граф. K n , n - граф Мура и ( n , 4) - клетка .
- Полные двудольные графы K n , n и K n , n +1 имеют максимально возможное количество ребер среди всех графов без треугольников с одинаковым количеством вершин; это теорема Мантеля . Результат Мантеля был обобщен на k -раздельные графы и графы, которые избегают больших клик в качестве подграфов в теореме Турана , и эти два полных двудольных графа являются примерами графов Турана , экстремальных графов для этой более общей проблемы.
- Полный двудольный граф К т , п имеет вершину , охватывающее число от мин { т , п } и кромку , охватывающее число от макса { т , п }.
- Полный двудольный граф K m , n имеет максимальное независимое множество размера max { m , n }.
- Матрица смежности полного двудольного графа K т , п имеет собственные значения √ нм , - √ нм и 0; с кратностью 1, 1 и n + m −2 соответственно.
- Лапласиан матрица полного двудольного графа K т , п имеет собственные значения п + т , п , т , и 0; с кратностью 1, m −1, n −1 и 1 соответственно.
- Полный двудольный граф K m , n имеет m n −1 n m −1 остовных деревьев .
- Полный двудольный граф K m , n имеет максимальное соответствие размера min { m , n }.
- Полный двудольный граф K n , n имеет собственную n- краевую раскраску, соответствующую латинскому квадрату .
- Каждый полный двудольный граф является модульным графом : каждая тройка вершин имеет медиану, которая принадлежит кратчайшим путям между каждой парой вершин.
Смотрите также
- Граф без бикликов , класс разреженных графов, определяемый избеганием полных двудольных подграфов
- Граф короны, граф , образованный удалением идеального соответствия из полного двудольного графа
- Полный многодольный граф , обобщение полных двудольных графов на более чем два набора вершин
- Бикликовая атака