Русская Википедия:Полный двудольный граф
Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску
автоморфизмы = <math>\left\{\begin{array}{ll}2 m! n! & n = m\\ m! n! & m \neq n \end{array}\right.</math>
вершин = <math>n+m</math>
рёбер = <math>mn</math>
хроматическое число = 2
хроматический индекс = <math>\max(m, n)</math>
радиус = <math>\left\{\begin{array}{ll}1 & m = 1 \vee n = 1\\ 2 & m \neq 1 \wedge n \neq 1\end{array}\right.</math>
диаметр = <math>\left\{\begin{array}{ll}1 & m = n = 1\\ 2 & m \neq 1 \vee n \neq 1\end{array}\right.</math>
обхват == <math>\left\{\begin{array}{ll}\infty & m = 1 \vee n = 1\\ 4 & m \neq 1 \wedge n \neq 1\end{array}\right.</math>
спектр = <math>\{0^{n + m - 2}, (\pm \sqrt{n m})^1\}</math>
обозначение = <math>K_{m,n}</math>
Полный двудольный граф (биклика) — специальный вид двудольного графа, у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин.
Определение
Полный двудольный граф <math>G := (V_1 + V_2, E)</math> — это такой двудольный граф, что для любых двух вершин <math>v_1 \in V_1</math> и <math>v_2 \in V_2</math>, <math>(v_1, v_2)</math> является ребром в <math>G</math>. Полный двудольный граф с долями размера <math>|V_1 | = m</math> и <math>|V_2 | = n</math> обозначается как <math>K_{m, n}</math>.
Примеры
- Графы <math>K_{1,k}</math> называются звёздами, все полные двудольные графы, являющиеся деревьями, являются звёздами.
- Граф <math>K_{1,3}</math> называется клешнёй и используется для определения графов без клешней.
- Граф <math>K_{3,3}</math> иногда называется «коммунальным графом», название восходит к классической задаче «домики и колодцы», в современной интерпретации использующей «коммунальную» формулировку (подключить три домика к водо-, электро- и газоснабжению без пересечений линий на плоскости); задача неразрешима ввиду непланарности графа <math>K_{3,3}</math>.
Свойства
- Задача поиска для данного двудольного графа полного двудольного подграфа <math>K_{n,n}</math> с заданным параметром <math>n</math> NP-полна.
- Планарный граф не может содержать <math>K_{3,3}</math> в качестве минора графа. Внешнепланарный граф не может содержать <math>K_{3,2}</math> в качестве минора (Это не достаточное условие планарности и внешней планарности, а необходимое). И наоборот, любой непланарный граф содержит либо <math>K_{3,3}</math>, либо полный граф <math>K_5</math> в качестве минора (Теорема Понтрягина — Куратовского).
- Полные двудольные графы <math>K_{n,n}</math> являются графами Мура и <math>(n,4)</math>-клетками.
- Полные двудольные графы <math>K_{n,n}</math> и <math>K_{n,n+1}</math> являются графами Турана.
- Полный двудольный граф <math>K_{m,n}</math> имеет размер вершинного покрытия, равный <math>\min(m, n)</math> и размер рёберного покрытия, равный <math>\max(m,n)</math>.
- Полный двудольный граф <math>K_{m,n}</math> имеет максимальное независимое множество размером <math>\max(m,n)</math>.
- Матрица смежности полного двудольного графа <math>K_{m,n}</math> имеет собственные значения <math>\sqrt{nm}</math>, <math>-\sqrt{nm}</math> и <math>0</math> с кратностями <math>1</math>, <math>1</math> и <math>n + m - 2</math> соответственно.
- Матрица Лапласа полного двудольного графа <math>K_{m,n}</math> имеет собственные значения <math>n+m</math>, <math>n</math>, <math>m</math>, <math>0</math> с кратностями <math>1</math>, <math>m-1</math>, <math>n-1</math> и <math>1</math> соответственно.
- Полный двудольный граф <math>K_{m,n}</math> имеет <math>m^{n-1}\cdot n^{m-1}</math> остовных деревьев.
- Полный двудольный граф <math>K_{m,n}</math> имеет максимальное паросочетание размера <math>\min(m, n)</math>.
- Полный двудольный граф <math>K_{n,n}</math> имеет подходящую <math>n</math>-рёберную раскраску, соответствующую латинскому квадрату.
Последние два результата являются следствием теоремы Холла, применённой к <math>k</math>-регулярному двудольному графу.
См. также
Литература
