Полный двудольный граф ( биклика ) — специальный вид двудольного графа , у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин.

Определение

Полный двудольный граф ${\displaystyle G:=(V_{1}+V_{2},E)}$ — это такой двудольный граф, что для любых двух вершин ${\displaystyle v_{1}\in V_{1}}$ и ${\displaystyle v_{2}\in V_{2}}$ , ${\displaystyle (v_{1},v_{2})}$ является ребром в ${\displaystyle G}$ . Полный двудольный граф с долями размера ${\displaystyle |V_{1}|=m}$ и ${\displaystyle |V_{2}|=n}$ обозначается как ${\displaystyle K_{m,n}}$ .

Примеры

• Графы ${\displaystyle K_{1,k}}$ называются звёздами , все полные двудольные графы, являющиеся деревьями , являются звёздами.
• Граф ${\displaystyle K_{1,3}}$ называется клешнёй и используется для определения графов без клешней .
• Граф ${\displaystyle K_{3,3}}$ иногда называется «коммунальным графом», название восходит к классической задаче « домики и колодцы », в современной интерпретации использующей «коммунальную» формулировку (подключить три домика к водо-, электро- и газоснабжению без пересечений линий на плоскости); задача неразрешима ввиду непланарности графа ${\displaystyle K_{3,3}}$ .

Свойства

• Задача поиска для данного двудольного графа полного двудольного подграфа ${\displaystyle K_{n,n}}$ с заданным параметром ${\displaystyle n}$ NP-полна .
• Планарный граф не может содержать ${\displaystyle K_{3,3}}$ в качестве минора графа . Внешнепланарный граф не может содержать ${\displaystyle K_{3,2}}$ в качестве минора (Это не достаточное условие планарности и внешней планарности, а необходимое). И наоборот, любой непланарный граф содержит либо ${\displaystyle K_{3,3}}$ , либо полный граф ${\displaystyle K_{5}}$ в качестве минора ( Теорема Понтрягина — Куратовского ).
• Полные двудольные графы ${\displaystyle K_{n,n}}$ являются графами Мура и ${\displaystyle (n,4)}$ - клетками .
• Полные двудольные графы ${\displaystyle K_{n,n}}$ и ${\displaystyle K_{n,n+1}}$ являются графами Турана .
• Полный двудольный граф ${\displaystyle K_{m,n}}$ имеет размер вершинного покрытия , равный ${\displaystyle \min(m,n)}$ и размер рёберного покрытия , равный ${\displaystyle \max(m,n)}$ .
• Полный двудольный граф ${\displaystyle K_{m,n}}$ имеет максимальное независимое множество размером ${\displaystyle \max(m,n)}$ .
• Матрица смежности полного двудольного графа ${\displaystyle K_{m,n}}$ имеет собственные значения ${\displaystyle {\sqrt {nm}}}$ , ${\displaystyle -{\sqrt {nm}}}$ и ${\displaystyle 0}$ с кратностями ${\displaystyle 1}$ , ${\displaystyle 1}$ и ${\displaystyle n+m-2}$ соответственно.
• Матрица Лапласа полного двудольного графа ${\displaystyle K_{m,n}}$ имеет собственные значения ${\displaystyle n+m}$ , ${\displaystyle n}$ , ${\displaystyle m}$ , ${\displaystyle 0}$ с кратностями ${\displaystyle 1}$ , ${\displaystyle m-1}$ , ${\displaystyle n-1}$ и ${\displaystyle 1}$ соответственно.
• Полный двудольный граф ${\displaystyle K_{m,n}}$ имеет ${\displaystyle m^{n-1}\cdot n^{m-1}}$ остовных деревьев .
• Полный двудольный граф ${\displaystyle K_{m,n}}$ имеет максимальное паросочетание размера ${\displaystyle \min(m,n)}$ .
• Полный двудольный граф ${\displaystyle K_{n,n}}$ имеет подходящую ${\displaystyle n}$ -рёберную раскраску , соответствующую латинскому квадрату .

Последние два результата являются следствием теоремы Холла , применённой к ${\displaystyle k}$ -регулярному двудольному графу.

См. также

• Цикл
• Путь
• Корона
• Полный многодольный граф

Литература

• John Adrian Bondy, U. S. R. Murty. Graph Theory with Applications. — North-Holland, 1976. — С. 5 . — ISBN 0-444-19451-7 . 13 апреля 2010 года.
• Reinhard Diestel. // 3rd. — Springer , 2005. — С. 17 . — ISBN 3-540-26182-6 .