Двудольные графы и раскраски

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

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

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

const int maxn = 1e5;
int color[maxn];

void dfs(int v, int col) {
    color[v] = col;
    for (int u : g[v]) {
        if (!color[u]) {
            dfs(u, -col);
        } else if (color[u] != -col) {
            cout << "Graph is not bipartite" << endl;
            exit(0);
        }
    }
}

Так как граф может быть несвязным, его возможно придется запускать много раз от разных вершин:

for (int v = 0; v < n; v++)
    if (!color[v])
        dfs(v, 1);

Так как мы просмотрим каждую вершину и каждое ребро по одному разу, асимптотика будет $O(n + m)$.

#Полезные утверждения про раскраски графов

Хроматическим числом графа называется минимальное число цветов, в которые его можно корректно раскрасить. В общем случае задача нахождения хроматического числа не решается за полиномиальное время.

Однако про раскраски можно доказать некоторые полезные утверждения, например:

• Граф можно раскрасить в два цвета — или, что эквивалентно, граф является двудольным — тогда и только тогда, когда все его простые циклы имеют чётную длину.
• Если степень любой вершины не превосходит $k$, то граф можно раскрасить в $k$ цветов.
• Любое планарный граф возможно раскрасить в 4 цвета.

Рекомендуем в качестве упражнения доказать первые два утверждения; последнее же пока умеют доказывать только на компьютере.