У математиці двочастковий граф (також біграф, двочастинний або дводольний граф) — граф, множину вершин якого можна розбити на дві підмножини, що не перетинаються, так, що кожне ребро графа має одну вершину з першої підмножини і одну з другої.
Визначення
Неорієнтовний граф називається двочастковим, якщо множина його вершин розбита на дві підмножини [] так, що
- жодна вершина в не з'єднана з вершинами в і
- жодна вершина в не з'єднана з вершинами в
Двочастковий граф називається повним, якщо для кожної пари вершин існує ребро . Для
такий граф позначається
Властивості
- Неорієнтований граф є двочастковим тоді й лише тоді, коли він не містить циклів непарної довжини.
- Граф є двочастковим тоді й лише тоді, коли його хроматичне число дорівнює 2.
Приклади
- Усі дерева є двочастковими графами.
- Цикли з парною кількістю вершин є двочастковими графами.
- Планарний граф у якого всі грані мають парну кількість ребер.
Див. також
Примітки
- 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 , (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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U matematici dvochastkovij graf takozh bigraf dvochastinnij abo dvodolnij graf graf mnozhinu vershin yakogo mozhna rozbiti na dvi pidmnozhini sho ne peretinayutsya tak sho kozhne rebro grafa maye odnu vershinu z pershoyi pidmnozhini i odnu z drugoyi Priklad dvochastkovogo grafaViznachennyaPovnij dvochastkovij graf K 3 2 displaystyle K 3 2 Neoriyentovnij graf G W E displaystyle G W E nazivayetsya dvochastkovim yaksho mnozhina jogo vershin rozbita na dvi pidmnozhini U V W U gt 0 V gt 0 displaystyle U cup V W quad U gt 0 V gt 0 dzherelo tak sho zhodna vershina v U displaystyle U ne z yednana z vershinami v U displaystyle U i zhodna vershina v V displaystyle V ne z yednana z vershinami v V displaystyle V Dvochastkovij graf nazivayetsya povnim yaksho dlya kozhnoyi pari vershin u U v V displaystyle u in U v in V isnuye rebro u v E displaystyle u v in E Dlya U i V j displaystyle U i V j takij graf poznachayetsya K i j displaystyle K i j VlastivostiNeoriyentovanij graf ye dvochastkovim todi j lishe todi koli vin ne mistit cikliv neparnoyi dovzhini Graf ye dvochastkovim todi j lishe todi koli jogo hromatichne chislo dorivnyuye 2 PrikladiUsi dereva ye dvochastkovimi grafami Cikli z parnoyu kilkistyu vershin ye dvochastkovimi grafami Planarnij graf u yakogo vsi grani mayut parnu kilkist reber Div takozhTeorema Holla Dvochastkova rozmirnist Majzhe mnogokutnik Graf Mejnelya Graf parnostiPrimitkiAsratian Denley ta Haggkvist 1998 teorema 2 1 3 s 8 Asratyan ta in vidnesli cyu harakteristiku do statti 1916 roku Denesha Keniga Dlya neskinchennih grafiv cej rezultat vimagaye aksiomi viboru Bang Jensen Jorgen Gutin Gregory 2001 Digraphs Theory Algorithms and Applications PDF vid 1st s 25 ISBN 9781852332686 PDF originalu za 2 sichnya 2023 procitovano 2 sichnya 2023 Asratian Denley ta Haggkvist 1998 s 7 DzherelaChartrand 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 Haggkvist Roland 1998 Bipartite Graphs and their Applications Cambridge Tracts in Mathematics t 131 Cambridge University Press ISBN 9780521593458