Проверка на двудольность

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

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

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



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin