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

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

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

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

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

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

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

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

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

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