Рёберная раскраска: расписание уроков, Кёниг и Визинг

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

Как думаешь, сколько слотов нужно расписанию

В школе 30 учителей и 30 классов, всего 320 уроков «учитель ведёт в классе». Самый загруженный учитель (или класс) участвует в 15 уроках. Значит, слотов в неделе нужно не меньше 15.

Прежде чем читать дальше, ответь себе: а хватит ли ровно 15? Или неудачное сочетание - этот учитель занят тогда, когда свободен этот класс - заставит добавить слот? В прошлом уроке раскраска ВЕРШИН оказалась трудной уже для трёх цветов. С рёбрами двудольного графа всё иначе.

На что это похоже

Турнир по шахматам между двумя командами, где каждый играет с некоторыми из чужой команды. Тур - это набор партий, в котором никто не играет дважды. Если у лучшего игрока 15 соперников, туров не меньше 15. Организатор, раздающий партии по турам по порядку, рано или поздно упрётся: пара свободна в разные туры, общего свободного тура нет. Опытный организатор не добавляет тур, а ПЕРЕСТАВЛЯЕТ: меняет местами два тура у цепочки игроков, освобождая нужный тур у нужного человека.

Механизм: свободные цвета и чередующийся путь

у каждой вершины степени < Δ всегда есть свободный цвет из Δ

красим ребро u–v:
    a = цвет, свободный у u;   b = цвет, свободный у v
    если a свободен и у v → красим в a, готово
    иначе: из v идёт путь из рёбер цветов a, b, a, b, ...
           (у каждой вершины не больше одного ребра каждого цвета -
            путь однозначен)
           меняем на нём a ↔ b → a освободился у v
           красим u–v в a

Почему перекраска не испортит u. Путь начинается в v ребром цвета a, и стороны двудольного графа чередуются. На сторону u путь каждый раз приходит ребром цвета a. Если бы путь дошёл до u, то по ребру цвета a - но a у u свободен, такого ребра нет. Значит, путь до u не доходит, и после обмена у u цвет a по-прежнему свободен, а у v он освободился. Так каждое ребро красится в один из Δ цветов - это и есть теорема Кёнига. Время - O(E · V): на ребро не больше одного пути.

В графе с нечётными циклами путь МОЖЕТ вернуться к u, и Δ цветов не всегда хватает: треугольник имеет Δ = 2, а рёбер-то три, и все попарно соседние - нужно три цвета. Визинг доказал, что больше Δ + 1 не нужно никогда (для графов без кратных рёбер), но определить, Δ или Δ + 1, в общем случае так же трудно, как раскрасить вершины тремя цветами.

Правило

Рёберной раскраске нужно не меньше Δ цветов. В двудольном графе ровно Δ хватает всегда (Кёниг): ребро u–v красят цветом a, свободным у u; если a занят у v, на чередующемся пути цветов a/b из v их меняют местами - путь до u не дойдёт. В любом простом графе хватает Δ + 1 (Визинг), но различить Δ и Δ + 1 трудно. Жадная раскраска (наименьший цвет, свободный у обоих концов) гарантирует лишь 2Δ − 1.

Разбор: где жадность тратит лишний цвет

путь x – u – v – y – z, Δ = 2. Рёбра приходят в порядке:
    x–u  → цвет 0
    y–z  → цвет 0
    v–y  → у y занят 0 → цвет 1
    u–v  → у u занят 0, у v занят 1 → ЖАДНО: цвет 2

по Кёнигу для u–v: a = 1 (свободен у u), b = 0 (свободен у v).
    a = 1 занят у v → путь из v по цветам 1, 0, 1...: v –1– y –0– z
    меняем: v–y станет 0, y–z станет 1
    теперь 1 свободен у v → u–v красим в 1. Итого два цвета.

Жадность не ошиблась ни на одном шаге «локально» - она просто не умеет возвращаться. Перекраска вдоль пути - это и есть возврат, но ограниченный одной цепочкой.

Разбор: 320 уроков

Программа строит случайное расписание: 30 учителей, 30 классов, 320 уроков, которые приходят вразнобой. Красит жадно и по Кёнигу, проверяет, что у каждого учителя и класса все уроки в разных слотах, и сравнивает число слотов с Δ.

import random


def zhadno(rebra):                   # наименьший цвет, свободный у двух
    cvet, zanyato = {}, {}
    for u, v in rebra:
        c = 0
        while c in zanyato.get(u, ()) or c in zanyato.get(v, ()):
            c += 1
        cvet[u, v] = c
        zanyato.setdefault(u, set()).add(c)
        zanyato.setdefault(v, set()).add(c)
    return cvet


def kyonig(rebra, delta):            # двудольный граф: ровно Δ цветов
    po_cvetu = {}                    # (вершина, цвет) -> сосед по ребру
    def svoboden(x):
        return next(c for c in range(delta) if (x, c) not in po_cvetu)
    for u, v in rebra:
        a, b = svoboden(u), svoboden(v)
        if (v, a) in po_cvetu:       # a занят у v: меняем a и b на
            put, x, c = [], v, a     # чередующемся пути из v
            while (x, c) in po_cvetu:
                y = po_cvetu[x, c]
                put.append((x, y, c))
                x, c = y, (b if c == a else a)
            for x, y, c in put:
                del po_cvetu[x, c], po_cvetu[y, c]
            for x, y, c in put:
                d = b if c == a else a
                po_cvetu[x, d], po_cvetu[y, d] = y, x
        po_cvetu[u, a], po_cvetu[v, a] = v, u
    return {(u, v): c for (u, c), v in po_cvetu.items() if u[0] == "у"}


rng = random.Random(0)
uchitelya = [f"у{i}" for i in range(30)]
klassy = [f"к{i}" for i in range(30)]
rebra = sorted({(rng.choice(uchitelya), rng.choice(klassy))
                for _ in range(400)})
rng.shuffle(rebra)                   # уроки приходят вразнобой
stepen = {}
for u, v in rebra:
    stepen[u] = stepen.get(u, 0) + 1
    stepen[v] = stepen.get(v, 0) + 1
delta = max(stepen.values())
for imya, cvet in (("жадно", zhadno(rebra)),
                   ("Кёниг", kyonig(rebra, delta))):
    for x in stepen:                 # проверка: у вершины цвета разные
        u_x = [c for (u, v), c in cvet.items() if x in (u, v)]
        assert len(u_x) == len(set(u_x)) == stepen[x]
    print(f"{imya}: уроков {len(cvet)}, Δ = {delta},"
          f" слотов {max(cvet.values()) + 1}")

жадно: уроков 320, Δ = 15, слотов 16
Кёниг: уроков 320, Δ = 15, слотов 15

Жадность потратила лишний слот, перекраска уложилась ровно в нижнюю границу Δ = 15 - лучше нельзя в принципе. Обе раскраски правильные, проверка прошла у всех шестидесяти вершин.

Что ломается без этого

Первая ошибка - решать расписание жадно и считать, что раз слотов вышло Δ + 1, меньше нельзя: для двудольных задач (учитель - класс, станок - деталь, отправитель - получатель) оптимум всегда ровно Δ. Вторая - путать рёберную раскраску с вершинной и бояться трудности там, где её нет. Третья - перекрашивать путь и забыть, что в НЕдвудольном графе он может дойти до u: тогда обмен ломает раскраску у самой вершины, ради которой его затевали. Четвёртая - не учитывать, что Визинг верен для простых графов: при кратных рёбрах (два урока одного учителя в одном классе) цветов может понадобиться до 3Δ/2.

Зачем это в работе

Расписания уроков и экзаменов, распределение передач в сети по временным окнам (коммутатор не может одновременно передать из одного порта в два и принять в один порт из двух - это двудольный граф «вход - выход»), назначение частот в сетях, где канал - ребро между узлами. Круговой турнир на n команд (чётное n) - рёберная раскраска полного графа в n − 1 цвет: тур за туром, и его строят «методом круга» - одну команду фиксируют, остальные вращают. Знание, что для двудольного случая хватает Δ, превращает «а нельзя ли уложить в меньше слотов?» из споров в доказательство.

Теперь сам

Двудольный граф: A соединена с 1, 2, 3, B - с 1, 2, C - с 3. Чему равно Δ и как раскрасить рёбра в Δ цветов? Сколько цветов взяла бы жадность при порядке B–1, A–2, B–2, A–1, A–3, C–3?