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

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

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

Визначення

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

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

• жодна вершина в $U$ не з'єднана з вершинами в $U$ і
• жодна вершина в $V$ не з'єднана з вершинами в $V$

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

$|U|=i,|V|=j$

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

Властивості

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

Приклади

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

Див. також

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

Джерела

• Chartrand, G. Introductory Graph Theory. New York: Dover, 1985.
• Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.
• Шаблон:Citation