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

Повний дводольний граф (бікліка) — спеціальний вид дводольного графа, у якого будь-яка вершина першої частки з'єднана з усіма вершинами другої частки вершин.[1][2]

Повний дводольний граф
Biclique K 3 5.svg
Повний дводольний граф з m = 5 та n = 3
Вершин n + m
Ребер mn
Радіус
Діаметр
Обхват
Автоморфізм
Хроматичне число 2
Хроматичний індекс max{m, n}
Позначення

ВизначенняРедагувати

Повний дводольний граф   — це дводольний граф, такий що для будь-яких двох вершин   і  ,   є ребром в  . Повний дводольний граф з частками розміру   і   позначається як.  .

ПрикладиРедагувати

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

ВластивостіРедагувати

  • Задача пошука для даного дводольного графа повного дводольного підграфа   NP-повна.
  • Планарний граф не може містити   як мінор графа. Зовнішньопланарний граф не може містити   як мінор (Це недостатня умова планарності та зовнішньої планарності, а необхідна). І навпаки, будь-який непланарний граф містить або  , або повний граф   як мінор (теорема Куратовського).
  • Повні дводольні графи   є графами Мура і  -клітинами.
  • Повні дводольні графи   і   є графами Турана.
  • Повний дводольний граф   має розмір вершинного покриття, рівний   і розмір реберного покриття, що дорівнює  .
  • Повний дводольний граф   має максимальну незалежну множину розміром  .
  • Матриця суміжності повного дводольного графа   має власні значення  ,   і   із кратностями  ,   і   відповідно.
  • Матриця Лапласа повного дводольного графа   має власні значення  ,  ,  ,   із кратностями  ,  ,   і   відповідно.
  • Повний дводольний граф   має   кістякових дерев.
  • Повний дводольний граф   має максимальне паропоєднання розміру  .
  • Повний дводольний граф   має підходяще  -реберне розфарбування, яке відповідає латинському квадрату.

Останні два результати є наслідком теореми Холла, застосованої до  -регулярного дводольного графа.

Див. такожРедагувати

ПриміткиРедагувати

  1. Bondy, John Adrian; Murty, U. S. R. (1976). Graph Theory with Applications. North-Holland. с. 5. ISBN 0-444-19451-7. .
  2. Diestel, Reinhard (2005). Graph Theory (вид. 3rd). Springer. ISBN 3-540-26182-6. . Electronic edition, page 17.