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

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

Определение

Полный двудольный граф ${\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. Graph Theory // 3rd. — Springer, 2005. — С. 17. — ISBN 3-540-26182-6.

Эта страница в последний раз была отредактирована 23 декабря 2021 в 15:07.