Розуміння дводольних графів: визначення та приклади

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

Наприклад, граф із двома непересічними кліками (тобто двома непересічними множинами вершин, усі з’єднані одна з одною) є дводольним графом.