Проверка, Является Ли Неориентированный Граф Двудольным

2021/01/05 – В предыдущем примере кода C# алгоритм был реализован неправильно. На его место была добавлена исправленная реализация Java.

Если вы не знакомы с графиками, ознакомьтесь с некоторыми из моих предыдущих сообщений о них.

Ресурсы:

1. Видео-объяснение
2. Краткий обзор видео (клип в увеличенном видео)
3. Объяснение

Еда на вынос:

• Двудольный граф (биография) – это граф, вершины которого можно разделить на два непересекающихся, независимых множества u и v . Каждое ребро будет соединять вершину из одного набора с другим (без самосоединяющихся ребер – т.Е. ребер, идущих из вершины в u в другую вершину в u ).
• Один из способов визуализации двудольного графа – это покрасить все вершины в наборе в один и тот же цвет. Набор u может быть красными вершинами, тогда как v может быть черным. Это означало бы, что ребро всегда будет состоять из пары красных и черных вершин.
• Этот тип двухцветности невозможен в недвойственных графах. Представьте себе график с тремя вершинами, расположенными в треугольнике. Мы не можем представить этот график в виде двух независимых наборов, и мы не можем раскрасить его таким образом, чтобы каждое ребро имело разные конечные точки.
• Один из способов, которым мы можем проверить, является ли граф двудольным, – это выполнить поиск по глубине (DFS) по вершинам. Нанесение двух цветов на график.
  • Начните со случайной вершины v и раскрасьте его в цвет 1 (красный, например).
  • Раскрасьте все соседние вершины u противоположным цветом v . Для каждого соседнего u также рекурсивно вызовите нашу процедуру DFS.
  • Если граф двудольный, мы можем завершить это двухцветие без противоречия.
  • Если граф не двудольный, то в какой-то момент вершина получит оба цвета – и это противоречие означает, что мы не можем добиться двухцветности графика.
• Временная сложность равна O(v + e) для списка смежности. Сложность пространства равна O(v) . Для матрицы смежности сложность времени и пространства будет O(v^2) .

Неориентированный график, который может быть двухцветным:

Неориентированный график, который не может быть двухцветным:

Ниже приведены реализации для проверки того, являются ли неориентированные графики двудольными. Существуют решения как для неориентированного списка смежности, так и для представления матриц смежности графов:

Как всегда, если вы обнаружили какие-либо ошибки в этом посте, пожалуйста, дайте мне знать!

Оригинал: “https://dev.to/jjb/part-21-checking-if-an-undirected-graph-is-bipartite-2n2d”