Полный двудольный граф (биклика) — специальный вид двудольного графа, у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин.
Определение Полный двудольный граф — это такой двудольный граф, что для любых двух вершин и , является ребром в . Полный двудольный граф с долями размера и обозначается как .
Примеры
Графы называются звёздами, все полные двудольные графы, являющиеся деревьями, являются звёздами. Граф называется клешнёй и используется для определения графов без клешней. Граф иногда называется «коммунальным графом», название восходит к классической задаче «домики и колодцы», в современной интерпретации использующей «коммунальную» формулировку (подключить три домика к водо-, электро- и газоснабжению без пересечений линий на плоскости); задача неразрешима ввиду непланарности графа .
Свойства Задача поиска для данного двудольного графа полного двудольного подграфа с заданным параметром NP-полна. Планарный граф не может содержать в качестве минора графа. Внешнепланарный граф не может содержать в качестве минора (Это не достаточное условие планарности и внешней планарности, а необходимое). И наоборот, любой непланарный граф содержит либо , либо полный граф в качестве минора (Теорема Понтрягина — Куратовского). Полные двудольные графы являются графами Мура и -клетками. Полные двудольные графы и являются графами Турана. Полный двудольный граф имеет размер вершинного покрытия, равный и размер рёберного покрытия, равный . Полный двудольный граф имеет максимальное независимое множество размером . Матрица смежности полного двудольного графа имеет собственные значения , и с кратностями , и соответственно. Матрица Лапласа полного двудольного графа имеет собственные значения , , , с кратностями , , и соответственно. Полный двудольный граф имеет остовных деревьев. Полный двудольный граф имеет максимальное паросочетание размера . Полный двудольный граф имеет подходящую -рёберную раскраску, соответствующую латинскому квадрату.
Последние два результата являются следствием теоремы Холла, применённой к -регулярному двудольному графу.
См. также Цикл Путь Корона Полный многодольный граф
Литература
Категория:Параметрические семейства графов