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

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

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

Визначення

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

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

• жодна вершина в ${\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}\,}$

Властивості

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

Приклади

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

Див. також

• Теорема Холла
• (Майже многокутник)
• (Граф Мейнеля)
• (Граф парності)

Примітки

1. Asratian, Denley та Häggkvist, (1998), теорема 2.1.3, с. 8. Асратян та ін. віднесли цю характеристику до статті 1916 року Денеша Кеніга. Для нескінченних графів цей результат вимагає аксіоми вибору.
2. Bang-Jensen, Jørgen; Gutin, Gregory (2001), Digraphs: Theory, Algorithms and Applications (PDF) (вид. 1st), с. 25, ISBN , (PDF) оригіналу за 2 січня 2023, процитовано 2 січня 2023
3. Asratian, Denley та Häggkvist, (1998, с. 7)

Джерела

• 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.
• Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, т. 131, Cambridge University Press, ISBN