Листок 3 (теория). Подсчёт степеней вершин и обходы. Индукция

Издавна среди жителей Кёнигсберга (бывшее название Калининграда) была распространена такая загадка: как пройти по всем семи мостам через реку Преголя, не проходя ни по одному из них дважды. Многие жители города пытались решить её, но как доказать возможность или отсутствие существования решения, никто из них не знал.

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был: «нельзя». Решение этой задачи Эйлером считается началом создания теории графов, которая с тех пор находит широкое применение, в том числе для составления оптимальных маршрутов.

Степень вершины – количество рёбер, смежных с этой вершиной.

Эйлеров путь в графе — это путь, проходящий по всем рёбрам графа только один раз.

Эйлеров цикл — это цикл графа, проходящий через каждое ребро графа ровно один раз.

Эйлеров граф — граф, содержащий эйлеров цикл.

Полу-эйлеров граф — граф, содержащий эйлеров путь (цепь).

Уникурсальной кривой называют линию, которая может быть начерчена без отрыва ручки от бумаги, причём каждая её точка прочерчивается один раз. Рисунок, сделанный рукой самого Эйлера в научной статье:

В статье Эйлер построил алгоритм нахождения маршрута обхода и доказал, что:

1. Число вершин, к которым ведёт нечётное число рёбер графа, всегда чётно, а сумма степеней всех вершин равна удвоенному числу рёбер (лемма о рукопожатиях).

2. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, его начертить, при этом можно начинать с любой вершины графа и закончить ею же.

3. Если ровно две вершины графа нечётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой из нечётных вершин и завершить его в другой нечетной вершине.

4. Граф с более чем двумя нечётными вершинами нельзя начертить одним росчерком.

Возможная последовательность доказательства этих утверждений такая:

Теорема 1. Сумма степеней вершин графа даёт удвоенное число рёбер.

Теорема 2. Пусть в графе есть незамкнутый эйлеров путь. Тогда степени двух концов этого пути нечетны, а степени всех остальных вершин четны.

Теорема 3. Пусть в графе есть эйлеров цикл. Тогда степени всех вершин четны.

Лемма. Если в графе степени всех вершин четны, то его можно представить в виде объединения циклов так, что каждое ребро входит ровно в один цикл.

Теорема 4. Если в связном графе степени всех вершин четны, то в нем есть эйлеров цикл.

Теорема 5. Если в связном графе степени ровно двух вершин нечетны, то в нем есть эйлеров путь с концами в нечетных вершинах.

Утверждения теорем 1-3 и леммы доказываются не очень сложно и их можно рассмотреть в качестве самостоятельного упражнения. Теоремы 4 и 5 требуют особого метода доказательства – математической индукции.

Поиск по сайту: