Подготовка к зачёту. Май 2024



Двудольный граф
 
Двудольный граф - граф, вершины которого можно разбить на два множества так, что каждое ребро соединяет вершины из разных множеств.


Часто в контексте двудольных графов используется понятие цвета вершины. Разбитие графа на две доли называется покраской его вершин в два различных цвета. Каждое ребро должно соединять вершины различного цвета.

Для проверки графа на двудольность и разбития его на доли чаще всего используется DFS
 

Алгоритм

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


Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация