Раскраска графа: жадный алгоритм и почему задача NP-полна

Коротко

Постановка

Раскрасить вершины графа так, чтобы соседние имели разные цвета, использовав минимальное число цветов. Это минимальное число называется хроматическим числом.

Практический смысл:

• расписание экзаменов: вершины — экзамены, ребро — общий студент, цвета — временные слоты;
• распределение регистров в компиляторе: переменные, живущие одновременно, соединены ребром;
• частоты в сотовой связи: соседние вышки не должны использовать одну частоту;
• судоку — частный случай раскраски в 9 цветов.

Граница сложности

Здесь тот же эффект, что в 2-SAT против 3-SAT.

Два цвета — задача решается за линейное время: граф раскрашивается в два цвета тогда и только тогда, когда он двудолен, а это проверяется обходом в ширину.

Три цвета — уже NP-полная задача. Полиномиального алгоритма не известно.

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

Жадный алгоритм

Идём по вершинам и назначаем каждой минимальный цвет, не занятый соседями.

def greedy_coloring(graph: dict, order: list = None) -> dict:
    if order is None:
        order = list(graph)

    color = {}

    for v in order:
        used = {color[u] for u in graph[v] if u in color}
        c = 0
        while c in used:
            c += 1
        color[v] = c

    return color


graph = {
    1: [2, 3],
    2: [1, 3],
    3: [1, 2, 4],
    4: [3],
}

coloring = greedy_coloring(graph)
print(coloring)                       # {1: 0, 2: 1, 3: 2, 4: 0}
print('цветов:', max(coloring.values()) + 1)   # 3

Жадный алгоритм гарантирует не более Δ + 1 цветов, где Δ — максимальная степень вершины. Но оптимальным он не бывает.

Порядок вершин решает всё

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

Практичная эвристика — сортировка по убыванию степени (алгоритм Уэлша-Пауэлла): сначала красим вершины с наибольшим числом соседей, у них меньше свободы.

def welsh_powell(graph: dict) -> dict:
    order = sorted(graph, key=lambda v: len(graph[v]), reverse=True)
    return greedy_coloring(graph, order)

Более сильная эвристика — DSATUR: на каждом шаге выбирается вершина с максимальным числом различных цветов среди соседей. Она даёт оптимальный результат на многих классах графов.

def dsatur(graph: dict) -> dict:
    color = {}
    uncolored = set(graph)

    while uncolored:
        # вершина с максимальной насыщенностью, ничьи по степени
        v = max(uncolored, key=lambda x: (
            len({color[u] for u in graph[x] if u in color}),
            len(graph[x]),
        ))

        used = {color[u] for u in graph[v] if u in color}
        c = 0
        while c in used:
            c += 1

        color[v] = c
        uncolored.remove(v)

    return color


print(dsatur(graph))

Точное решение перебором

При малом числе вершин (до 20) хроматическое число находится динамическим программированием по подмножествам.

def chromatic_number(n: int, adjacency: list[int]) -> int:
    """adjacency[i] — битовая маска соседей вершины i."""
    full = (1 << n) - 1

    # независимые множества
    independent = []
    for mask in range(1 << n):
        ok = True
        m = mask
        while m:
            v = (m & -m).bit_length() - 1
            if adjacency[v] & mask:
                ok = False
                break
            m &= m - 1
        if ok:
            independent.append(mask)

    INF = float('inf')
    dp = [INF] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == INF:
            continue
        rest = full ^ mask
        for ind in independent:
            if ind and (ind & rest) == ind:
                dp[mask | ind] = min(dp[mask | ind], dp[mask] + 1)

    return dp[full]


# треугольник: нужно 3 цвета
adj = [0b110, 0b101, 0b011]
print(chromatic_number(3, adj))   # 3

Идея: каждый цвет — это независимое множество вершин. Задача сводится к покрытию всех вершин минимальным числом независимых множеств.

Известные результаты

Теорема о четырёх красках. Любой планарный граф раскрашивается в 4 цвета. Доказана в 1976 году с помощью компьютера — первое такое доказательство в истории математики.

Теорема Брукса. Для связного графа, не являющегося полным и не циклом нечётной длины, хроматическое число не превышает Δ.

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

Частые ошибки

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

Игнорирование порядка вершин. Разница между случайным порядком и DSATUR бывает существенной.

Попытка решить точно при большом n. Перебор подмножеств работает до n ≈ 20.

Путаница раскраски вершин и рёбер. Раскраска рёбер — отдельная задача со своими теоремами (теорема Визинга).

Что запомнить

• Хроматическое число — минимум цветов, при котором соседи различаются.
• Два цвета проверяются за O(V + E) через двудольность, три цвета — уже NP-полная задача.
• Жадный алгоритм даёт не более Δ + 1 цветов, но не оптимален.
• Порядок вершин критичен: сортировка по степени и DSATUR заметно улучшают результат.
• Точное решение — ДП по подмножествам, применимо до 20 вершин.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→