Понимание двуразделений в теории графов

В теории графов двуразделение графа — это разделение его множества вершин на два непересекающихся множества (называемых раздельными множествами), так что все ребра соединяют вершины из разных раздельных множеств. Другими словами, между вершинами одного и того же раздельного множества нет ребер.

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