В этом учебном году в учебном плане семиклассников появился новый предмет - «Вероятность и статистика». В структуре программы учебного курса «Вероятность и статистика»(7 класс) выделено четыре содержательно-методических линий: «Представление данных и описательная статистика», «Вероятность», «Элементы комбинаторики», «Введение в теорию графов». На изучение последней из этих линий отведено 4 часа.
Предлагаю вашему вниманию материалы для изучения данной темы. Предложенный материал «разбить» на уроки можно по-разному, я представляю его одним блоком.
Начинаю тему с рассказа о городе Калининграде (можно показать видео о городе, можно ограничиться презентацией фотографий) и рассказываю о мостах этого замечательного города. В г. Калининграде (ранее Кёнигсберг) протекает река Прегель, разделяясь на два рукава и образуя острова. В 18 веке в городе было 7 мостов, как показано на рисунке.
Рис. 1
С давних пор жители Кёнигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому лишь только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку никто не смог.
В 1736 году известный математик, член Петербургской академии наук Леонард Эйлер взялся решить задачу о семи мостах. В том же году он написал об этом инженеру и математику Мариони. Эйлер писал, что нашел правило, по которому нетрудно вычислить, можно ли пройти по всем мостам и при этом ни по одному не пройти дважды. На семи Кёнигсбергских мостах это сделать невозможно.
Давайте и мы с вами попробуем найти это правило. Отметим на каждом берегу и на островах по одной точке и соединим эти точки в соответствии с расположением мостов. Задача свелась к задаче изображения одним росчерком следующей картинки:
Рис. 2
Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки А, В, С, D называют вершинами графа, а линии, которые соединяют вершины - ребрами графа. Количество ребер, выходящих из вершины графа, называются степенью вершины. Вершина графа, имеющая нечетную степень, называется нечетной, а имеющая четную степень - четной.
Переформулируем задачу о Кёнигсбергских мостах на язык теории графов. Следует выяснить, существует ли замкнутый путь, который включает все ребра графа, изображенного на рисунке 2.
Решая задачу про мосты Кёнигсберга, Эйлер установил свойства графов. Рассмотрим эти свойства.
Вернемся к нашей картинке. В представленном на ней графе 4 вершины и 7 ребер. Определим степени вершин: степень вершины А равна 3, степень вершины В - 5, степень вершины С - 3, степень вершины D - 5. Сложим эти числа: 3 + 3 + 5 + 3 = 14, при этом каждое ребро мы посчитали два раза.
Можем сделать вывод о том, что сумма степеней графа равна удвоенному количеству ребер, то есть сумма степеней графа четное число.
А теперь немного математики, не относящейся к графам. Нам надо сложить несколько чисел, часть из которых четные, а часть нечетные. Каков будет результат сложения: четное или нечетное число и от чего это зависит? Сумма четных чисел всегда четное число, сумма нечетных же может быть и четным, и нечетным числом. Если количество нечетных чисел нечетно, то и их сумма будет нечетное число. И наоборот. Значит, для того, чтобы сумма четных и нечетных чисел была четным числом, нужно взять четное количество нечетных чисел. Теперь применим это свойство к степеням вершин графа: чтобы сумма степеней графа была четным числом (удвоенное количество ребер графа), необходимо, чтобы четное количество вершин имели нечетную степень.
Рассмотрим ещё некоторые понятия, связанные с графами. Путь, соединяющий вершины, назовем маршрутом. Рассмотрим, какие могут быть маршруты в графах.
Вернемся к нашей задаче: нам нужно построить замкнутый маршрут, ребра которого различны, то есть цикл и к тому же включающий все ребра графа.
Эйлеров путь (или эйлерова цепь) в графе - это путь, проходящий по всем ребрам графа и притом только по одному разу. И существует такой путь только тогда, когда граф содержит не более двух вершин нечетной степени. В нашей же задаче все вершины графа имеют нечетную степень. Следовательно, данная задача решения не имеет.
В качестве дополнительного задания можно предложить ребятам определить, где и сколько дополнительных мостов нужно построить, чтобы задача имела решение.
Для закрепления этой информации можно предложить следующие задания:
1. Можно ли построить микросхему, которая имеет 7 датчиков, каждый из которых соединен с 3 другими? (сделать нельзя, так как нечетное количество вершин, имеющих нечетную степень).
2. Можно ли проложить непересекающиеся дорожки, соединяющие каждый из домов с каждым колодцем?
Рис. 3
3. Можно ли при раскрашивании политической контурной карты использовать не более 4 различных цветов?
Рис. 4
4. Является ли эйлеровым графом «подпись Магомета»? Если да, воспроизведите её.
Рис. 5
В качестве домашнего задания можно предложить начертить фигуры одним росчерком, либо самим составить такие фигуры.
Рис. 6
В завершение предлагаю задачи, в которых требуется не только решить их, но и определить, какое понятие теории графов можно использовать в ходе их решения:
1. Водитель снегоуоборочной машины заметил, что если по каждой улице города он проедет только по одному разу, то закончит свою поездку на том перекрестке, где находится гараж. На рисунке 7 дана схема улиц города. Найдите, с какого перекрестка должен начать водитель работу и на каком перекрестке тогда находится гараж? Сколько решений имеет задача?
Рис. 7
2. Шесть островов на реке в парке «Лотос» соединены мостами. Можно ли, начав прогулку на одном из островов, пройти по каждому из мостиков ровно один раз и вернуться на тот же остров? В случае отрицательного ответа определите, сколько мостиков и между какими островами достаточно построить, чтобы такая прогулка стала возможной.
Рис. 8
3. На озере находится 7 островов, которые соединены между собой мостами так, как показано на рисунке 9. На какой остров должен доставить катер путешественников, чтобы они могли пройти по каждому мосту и только один раз?. С какого острова катер должен снять этих людей? Почему нельзя доставить путешественников на остров А?
Рис. 9
4. Дан план подземелья в одной из комнат которого скрыты богатства рыцаря (на рисунке 10 комнаты пронумерованы). После смерти рыцаря его наследники нашли его завещание, в котором было сказано, что для отыскания сокровищ необходимо войти в одну из комнат подземелья так, чтобы можно было пройти через все двери, причем в точности по одному разу через каждую, сокровища скрыты за той дверью, которая будет пройдена последней. В какой комнате были спрятаны сокровища? Сколько решений имеет задача?
Рис. 10
5. В небольшой роще находится заяц. Выскочив из норы и бегая по снегу от дерева к дереву, он оставил следы и, наконец, спрятался под одним из этих деревьев. Опытный охотник определил, что между каждыми двумя деревьями заяц пробегал не более одного раза. Где находится сейчас заяц? Под каким деревом находится его нора? Сколько решений имеет задача?
Рис. 11
Литература
- Игнатьев Е.И. В царстве смекалки, М., 1978г.
- https://dzen.ru/a/XuqIY-WtSEjKXbjs
- https://grafielk.narod.ru/HTMLs/theory4.html