Разрядный метод (дискретная математика)

Метод разряда — метод доказательства лемм структурной теории графов . ^[1] Разрядка наиболее известна своей центральной ролью в доказательстве теоремы о четырех цветах . Метод выгрузки используется для доказательства того, что каждый граф в определенном классе содержит некоторый подграф из заданного списка. Наличие искомого подграфа затем часто используется для доказательства результата раскраски . ^[1]

Чаще всего разрядку применяют к плоским графам .Первоначально заряд каждой грани и каждой вершине графа присваивается .Заряды распределяются так, что их сумма дает небольшое положительное число. Во время фазы разрядки заряд на каждой грани или вершине может быть перераспределен на соседние грани и вершины, как того требует набор правил разрядки. Однако каждое правило выписки сохраняет сумму начислений. Правила построены так, что после фазы разрядки каждая грань или вершина с положительным зарядом лежит в одном из нужных подграфов. Поскольку сумма зарядов положительна, какая-то грань или вершина должны иметь положительный заряд. Многие аргументы разрядки используют одну из нескольких стандартных функций начального заряда (они перечислены ниже). Успешное применение метода выписки требует творческой разработки правил выписки.

Пример

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

Теорема: Если планарный граф имеет минимальную степень 5, то он либо имеет реброс конечными точками как степени 5, так и один с конечными точками степени 5 и 6.

Доказательство: Мы используем $V$ , $F$ , и $E$ для обозначения наборов вершин, граней и ребер соответственно.Мы называем краевым светом , если его конечные точки имеют обе степени 5 или степени 5 и 6.Встроить график в плоскость. Для доказательства теоремы достаточно рассматривать только плоские триангуляции (поскольку, если она справедлива для триангуляции, при удалении узлов для возврата к исходному графу ни один узел с любой стороны от искомого ребра не может быть удален без уменьшения минимальной степени графика ниже 5). Мы произвольно добавляем ребра в граф, пока он не станет триангуляцией. Поскольку исходный граф имел минимальную степень 5, каждая конечная точка нового ребра имеет степень не менее 6. Итак, ни одно из новых ребер не является легким.Таким образом, если триангуляция содержит легкое ребро, то это ребро должно было находиться в исходном графе.

Мы даем заряд $6-d(v)$ к каждой вершине $v$ и заряд $6-2d(f)$ каждому лицу $f$ , где $d(x)$ обозначает степень вершины и длину грани. (Поскольку граф представляет собой триангуляцию, заряд на каждой грани равен 0.) Напомним, что сумма всех степеней графа равна удвоенному числу ребер; аналогично сумма длин всех граней равна удвоенному количеству ребер. Используя формулу Эйлера , легко увидеть, что сумма всех зарядов равна 12:

${\begin{aligned}\sum _{f\in F}6-2d(f)+\sum _{v\in V}6-d(v)=&\\6|F|-2(2|E|)+6|V|-2|E|=&\\6(|F|-|E|+|V|)=&&12.\end{aligned}}$

Мы используем только одно правило выгрузки:

Каждая вершина степени 5 дает заряд 1/5 каждому соседу.

Рассмотрим, какие вершины могут иметь положительный конечный заряд.Единственными вершинами с положительным начальным зарядом являются вершины степени 5. Каждая вершина степени 5 дает заряд 1/5 каждому соседу. Таким образом, каждой вершине придан суммарный заряд не более $d(v)/5$ . Начальный заряд каждой вершины v равен $6-d(v)$ . Итак, конечный заряд каждой вершины не более $6-4d(v)/5$ . Следовательно, вершина может иметь положительный конечный заряд только в том случае, если ее степень не превышает 7. Теперь мы покажем, что каждая вершина с положительным конечным зарядом примыкает к конечной точке легкого ребра.

Если вершина $v$ имеет степень 5 или 6 и имеет положительный конечный заряд, тогда $v$ получил заряд от соседней вершины 5-й степени $u$ , так что край $uv$ светлый. Если вершина $v$ имеет степень 7 и имеет положительный конечный заряд, тогда $v$ получил заряд как минимум от 6 смежных вершин 5-й степени. Поскольку граф представляет собой триангуляцию, вершины, прилегающие к $v$ должен образовывать цикл, и поскольку он имеет только степень 7, соседи степени 5 не могут быть разделены вершинами более высокой степени; хотя бы два из соседей 5-й степени $v$ должны быть соседними друг с другом в этом цикле. Это дает светлый край.

Ссылки

^ Перейти обратно: ^а ^б Крэнстон, Дэниел В.; Уэст, Дуглас Б. (1 апреля 2017 г.). «Введение в метод разрядки посредством раскраски графа» . Дискретная математика . 340 (4): 766–793. arXiv : 1306.4434 . дои : 10.1016/j.disc.2016.11.022 . ISSN 0012-365X . Проверено 25 февраля 2023 г.

Аппель, Кеннет ; Хакен, Вольфганг (1977), «Каждая плоская карта раскрашивается в четыре цвета. I. Разрядка», Illinois Journal of Mathematics , 21 : 429–490, doi : 10.1215/ijm/1256049011 .
Аппель, Кеннет ; Хакен, Вольфганг (1977), «Каждая плоская карта раскрашивается в четыре цвета. II. Сводимость», Illinois Journal of Mathematics , 21 : 491–567, doi : 10.1215/ijm/1256049012 .
Хлиненый, Петр (2000), Техника разрядки на практике . (Текст лекции для Весенней школы по комбинаторике).
Робертсон, Нил ; Сандерс, Дэниел П .; Сеймур, Пол ; Томас, Робин (1997), «Теорема о четырех цветах», Журнал комбинаторной теории, серия B , 70 : 2–44, doi : 10.1006/jctb.1997.1750 .
Вернике, П. (1904), «О картографической теореме о четырех цветах» (PDF) , Math. (на немецком языке), 58 (3): 413–426, doi : 10.1007/bf01444968 .

[10.1016_j.disc.2016.11.022-1] Перейти обратно: ^а ^б Крэнстон, Дэниел В.; Уэст, Дуглас Б. (1 апреля 2017 г.). «Введение в метод разрядки посредством раскраски графа» . Дискретная математика . 340 (4): 766–793. arXiv : 1306.4434 . дои : 10.1016/j.disc.2016.11.022 . ISSN 0012-365X . Проверено 25 февраля 2023 г.

[1]