Дводольний граф

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

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

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

Повний дводольний граф K_{3,2}

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

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

Дводольний граф називається повним, якщо для кожної пари вершин u \in U, v \in V існує ребро (u,v) \in E. Для

|U|=i, |V|=j \,

такий граф позначається K_{i, j} \,

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

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