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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Полный двудольный граф с 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 := (V1 + V2, E) – это двудольный граф, такой что для любых двух вершин v1V1 и v2V2 (v1v2) является ребром в G. Полный двудольный граф с долями размера |V1|=m и |V2|=n обозначается как Km,n.

Примеры[править | править исходный текст]

Графы-звезды S3, S4, S5 и S6.
Граф использования ресурсов K3,3
  • Для любого k, K1,k называется звездой. Все полные двудольные графы, являющиеся деревьями, являются звёздами.
  • Граф K1,3 называется клешнёй и используется для определения графов без клешней.
  • Граф K3,3 называется графом ресурсов. Название восходит к математической головоломке, в которой три различных ресурса должны быть подключены к трём зданиям. Задачу невозможно решить без пересечения подводки ресурсов ввиду непланарности графа K3,3.

Свойства[править | править исходный текст]

Смотрите также[править | править исходный текст]

Ссылки[править | править исходный текст]