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

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

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

Визначення[ред. | ред. код]

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

Приклади[ред. | ред. код]

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

Властивості[ред. | ред. код]

  • Задача пошука для даного дводольного графа повного дводольного підграфа 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.