Введение

Двухдольный граф, где каждый узел первого множества соединен со всеми узлами второго множества.

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

Определение

Полный двудольный граф — это граф, чьи вершины можно разбить на два подмножества и таким образом, чтобы ни одно ребро не имело обе конечные точки в одном и том же подмножестве, и каждое возможное ребро, которое могло бы соединить вершины из разных подмножеств, являлось бы частью графа. То есть, это двудольный граф, такой, что для любых двух вершин и , ребро существует в E. Полный двудольный граф с подмножествами размера и обозначается как ;
Граф называется графом коммунальных услуг. Это название происходит от стандартной математической головоломки, в которой три коммунальные службы должны быть соединены с тремя зданиями; её невозможно решить без пересечений из-за непланарности графа . Максимальные биклики, найденные в качестве подграфов диграфа отношения, называются концептами. Когда решётка формируется путем взятия пересечений и объединений этих подграфов, отношение имеет индуцированную решётку концептов. Этот тип анализа отношений называется формальным концептуальным анализом.

Свойства

+ Пример полных двудольных графов с 3 ребрами4 ребрами5 ребрамиРегулярные сложные многоугольники формы 2{4}p имеют полные двудольные графы с 2p вершинами (красными и синими) и 2 ребрами. Они также могут быть представлены как p раскрасок ребер. Для заданного двудольного графа, проверка наличия в нем полного двудольного подграфа для параметра i является NP-полной задачей. Планарный граф не может содержать в качестве минора; внешнепланарный граф не может содержать в качестве минора (это не достаточные условия для планарности и внешнепланарности, но необходимые). И наоборот, каждый непланарный граф содержит либо либо полный граф в качестве минора; это теорема Вагнера. Каждый полный двудольный граф является графом Мура и (n,4)-клетью. Полные двудольные графы и имеют максимально возможное число ребер среди всех треугольник-свободных графов с одинаковым числом вершин; это теорема Мантеля. Результат Мантеля был обобщен на k-дольные графы и графы, избегающие больших клик в качестве подграфов в теореме Турана, и эти два полных двудольных графа являются примерами графов Турана, экстремальных графов для этой более общей задачи. Полный двудольный граф имеет число вершинного покрытия, равное 'min'{m, n}, и число реберного покрытия, равное 'max'{m, n}. Полный двудольный граф имеет максимальное независимое множество размера 'max'{m, n}. Матрица смежности полного двудольного графа имеет собственные значения , и 0; с кратностью 1, 1 и n + m − 2 соответственно. Матрица Лапласа полного двудольного графа имеет собственные значения n + m, n, m и 0; с кратностью 1, m − 1, n − 1 и 1 соответственно. Полный двудольный граф имеет остовных деревьев. Полный двудольный граф имеет максимальное паросочетание размера 'min'{m,n}. Полный двудольный граф имеет правильную n-раскраску ребер, соответствующую латинскому квадрату. Каждый полный двудольный граф является модульным графом: для каждой тройки вершин существует медиана, принадлежащая кратчайшим путям между каждой парой вершин.