Раскраска графа в два цвета

Материал из Algocode wiki
Версия от 16:29, 26 сентября 2019; Глеб (обсуждение | вклад) (Новая страница: «Корректной раскраской графа в два цвета назывется такая раскраска, что никакое ребро не...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Корректной раскраской графа в два цвета назывется такая раскраска, что никакое ребро не соединяет две вершины одного цвета. Графы, которые можно так раскрасить, называют еще двудольными.

С помощью обхода графа легко проверить граф на двудольность и даже вывести цвет каждой вершины - достаточно запустить dfs и просто красить вершины, 1 - в первый, все в которые ведут ребра во второй, затем снова в первый и так далее.