Розуміння подвійних частин у теорії графів

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

Наприклад, розглянемо граф із 4 вершинами {a,b,c,d} і розділимо множину вершин на дві частини: {a,b} і {c,d}. Граф є дводольним, оскільки всі ребра з’єднують вершини з різних частин.

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