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

Полный двудольный граф с $m=5$ и $n=3$
автоморфизмы = $\{\begin{array}{cc}2m!n!& n=m\\ m!n!& m\ne n\end{array}$
вершин = $n+m$
рёбер = $mn$
хроматическое число = 2
хроматический индекс = $\max (m,n)$
радиус = $\{\begin{array}{cc}1& m=1\vee n=1\\ 2& m\ne 1\wedge n\ne 1\end{array}$
диаметр = $\{\begin{array}{cc}1& m=n=1\\ 2& m\ne 1\vee n\ne 1\end{array}$
обхват == $\{\begin{array}{cc}\mathrm{\infty }& m=1\vee n=1\\ 4& m\ne 1\wedge n\ne 1\end{array}$
спектр = $\{0^{n+m-2},(\pm \sqrt{nm}{)}^1\}$
обозначение = $K_{m,n}$

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

Определение

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

Примеры

Графы-звёзды $S_3$, $S_4$, $S_5$ и $S_6$.

Граф $K_{3,3}$.

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

Свойства

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

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

См. также

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

Литература

• Шаблон:Статья
• Шаблон:Статья