Сначала сделайте следующее наблюдение:
График G является двудольным тогда и только тогда, когда каждый цикл в графе является четным.
Доказательство:
Предположим, что существует нечетный цикл длины, а график четный.Затем рассмотрим цикл, определенный как v1, v2, ..., vn, где n = нечетное.Если мы возьмем G и разделим ее на два непересекающихся множества S1 и S2 так, что в S1 или S2 нет вершины, смежной с другой вершиной в его наборе, то получим, что мы чередуемся между наборами.Если мы начнем с S1, то мы чередуем S1, S2, S1, S2, ..., но, поскольку длина цикла нечетна, у нас будет n + 1 вершина и, следовательно, конец S1 и S2.Однако у нас было то, что S1 и S2 были непересекающимися множествами, что является противоречием.
Таким образом, мы доказали противоположность того, что двудольный граф подразумевает четный граф.
Другое направление заключается в том, что мы хотим показать, что график четного цикла подразумевает двудольный граф.Мы докажем еще раз, взяв противоположное, следовательно, если G не является двудольным, то мы имеем нечетный цикл.Рассмотрим компонент H такой, что H не является двудольным.Должен существовать компонент H, иначе у нас будет противоречие, поскольку мы можем произвольно добавлять компоненты в непересекающиеся множества.Следовательно, существует ребро {u, v}, такое что u, v оба существуют в одном непересекающемся множестве.Теперь, поскольку компонент связан (определен как максимальный связный граф), мы можем сгенерировать минимальное остовное дерево T. Поскольку T связно (по определению), существует путь между u и v. Однако, поскольку u, vв дереве и связанном, расстояние должно быть четным, так как мы можем сгенерировать двудольный граф из дерева.Поскольку существует ребро {u, v}, мы можем вызвать цикл, добавив ребро {u, v} + T. Это приводит к нечетному циклу длины.QED
Принимая это к сведению, мы можем сгенерировать простой алгоритм.Рассмотрим два набора, и мы можем взять каждый узел и добавить 3-кортеж, указывающий, присутствует ли узел в наборе S1, S2 или ни того, ни другого.Теперь для каждой комбинации мы запускаем алгоритм топологической сортировки или алгоритм нахождения одного цикла, который может найти наличие циклов.Для каждого цикла нам нужно определить, существует ли цикл нечетной длины, и в этом случае мы знаем, что выбранные наборы не работают.Естественно, это мотивирует решение O (3 ^ n), что не очень хорошо.Кроме того, необходимо также запустить алгоритм поиска цикла, добавив ребра в график, что может занять O (2n) времени на каждую итерацию - следовательно, O (3 ^ n * n)
Сложностьприходит в оптимизации этого алгоритма до полиномиального времени, но это будет начало.
Альтернативным решением было бы рассмотреть раскраску графа и попытаться жадно раскрасить узлы.Это также привело бы к решению O (3 ^ n * n), хотя и немного быстрее, чем обнаружение цикла.Однако, чтобы уменьшить сложность времени, подумайте о том, чтобы выполнить BFS (поиск в выдохе) на графике и попытаться жадно назначать цвета.При назначении цветов в любое время, когда есть обратный край для узла того же цвета, удалите этот текущий узел.Этот жадный алгоритм затем вернет количество ребер и даст время O (n).