Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Пример [ править ]

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

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

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

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

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

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

Считаем, какие вершины могут иметь положительный конечный заряд. Единственные вершины с положительным начальным зарядом - это вершины степени 5. Каждая вершина степени 5 дает заряд 1/5 каждому соседу. Таким образом, каждой вершине дается максимальный заряд . Начальный заряд каждой вершины v равен . Итак, финальный заряд каждой вершины не больше . Следовательно, вершина может иметь положительный конечный заряд только в том случае, если она имеет степень не выше 7. Теперь мы покажем, что каждая вершина с положительным конечным зарядом смежна с конечной точкой светлого ребра.

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

Ссылки [ править ]