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

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

Повний двочастковий граф
Повний двочастковий граф із m = 5 та n = 3
(Вершин)	n + m
(Ребер)	mn
(Радіус)	${\displaystyle \left\{{\begin{array}{ll}1&m=1\vee n=1\\2&m\neq 1\wedge n\neq 1\end{array}}\right.}$
(Діаметр)	${\displaystyle \left\{{\begin{array}{ll}1&m=n=1\\2&m\neq 1\wedge n\neq 1\end{array}}\right.}$
(Обхват)	${\displaystyle \left\{{\begin{array}{ll}\infty &m=1\vee n=1\\4&m\neq 1\wedge n\neq 1\end{array}}\right.}$
(Автоморфізм)	${\displaystyle \left\{{\begin{array}{ll}2m!n!&n=m\\m!n!&m\neq n\end{array}}\right.}$
Хроматичне число	2
Хроматичний індекс	max{m, n}
Спектр	${\displaystyle \{0^{n+m-2},(\pm {\sqrt {nm}})^{1}\}}$
Позначення	${\displaystyle K_{m,n}}$

Визначення

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

Приклади

Графи-зірки ${\displaystyle S_{3}}$, ${\displaystyle S_{4}}$, ${\displaystyle S_{5}}$ і ${\displaystyle S_{6}}$.

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

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

Властивості

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

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

Див. також

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

Примітки

1. ; (1976), Graph Theory with Applications, North-Holland, с. 5, ISBN .
2. Diestel, Reinhard (2005), Graph Theory (вид. 3rd), , ISBN . Electronic edition, page 17.