WikiSort.ru - Не сортированное

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

Определение

Полный двудольный граф ${\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_{m,n}}$ NP-полна.
• Планарный граф не может содержать ${\displaystyle K_{3,3}}$ в качестве минора графа. Внешнепланарный граф не может содержать ${\displaystyle K_{3,2}}$ в качестве минора (Это не достаточное условие планарности и внешней планарности, а необходимое). И наоборот, любой непланарный граф содержит либо ${\displaystyle K_{3,3}}$ , либо полный граф ${\displaystyle K_{5}}$ в качестве минора (теорема Куратовского^[en]).
• Полные двудольные графы ${\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.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.