Графовые задачи: существование, построение и точный подсчёт
Реализация степеней, маршруты, зависимости, раскраски, назначения и остовы с независимыми проверками результата.
Задачи модуля
Отделяйте решение о существовании от построения одного объекта и подсчёта всех объектов. Условия для эйлерова маршрута не отвечают на вопрос о числе остовов.
После конструкций переходите к оптимизации расписания. Предъявленный вариант проверяет допустимость, а минимальность или максимальность требует дополнительного аргумента.
Проверять степени, связность и использование каждого ребра в предъявленном объекте.
Сохранять достижимость DAG и доказывать минимальное число цветов.
Считать полные назначения и остовы, находить оптимальный вес совместимых интервалов.
Графовые сертификаты
Паросочетание и Холл: сертификат невозможности
Чтобы доказать невозможность назначить каждому объекту отдельного исполнителя, иногда достаточно найти маленькую группу объектов с недостаточным общим набором вариантов. Такой дефицит проверяется без полного поиска назначений.
Перед началом: Двудольный граф; Инъективное отображение.
Соседи группы ограничивают все назначения
В двудольном графе с левой долей L паросочетание, покрывающее L, назначает каждой левой вершине своего правого соседа. Для любого S⊆L все эти разные соседи должны лежать в N(S), поэтому необходимо |N(S)|≥|S|. Теорема Холла утверждает достаточность выполнения условия для всех S. Для опровержения достаточно одного нарушающего подмножества; проверять все остальные уже не нужно.
Дефицит даёт количественную верхнюю границу
Если |S|−|N(S)|=d>0, как минимум d левых вершин останутся непокрытыми в любом паросочетании. Следовательно, размер не больше |L|−d. Это не всегда точная граница для случайно выбранного S, но если предъявлено паросочетание такого размера, оптимальность доказана. Получается пара сертификатов: конкретные непересекающиеся рёбра снизу и дефицит соседей сверху. Ни один из них по отдельности не доказывает точный максимум.
Не проверяйте только степени отдельных вершин
Каждая вершина может иметь по два или больше соседей, но несколько вершин могут делить один и тот же маленький набор. Поэтому ненулевая степень не гарантирует полного назначения. Увеличивающие пути дают алгоритмический способ строить максимум, а достижимые множества после неудачного поиска помогают извлечь свидетельство дефицита. В небольшом примере можно независимо перебрать все частичные инъективные назначения. Если рёбра имеют стоимость, существование полного паросочетания и поиск самого дешёвого — разные задачи.
Свидетельство дефицита можно проверять без полного графа поиска: перечислите S, объедините все его соседства и сравните размеры. Пропуск хотя бы одного соседа делает верхнюю границу недоказанной, поэтому список N(S) должен быть полным, а не выбранным удобным подмножеством.
Четыре заявки и общие варианты
Условие. L={a,b,c,d}, справа {1,2,3,4}; a,b,c соединены с 1,2, а d с 3,4. Найдите максимум.
Возьмём S={a,b,c}; его соседи только {1,2}.
Дефицит равен 3−2=1, поэтому полный размер 4 невозможен и максимум не больше 3.
Рёбра a−1,b−2,d−3 образуют допустимое паросочетание размера 3.
Нижняя и верхняя границы совпали; c остаётся непокрытой в предъявленном варианте.
Ответ. Максимальный размер 3; свидетельство Холла S={a,b,c}.
Проверка. Все рёбра выбранного набора имеют разные концы, а никакое назначение трёх вершин S двум соседям не может быть инъективным.
Где легко ошибиться. Проверка числа соседей каждой вершины отдельно не заменяет условие для всех подмножеств.
Проверьте понимание
Вопросы к этой главе
Свидетельство дефицита всегда единственно?
Нет. Разные группы могут нарушать условие и давать одинаковые или разные верхние границы.
Почему d можно назначить 4 вместо 3?
Оба ребра существуют и не конфликтуют с остальными; оптимальное паросочетание не обязано быть единственным.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Раздел Hall’s Matching Theorem: соседство подмножеств; количественная граница дефицита выведена непосредственно. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Поток и разрез: две одинаковые величины доказывают оптимальность
Допустимый поток показывает, сколько можно передать, а разрез ограничивает любой возможный поток сверху. Совпадение этих чисел доказывает оптимальность без доверия к истории работы алгоритма.
Перед началом: Ориентированная сеть; Сохранение потока.
Проверьте допустимость по рёбрам и вершинам
Поток на каждом ребре должен лежать между нулём и пропускной способностью. Во внутренних вершинах суммарный вход равен выходу. Значение потока — чистый выход из источника, совпадающий с чистым входом в сток. Наличие циклической циркуляции может увеличить отдельные значения на рёбрах, но не доставку от источника к стоку. Поэтому суммировать все рёбра сети как общий объём нельзя.
Любой разрез даёт верхнюю оценку
Разделим вершины на S и T, где источник в S, сток в T. По сохранению значение потока равно потоку из S в T минус обратный. Оно не превосходит суммы пропускных способностей рёбер из S в T. Это слабая двойственность и непосредственно проверяемая граница. Обратные рёбра в ёмкость разреза не прибавляют. Если допустимый поток достигает этой границы, никакое улучшение невозможно независимо от выбранного алгоритма.
Остаточная сеть объясняет поиск сертификата
Остаточные прямые рёбра позволяют добавить поток, обратные — отменить прежний выбор. Отсутствие увеличивающего пути выделяет множество достижимых вершин, которое образует минимальный разрез. Но для проверки готового ответа не нужно повторять поиск: достаточно проверить сам поток и предъявленный разрез. Для целых ёмкостей существует целочисленный максимум; это не означает обязательной целочисленности каждой промежуточной модели с произвольными дополнительными ограничениями. Здесь рассматривается обычный однотоварный поток без стоимостей.
Сумма сохранений по вершинам S сокращает все внутренние рёбра попарно. Остаются только переходы через границу, что даёт прямое доказательство верхней оценки разреза без обращения к полному алгоритму максимального потока.
Разрез S={s} имеет ёмкость 4+3=7, значит любой поток не больше 7.
Ответ. Максимальный поток 7, доказан потоком и разрезом одинаковой величины.
Проверка. Суммарный вход в сток 2+5=7; полный перебор целых допустимых потоков не даёт большего значения.
Где легко ошибиться. В ёмкости ориентированного разреза учитываются только рёбра из стороны источника наружу, а не все пересекающие границу в обе стороны.
Проверьте понимание
Вопросы к этой главе
Зачем обратное ребро в остаточной сети?
Оно позволяет отменить часть прежнего потока и перенаправить её, не нарушая исходных ограничений.
Достаточно ли предъявить поток 7?
Это доказывает достижимость 7, но без верхней границы не исключает поток 8 или больше.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Сохранение потока, остаточная сеть и теорема о потоке и разрезе. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Эйлеров путь: степени недостаточно без связности
Маршрут, проходящий каждое ребро ровно один раз, определяется рёбрами, а не неповторением вершин. Чётные степени не помогут, если рёбра лежат в разных несвязанных компонентах.
Перед началом: Степень вершины; Неориентированный граф.
Вход и выход попарно расходуют рёбра
Во внутренней вершине открытого маршрута каждый приход сочетается с уходом, поэтому степень должна быть чётной. У двух разных концов степень нечётна. Для замкнутого эйлерова обхода нечётных вершин нет. Помимо этого, все вершины ненулевой степени должны принадлежать одной компоненте связности. Изолированные вершины не мешают пройти рёбра, но если требуется посетить и их, это уже дополнительная задача. Петля добавляет к степени два, поскольку имеет два конца в одной вершине.
Идентификаторы защищают от потери параллельных рёбер
Алгоритм Хиерхольцера проходит неиспользованные рёбра и при тупике добавляет вершины в обратный порядок ответа. Каждое ребро помечают по отдельному идентификатору. Два одинаковых соседа в списке могут соответствовать разным рёбрам и должны расходоваться отдельно. Если хранить только множество пар вершин, мультиграф незаметно превратится в простой граф. Проверка длины готового ответа должна дать число рёбер плюс один, но одной длины недостаточно без проверки идентификаторов.
Сертификат маршрута проверяется напрямую
Укажите последовательность рёбер и вершин. Для каждой пары соседних вершин проверьте соответствующее ребро, затем убедитесь, что каждый идентификатор использован ровно один раз. Это доказывает построение независимо от критерия существования. Напротив, список степеней и связность доказывают, что маршрут возможен, но не подтверждают конкретный ошибочно выписанный маршрут. Для ориентированного случая условия меняются на баланс входящих и исходящих степеней и подходящую связность; механический перенос чётности неверен.
Если в готовой записи одно параллельное ребро использовано дважды, правильная последовательность вершин может скрыть ошибку. Поэтому сертификат обязательно содержит и идентификаторы, а не только названия концов.
Раздел Euler tours: чётность и связность. Открытый маршрут мультиграфа проверен по идентификаторам рёбер. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Матричная теорема о деревьях: точный подсчёт через минор
Число остовных деревьев можно получить одним определителем лапласиана. Для небольшого графа полезно независимо перебрать наборы рёбер и увидеть, что именно считает этот определитель.
Перед началом: Определитель; Остовное дерево.
Лапласиан кодирует степени и соседство
Для простого неориентированного графа L=D−A: диагональ содержит степени, вне диагонали стоят минус единицы на рёбрах. Сумма каждой строки нулевая, поэтому полный определитель L равен нулю. Матричная теорема о деревьях использует любой главный минор размера n−1, то есть удаление одной строки и того же столбца. Все такие кофакторы равны числу остовных деревьев. Полный определитель вместо минора всегда дал бы неправильный нулевой ответ.
Связность проявляется в ранге
У связного графа ядро лапласиана состоит из постоянных векторов и имеет размерность один. У нескольких компонент можно выбрать независимые постоянные значения на каждой, и минор указанного размера обращается в нуль. Это согласуется с отсутствием остовного дерева всего графа. В мультиграфе веса соседства должны учитывать число параллельных рёбер: разные рёбра дают разные остовы. Петли в обычный неориентированный лапласиан для этой задачи не вносят вклад в соединение вершин.
Точный счёт требует точной арифметики
Определитель целочисленной матрицы является целым, но вычисление через плавающую точку может дать близкое нецелое число. Для сертификата лучше использовать целые преобразования или рациональные дроби. Независимый перебор выбирает n−1 ребро и проверяет связность: для такого числа рёбер связность уже обеспечивает отсутствие цикла. Это экспоненциальный способ, пригодный для проверки маленького случая, а не замена полиномиальной формуле на больших графах.
Выбор удалённой вершины может упростить арифметику: если у неё много связей, оставшийся минор иногда становится менее удобным, а иногда наоборот. Теорема разрешает выбирать свободно, но строка и столбец должны соответствовать одной вершине. Сравнение двух разных главных миноров даёт дополнительный контроль реализации определителя.
Квадрат с одной диагональю
Условие. Граф имеет рёбра 12,23,34,41,13. Посчитайте остовные деревья.
Степени равны 3,2,3,2. Удалим строку и столбец вершины 4.
Минор равен [[3,−1,−1],[−1,2,−1],[−1,−1,3]].
Его определитель равен 8.
Независимый счёт: без диагонали четыре остова; с диагональю нужно выбрать по одному из двух рёбер к вершинам 2 и 4, ещё четыре.
Ответ. Всего 8 остовных деревьев.
Проверка. Из десяти трёхрёберных подмножеств ровно два содержат треугольник и изолируют оставшуюся вершину; остальные восемь подходят.
Где легко ошибиться. Удалять нужно согласованную строку и столбец. Полный лапласиан всегда сингулярен и не даёт число деревьев своим определителем.
Проверьте понимание
Вопросы к этой главе
Почему достаточно n−1 ребра и связности?
Связный неориентированный граф на n вершинах с n−1 рёбрами является деревом.
Могут ли разные удалённые вершины дать разные ответы?
Нет. По теореме все главные кофакторы равны одному числу остовных деревьев.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Теорема 1: число остовных деревьев как главный кофактор лапласиана. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Хроматический многочлен: удалить или стянуть ребро
Правильные раскраски можно считать, разделив случаи по равенству цветов концов одного ребра. Удаление и стягивание образуют точную рекурсию, но полученные графы нужно трактовать согласованно.
Перед началом: Правильная раскраска; Полиномиальная рекурсия.
Разделите раскраски графа без ребра
Пусть e соединяет разные вершины u,v. В G−e допустимы раскраски с разными цветами u,v и с одинаковыми. Первые совпадают с правильными раскрасками G. Вторые соответствуют раскраскам G/e, где u,v объединены. Поэтому P_G(k)=P_(G−e)(k)−P_(G/e)(k). Цвета считаются различимыми: перестановка названий обычно даёт другую раскраску. Переход к раскраскам с точностью до перестановки цветов является другой задачей.
После стягивания обработайте кратность
Параллельные рёбра не меняют условие неравенства цветов и могут быть объединены в простом графе. Петля делает правильную раскраску невозможной, потому что потребовала бы цвет вершины отличаться от самого себя. Поэтому при рекурсии нельзя молча удалить возникшую петлю. Базовый граф без рёбер на n вершинах имеет kⁿ раскрасок. Для дерева последовательный выбор от корня даёт k(k−1)^(n−1), что часто ускоряет ручное вычисление.
Проверяйте значения и старшие коэффициенты
Хроматический многочлен графа на n вершинах имеет старшую степень n и коэффициент 1. Для простого графа следующий коэффициент равен минус числу рёбер. Это полезные проверки, но не доказательство всей формулы. Независимый перебор при маленьком целом k проверяет конкретное значение. Если полученный многочлен даёт отрицательное число при положительном целом k, где раскраски существуют, ошибка почти наверняка связана со знаком рекурсии или неверным стягиванием.
Коэффициенты многочлена не являются числами раскрасок по отдельности: среди них могут быть отрицательные. Неотрицательным целым должен быть результат при каждом неотрицательном целом числе доступных цветов. В нашем квадрате значение при k=1 равно нулю, потому что есть рёбра; при k=0 тоже нуль для непустого графа. Эти базовые проверки полезны, но не определяют весь многочлен без достаточного числа условий или рекурсивного доказательства.
Цикл из четырёх вершин
Условие. Получите P(k) для квадрата без диагоналей через одно ребро.
Удаление выбранного ребра оставляет путь на четырёх вершинах: k(k−1)³.
Стягивание этого ребра даёт треугольник: k(k−1)(k−2).
Вычитаем: P=k(k−1)[(k−1)²−(k−2)].
После раскрытия P=k⁴−4k³+6k²−3k; при k=3 получаем 18.
Раздел Deletion Contraction: разность многочленов, различимые цвета и обработка кратных рёбер. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Связанные методы
Чётной суммы мало: как построить граф по заданным степеням
Последовательность степеней задаёт ограничения на соседство, а не готовый граф. Чётная сумма является лишь необходимой проверкой. Метод Хавела — Хакими последовательно снимает максимальную степень, уменьшая степени выбранных соседей, и позволяет восстановить сами рёбра.
Как стек Хиерхольцера собирает маршрут из использованных рёбер
В эйлеровом маршруте ограничено повторение рёбер, а не вершин. Сначала проверяют связность части графа с рёбрами и число нечётных степеней. Затем строят маршрут, сохраняя возможность вернуться к ранее встреченной вершине через другие ещё не использованные рёбра.
Какая стрелка зависимости лишняя: сохранение всех достижимых пар
Избыточная прямая зависимость имеет обходной направленный путь между теми же концами. В ациклическом графе можно удалить такие дуги и сохранить достижимость, получив более короткую запись тех же отношений предшествования. Непосредственные соседи при этом меняются.