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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Полный двудольный граф с m=5 и n=3
автоморфизмы = \left\{\begin{array}{ll}2 m! 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 \wedge 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{n m})^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}.

Свойства[править | править вики-текст]

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]