Раскраска графа в два цвета: различия между версиями
Материал из Algocode wiki
Глеб (обсуждение | вклад) (Новая страница: «Корректной раскраской графа в два цвета назывется такая раскраска, что никакое ребро не...») |
Глеб (обсуждение | вклад) |
||
Строка 2: | Строка 2: | ||
С помощью обхода графа легко проверить граф на двудольность и даже вывести цвет каждой вершины - достаточно запустить dfs и просто красить вершины, 1 - в первый, все в которые ведут ребра во второй, затем снова в первый и так далее. | С помощью обхода графа легко проверить граф на двудольность и даже вывести цвет каждой вершины - достаточно запустить dfs и просто красить вершины, 1 - в первый, все в которые ведут ребра во второй, затем снова в первый и так далее. | ||
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 13:31, 26 сентября 2019
Корректной раскраской графа в два цвета назывется такая раскраска, что никакое ребро не соединяет две вершины одного цвета. Графы, которые можно так раскрасить, называют еще двудольными.
С помощью обхода графа легко проверить граф на двудольность и даже вывести цвет каждой вершины - достаточно запустить dfs и просто красить вершины, 1 - в первый, все в которые ведут ребра во второй, затем снова в первый и так далее.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin