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

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

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

ВизначенняРедагувати

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

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

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

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

 

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

ВластивостіРедагувати

  • Граф є двочастковим тоді й лише тоді, коли він не містить циклів непарної довжини.
  • Граф є двочастковим тоді й лише тоді, коли його хроматичне число дорівнює 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.