Определите, можно ли раскрасить неориентированный график, используя только 2 цвета

Question

Любые подсказки, как вы можете определить, можно ли раскрасить неориентированный график только двумя цветами?Как это может быть реализовано в Java?

Answer 1

Выполните поиск в ширину на графике.На каждой четной глубине закрасьте узлы одним цветом, скажем, красным, а на нечетной глубине вы закрасите узлы синим цветом.Каждый раз, когда у вас есть не дерево (ребро между двумя узлами, которые вы уже посетили), убедитесь, что цвета разные.Если на графике есть несколько связанных компонентов, вы просто повторяете поиск по каждому компоненту.

Answer 2

Это то же самое, что определить, является ли график двудольным. Чтобы сделать это, вы должны проверить, существует ли какой-либо цикл нечетной длины в графе. Для этого вы делаете поиск в ширину на графике. Если на каком-либо уровне в BFS существует какое-либо ребро между узлами одного и того же уровня, то график не является двудольным, то есть его нельзя раскрасить, используя только 2 цвета. (Предполагается, что соседние узлы должны быть разных цветов)