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

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

Полный двудольный граф с $m=5$ и $n=3$
автоморфизмы = $\left\{{\begin{array}{ll}2m!n!&n=m\\m!n!&m\neq n\end{array}}\right.$
вершин = $n+m$
рёбер = $mn$
хроматическое число = 2
хроматический индекс = $\max(m,n)$
радиус = $\left\{{\begin{array}{ll}1&m=1\vee n=1\\2&m\neq 1\wedge n\neq 1\end{array}}\right.$
диаметр = $\left\{{\begin{array}{ll}1&m=n=1\\2&m\neq 1\vee n\neq 1\end{array}}\right.$
обхват == $\left\{{\begin{array}{ll}\infty &m=1\vee n=1\\4&m\neq 1\wedge n\neq 1\end{array}}\right.$
спектр = $\{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$-регулярному двудольному графу.

См. также

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

Литература

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