Как проверить является ли неориентированный граф двудольным
Можете дать алгоритм , который определит можно ли перекрасить неориентированный граф в 2 цвета , или же просто алгоритм , который проверяет является ли неориентированный граф 2-цветым(двудольным)
Ответы (1 шт):
Есть простой алгоритм. Используете любой алгоритм (поиск в ширину или глубину), что бы пройти по всем вершинам. Каждую вершину при посещении разукрашиваете в белый или черный цвет (можно хранить отдельно массив с разукрашенными вершинами.
Правило раскраски - две соседние вершины должны быть разного цвета. То есть, если текущая белая, то соединенные с ней - черные. Если все вершины разукрасились - ура, наш граф двудольный. Если в процессе разукраски натолкнулись на уже покрашенную вершину и цвет совпал, ок, продолжаем. Если не совпал - нашли проблемное место, грав не двудольный.
Более строгое математическое определение - все циклы в таком графе - четные. (теорема Кенига).