Двочастковий граф

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

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

Визначення

Повний двочастковий граф ${\displaystyle K_{3,2}}$

Неорієнтовний граф ${\displaystyle G=(W,E)\,}$ називається двочастковим, якщо множина його вершин розбита на дві непорожні підмножини ${\displaystyle U\cup V=W,}$^{[джерело?]} так, що

• жодна вершина в ${\displaystyle U\,}$ не з'єднана з вершинами в ${\displaystyle U\,}$ і
• жодна вершина в ${\displaystyle V\,}$ не з'єднана з вершинами в ${\displaystyle V\,}$

Двочастковий граф називається повним, якщо для кожної пари вершин ${\displaystyle u\in U,v\in V}$ існує ребро ${\displaystyle (u,v)\in E}$. Для

${\displaystyle |U|=i,|V|=j\,}$

такий граф позначається ${\displaystyle K_{i,j}\,}$

Властивості

• Неорієнтований граф є двочастковим тоді й лише тоді, коли він не містить циклів непарної довжини^[1][2].
• Граф є двочастковим тоді й лише тоді, коли його хроматичне число дорівнює 2^[3].

Приклади

• Усі дерева є двочастковими графами.
• Цикли з парною кількістю вершин є двочастковими графами.
• Планарний граф у якого всі грані мають парну кількість ребер.

Див. також

• Теорема Холла
• Двочасткова розмірність
• Майже многокутник
• Граф Мейнеля
• Граф парності