Раскраска графа в два цвета: различия между версиями

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

Текущая версия на 16:31, 26 сентября 2019

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

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



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

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