Урок Эйлеровы циклы (9 класс)

Урок «Эйлеровы циклы»

факультативного курса «теория графов и их приложения» (9 класс)

В данной работе предлагается материал для проведения нескольких (2-3-х) занятий «Эйлеровы циклы» в рамках внеурочной работы по предмету. Этот материал может войти и в структуру факультативного курса «Элементы теории графов и их приложения», если учитель планирует такой курс. Тема «Эйлеровы циклы» является одной из важнейших задач теории графов, ведь именно с этой задачей и с именем Леонарда Эйлера связано рождение самой теории графов. Предполагается, что обучающиеся уже знакомы с такими элементарными понятиями теории графов, как вершина, ребро, степень вершины (валентность), инцидентность и смежность, связный граф. Если обучающимся неизвестны эти понятия, необходимо провести ознакомительное занятие.

Предлагается следующий порядок проведения занятий:

• задача о кёнигсбергских мостах;

• дискуссия по проблеме ее решения;

• теорема о наличии эйлерова цикла и её доказательство;

• решение задач на эйлеровы циклы и дискуссия о том, где встречаются такие задачи.

Задача о кёнигсбергских мостах.

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

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

При всей простоте формулировки эта задача оказалось довольно сложной. Часть горожан считала, что можно, другая - что нельзя. И жители города решили поставить эту задачу перед великим математиком, членом Петербургской академии наук Леонардом Эйлером. Как и надлежит математику, Леонард Эйлер прежде всего постарался представить условия задачи в схематическом виде, облегчающем понимание сути задачи и отбрасывающем все лишние подробности. Так родилось представление условия задачи с помощью графа. Наверняка, это было не первое использование графа для структурирования условия задачи, но благодаря великому математику, такой способ получил собственную теоретическую значимость, что позже и вылилось в теорию графов. Как же Леонард Эйлер представил схему задачи? Давайте посмотрим. На рисунке 1 представлен план города.

Рисунок 1 - План города Кёнигсберга

Давайте попытаемся решить задачу и ответить на вопрос: можно ли, выйдя из одной точки, прогуляться по одному разу по всем мостам и вернуться опять в эту точку? Представим план города с помощью схемы, получившей название графа (рисунок 2).

Рисунок 2. Граф кенигсбергских мостов

Дискуссия. При проведении обсуждения надо просить обучающихся аргументировать свой ответ, объясняя, почему они считают так, а не иначе. В ходе обсуждения можно подсказать, что задачу можно попытаться решить, если пробовать из любой точки (вершины) обвести этот граф, не отрывая карандаша от бумаги и проходя по каждому ребру только один раз, после чего вновь попасть в эту вершину. Если это удастся, то ответ на вопрос - да, возможно; если не удастся, то ответ - нет, невозможно.

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

Теорема Эйлера и решение задачи. Сейчас, когда все учащиеся попытались решить задачу, и, возможно, уже пришли к тому же мнению, что и Леонард Эйлер, давайте дадим некоторые определения и термины теории графов. Для всех терминов приведем иллюстрации.

Граф без петель и кратных ребер принято называть графом (рисунок 3, а).

Граф, в котором разрешены кратные ребра - мультиграфом (рисунок 3, б).

Мультиграф, в котором разрешены петли, - псевдографом (рисунок 3, в).

Рисунок 3. Граф (а), мультиграф (б), псевдограф (в)

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

Знакомимся еще с рядом понятий теории графов. Несмотря на их простоты и легкость восприятия, все они также должны быть проиллюстрированы рисунком.

Ребро и вершина графа инцидентны, если ребро содержит вершину. Степенью (валентностью) вершины называется число ребер, ей инцидентных (петля считается дважды: так степень вершины с петлей на рисунке 3, (в) равна 5). Маршрутом в графе G называется любая последовательность вида v₀, (v₀, v₁), v₁, (v₁, v₂), … v_n-1, (v_n-1, v_n), v_n, в которой любые два соседних элемента инцидентны. Число n является длиной маршрута.

Маршрут называется замкнутым, если v₀ = v_n.

Цепью называется маршрут, в котором нет повторяющихся рёбер.

Простой цепью называется маршрут без повторения вершин.

Замкнутая цепь называется циклом.

Замкнутая простая цепь - простым циклом.

Рассмотрим пример (рисунок 4)

Рисунок 4. Маршруты, цепи и циклы в графе

Предлагаем учащимся указать на рисунке объекты, соответствующие данным определениям (здесь также используется прием - подведение под определение). После обсуждений (предположений, обоснований и пр.) учащиеся записывают результаты.

Для графа, представленного на рисунке 4:

• v₁, v₃, v₁, v₄ - маршрут, но не цепь;

• v₁, v₃, v₅, v₂, v₃, v₄ - цепь, но не простая цепь;

• v₁, v₄, v₃, v₂, v₅ - простая цепь;

• v₁, v₃, v₅, v₂, v₃, v₄, v₁ - цикл, но не простой цикл;

• v₁, v₃, v₄, v₁ - простой цикл.

Если ребра графа не имеют направления, то он называется неориентированным. Граф на рисунке 4 - неориентированный (иногда говорят - неорграф). У ориентированного графа ребра имеют направленность (вообще, ребра ориентированного графа принято называть дугами). На рисунке 5 изображен ориентированный граф.

Рисунок 5. Пример ориентированного графа (орграфа)

Если между парой вершин графа существует как минимум один маршрут, такой граф называют связным. На рисунке 6, а) изображен связный граф, на рисунке 6, б) - несвязный. Из рисунка 6, б) видно, что в графе, например, из вершины v₂ нельзя попасть в вершину v₄ и граф оказывается разбит как бы на две не связанные части. Одна часть включает вершины v_1, v₂, v₃, а вторая - вершины v₄ и v_5. Такие части называют компонентами связности графа.

Рисунок 6 - Связный (а) и несвязный (б) графы

Возвращаемся к задаче о мостах. Неориентированный мультиграф G, представляющий задачу, показан на рисунке 2. Вершины v₁, v₄ соответствуют берегам реки, v₂, v₃ островам, ребра мультиграфа - мостам.

Предлагаем учащимся сформулировать задачу с использованием введенных терминов теории графов.

После некоторых попыток они приходят к формулировке: существует ли в мультиграфе цикл, содержащий все ребра данного мультиграфа?

Заранее подготовленный учащийся (тот же самый, который в начале занятия давал историческую справку) говорит, что такой цикл называют эйлеровым и граф, его содержащий, тоже называют эйлеровым. В 1736 году Леонард Эйлер решил эту задачу и сформулировал обобщённое решение всех подобных задач в виде теоремы.

Учитель приводит ее современную формулировку и знакомит учащихся с доказательством при их активном участии в его проведении.

Теорема. Связный граф является эйлеровым тогда и только тогда, когда степень каждой его вершины четная.

Доказательство. Необходимость. Пусть G - эйлеров граф. Эйлеров цикл этого графа, проходя через каждую его вершину, входит в нее по одному ребру, а выходит по-другому. Это означает, что каждое прохождение вершины по циклу вносит слагаемое 2 в ее степень. Поскольку цикл содержит все ребра графа, то степени всех вершин будут четными.

Достаточность. Предположим, что степени всех вершин связного графа G четные. Рассмотрим рисунок 7.

Рисунок 7. К доказательству теоремы Эйлера

Начнем цепь P₁ из произвольной вершины v₁ и будем продлевать ее, выбирая каждый раз новое ребро. Так как степени вершин четные, то, попав в некоторую вершину, мы всегда будем иметь в распоряжении еще не пройденное ребро. Таким образом, построение цепи P обязательно закончится в вершине v₁, и P₁ окажется циклом. Если P₁ содержит все ребра графа G, то построен эйлеров цикл. В противном случае, удалив из G ребра P₁ получим граф G₂. Так как степени всех вершин графов G и P₁ были четными, то и G₂ будет обладать этим свойством. В силу связности G графы P₁ и G₂ должны иметь хотя бы одну общую вершину v₂. Теперь, начиная из v₂, построим в G₂ цикл P₂ подобно тому, как построили P₁. Объединим циклы P₁ и P₂ следующим образом: пройдем часть P₁ от вершины v₁ до вершины v₂, затем пройдем цикл P₂, затем - оставшуюся часть P₁ от v₂ до v₁ (см. рисунок 4). Если объединенный цикл не эйлеров, то, проделав аналогичные построения, получим еще больший цикл. Поскольку степени вершин во всех графах, составленных из ребер, не попавших в строящийся цикл, четные, и число ребер в этих графах убывает, то процесс закончится построением эйлерова цикла. Теорема доказана.

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

Можно продолжить далее знакомство с эйлеровыми графами. Для этого надо ввести понятие эйлеровой цепи и сформулировать связанное с ней свойство связного графа.

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

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

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

Другой заранее подготовленный учащийся знакомит одноклассников с легендой, связанной с задачей о кёнигсбергских мостах. В 1905 году в Кёнигсберге был построен Императорский мост (он был впоследствии разрушен во время Второй мировой войны). Считается, что этот мост был построен по приказу кайзера, который велел возвести его из-за того, что не смог решить задачу о кёнигсбергских мостах. А всё потому, что он стал жертвой шутки, которую сыграли с ним учёные, присутствовавшие на светском приёме. Они убедили кайзера, что можно прогуляться по одному разу по всем мостам и прийти в исходную точку. Разумеется, ему это не удалось. Но надо заметить, что если добавить восьмой мост, то задача становится разрешимой. В 2005 году на опорах разрушенного Императорского моста был построен Юбилейный мост. И сейчас в Калининграде восемь мостов.

Далее предлагаем учащимся серию задач на рассмотренный материал.

Задачи для обсуждения. Большинство задач взяты из пособий О.И. Мельникова, рекомендуется также использовать пособие.

Задача 1. Шесть островов на реке в парке «Лотос» соединены мостами (рисунок 8). Можно ли, начав прогулку на одном из островов, пройти по каждому из мостиков ровно один раз и вернуться на тот же остров? В случае отрицательного ответа определите, сколько мостиков и между какими островами нужно построить, чтобы такая прогулка стала возможной.

Рисунок 8. К задаче 1

Задача 2. Можно ли нарисовать фигуры, изображенные на рисунке 9, не отрывая карандаша от бумаги, причем каждую точку фигуры карандаш должен проходить только один раз?

Рисунок 9. К задаче 2

Задача 3. Можно ли выполнить аналогичные действия для фигуры, представленной на рисунке 10?

Рисунок 10. К задаче 3

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

Рекомендуемая литература

1. Аммосова Н.В., Коваленко Б.Б. Элементы теории графов на факультативных занятиях в школе // Организация исследовательской деятельности в образовательных учреждениях: Сб. трудов II Всеросс. научно-практич. конф. - Астрахань: Изд-во АИПКП, 2008. - С. 23-26.

2. Аммосова Н.В., Izvorska D., Коваленко Б.Б. Использование мыслительных операций как базы синергетического подхода при обучении математике // Education, science and economics at universities, integration to international educational area: International conference. - Plock, Poland, 2008. - P. 246-250.

3. Березина Л. Ю. Графы и их применение: Пособие для учителей с ил. - М.: Просвещение, 1979. - 143 с.

4. Мельников О.И. Занимательные задачи по теории графов. - Минск: ТетраСистемс, 2001. - 144 с.

5. Мельников О.И. Теория графов в занимательных задачах. Изд.3, испр. и доп. - М.: Книжный дом «ЛИБРОКОМ» ,2009. - 232 с.