Повний двочастковий граф

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

Визначення

Повний двочастковий граф $G:=(V_1+V_2,E)$ — це двочастковий граф, такий що для будь-яких двох вершин $v_1\in V_1$ і $v_2\in V_2$, $(v_1,v_2)$ є ребром в $G$. Повний двочастковий граф з частками розміру $|V_1|=m$ і $|V_2|=n$ позначається як. $K_{m,n}$.

Приклади

Графи-зірки $S_3$, $S_4$, $S_5$ і $S_6$.

Граф $K_{3,3}$.

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

Властивості

• Задача пошуку для даного двочасткового графа повного двочасткового підграфа $K_{m,n}$ NP-повна.
• Планарний граф не може містити $K_{3,3}$ як мінор графа. Зовніпланарний граф не може містити $K_{3,2}$ як мінор (Це недостатня умова планарності та зовнішньої планарності, а необхідна). І навпаки, будь-який непланарний граф містить або $K_{3,3}$, або повний граф $K_5$ як мінор (теорема Куратовського).
• Повні двочасткові графи $K_{n,n}$ є графами Мура і $(n,4)$-клітками.
• Повні двочасткові графи $K_{n,n}$ і $K_{n,n+1}$ є графами Турана.
• Повний двочастковий граф $K_{m,n}$ має розмір вершинного покриття, рівний $\min (m,n)$ і розмір реберного покриття, що дорівнює $\max (m,n)$.
• Повний двочастковий граф $K_{m,n}$ має максимальну незалежну множину розміром $\max (m,n)$.
• Матриця суміжності повного двочасткового графа $K_{m,n}$ має власні значення $\sqrt{nm}$, $-\sqrt{nm}$ і $0$ із кратностями $1$, $1$ і $n+m-2$ відповідно.
• Матриця Лапласа повного двочасткового графа $K_{m,n}$ має власні значення $n+m$, $n$, $m$, $0$ із кратностями $1$, $m-1$, $n-1$ і $1$ відповідно.
• Повний двочастковий граф $K_{m,n}$ має $m^{n-1}\cdot n^{m-1}$ кістякових дерев.
• Повний двочастковий граф $K_{m,n}$ має максимальне парування розміру $\min (m,n)$.
• Повний двочастковий граф $K_{n,n}$ має підхоже $n$-реберне розфарбування, яке відповідає латинському квадрату.

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

Див. також

• Вільний від біклік граф
• Двогранний граф
• Двочасткова розмірність
• Корона
• Цикл
• Шлях