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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Приклад двочасткового графа

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

Визначення[ред. | ред. код]

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

Неорієнтовний граф називається двочастковим, якщо множина його вершин розбита на дві підмножини [джерело?] так, що

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

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

такий граф позначається

Властивості[ред. | ред. код]

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

Приклади[ред. | ред. код]

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

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

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