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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Полный двудольный граф с и
автоморфизмы =
вершин =
рёбер =
хроматическое число = 2
хроматический индекс =
радиус =
диаметр =
обхват ==
спектр =
обозначение =

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

Определение[править | править вики-текст]

Полный двудольный граф  — это такой двудольный граф, что для любых двух вершин и , является ребром в . Полный двудольный граф с долями размера и обозначается как .

Примеры[править | править вики-текст]

Графы-звёзды , , и .
Граф .
  • Графы называются звёздами, все полные двудольные графы, являющиеся деревьями, являются звёздами.
  • Граф называется клешнёй и используется для определения графов без клешней.
  • Граф иногда называется «коммунальным графом», название восходит к классической задаче «домики и колодцы», в современной интерпретации использующей «коммунальную» формулировку (подключить три домика к водо-, электро- и газоснабжению без пересечений линий на плоскости); задача неразрешима ввиду непланарности графа .

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

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

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

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