Есть связанный ненаправленный граф. Необходимо разбить рёбра графа на 3 множества (А, Б, В), т.ч. никакое ребро из А не было смежным (не имело общих вершин) с никаким ребром из В. Рёбра из Б, соотв., могут быть смежными и с А, и с В.
Если представить графически, то надо "разрезать" граф по некоторым рёбрам на 2 части.
При этом желательно минимизировать размер множества Б, а размер А и В был примерно одинаковым. Т.е. в идеале |А|=~N/2, |В|=~N/2, |Б|=~1.
Идеальная точность не нужна, а время выполнения критично. В идеале подошёл бы какой-нибудь жадный алгоритм. Есть что-нибудь такое?