Метод разряда (дискретная математика) - Discharging method (discrete mathematics)

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

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

Пример

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

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

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

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

${ Displaystyle { 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 каждому соседу. Таким образом, каждой вершине дается общий заряд не более ${ displaystyle d (v) / 5}$ . Начальный заряд каждой вершины v равен ${ displaystyle 6-d (v)}$ . Итак, окончательный заряд каждой вершины не превосходит ${ displaystyle 6-4d (v) / 5}$ . Следовательно, вершина может иметь положительный конечный заряд только в том случае, если ее степень не выше 7. Теперь мы покажем, что каждая вершина с положительным конечным зарядом смежна с конечной точкой светлого ребра.

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

Метод разряда (дискретная математика) - Discharging method (discrete mathematics)

Пример

Рекомендации