Метод разрядки (дискретная математика)

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

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

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

Пример

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

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

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

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

${\begin{align}\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{align}}$

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

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

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

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

Ссылки

^ ab Cranston, Daniel W.; West, Douglas B. (1 апреля 2017 г.). «Введение в метод разрядки с помощью раскраски графа». Дискретная математика . 340 (4): 766– 793. arXiv : 1306.4434 . doi : 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), "Über den kartographischen Vierfarbensatz", Math. Энн. (на немецком языке), 58 (3): 413–426 , doi : 10.1007/bf01444968..

[10.1016_j.disc.2016.11.022-1] Cranston, Daniel W.; West, Douglas B. (1 апреля 2017 г.). «Введение в метод разрядки с помощью раскраски графа». Дискретная математика . 340 (4): 766– 793. arXiv : 1306.4434 . doi : 10.1016/j.disc.2016.11.022. ISSN 0012-365X . Получено 25 февраля 2023 г.