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

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

Полный двудольный граф с и
автоморфизмы =
вершин =
рёбер =
хроматическое число = 2
хроматический индекс =
радиус =
диаметр =
обхват ==
спектр =
обозначение =

ОпределениеПравить

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

ПримерыПравить

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

СвойстваПравить

  • Задача поиска для данного двудольного графа полного двудольного подграфа   с заданным параметром   NP-полна.
  • Планарный граф не может содержать   в качестве минора графа. Внешнепланарный граф не может содержать   в качестве минора (Это не достаточное условие планарности и внешней планарности, а необходимое). И наоборот, любой непланарный граф содержит либо  , либо полный граф   в качестве минора (Теорема Понтрягина — Куратовского).
  • Полные двудольные графы   являются графами Мура и  -клетками.
  • Полные двудольные графы   и   являются графами Турана.
  • Полный двудольный граф   имеет размер вершинного покрытия, равный   и размер рёберного покрытия, равный  .
  • Полный двудольный граф   имеет максимальное независимое множество размером  .
  • Матрица смежности полного двудольного графа   имеет собственные значения  ,   и   с кратностями  ,   и   соответственно.
  • Матрица Лапласа полного двудольного графа   имеет собственные значения  ,  ,  ,   с кратностями  ,  ,   и   соответственно.
  • Полный двудольный граф   имеет   остовных деревьев.
  • Полный двудольный граф   имеет максимальное паросочетание размера  .
  • Полный двудольный граф   имеет подходящую  -рёберную раскраску, соответствующую латинскому квадрату.

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

См. такжеПравить

ЛитератураПравить