Двочастковий граф — Вікіпедія
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/220px-Simple-bipartite-graph.svg.png)
У математиці двочастковий граф (також біграф, двочастинний або дводольний граф) — граф, множину вершин якого можна розбити на дві підмножини, що не перетинаються, так, що кожне ребро графа має одну вершину з першої підмножини і одну з другої.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Complete_bipartite_graph_K3%2C2.svg/220px-Complete_bipartite_graph_K3%2C2.svg.png)
Неорієнтовний граф називається двочастковим, якщо множина його вершин розбита на дві підмножини [джерело?] так, що
- жодна вершина в не з'єднана з вершинами в і
- жодна вершина в не з'єднана з вершинами в
Двочастковий граф називається повним, якщо для кожної пари вершин існує ребро . Для
такий граф позначається
- Неорієнтований граф є двочастковим тоді й лише тоді, коли він не містить циклів непарної довжини[1][2].
- Граф є двочастковим тоді й лише тоді, коли його хроматичне число дорівнює 2[3].
- Усі дерева є двочастковими графами.
- Цикли з парною кількістю вершин є двочастковими графами.
- Планарний граф у якого всі грані мають парну кількість ребер.
- ↑ Asratian, Denley та Häggkvist, (1998), теорема 2.1.3, с. 8. Асратян та ін. віднесли цю характеристику до статті 1916 року Денеша Кеніга. Для нескінченних графів цей результат вимагає аксіоми вибору.
- ↑ Bang-Jensen, Jørgen; Gutin, Gregory (2001), Digraphs: Theory, Algorithms and Applications (PDF) (вид. 1st), с. 25, ISBN 9781852332686, архів (PDF) оригіналу за 2 січня 2023, процитовано 2 січня 2023
- ↑ 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 9780521593458