Урок 22. Задача о Кёнигсбергских мостах(7 класс)

Слайд #1

Урок 22
Вероятность и статистика 8 класс

Слайд #2

Вопросы:
1. Своими словами объясните, что такое путь в графе.
2. Объясните, что такое цепь.
3. Может ли в цепи рёбер быть больше, чем вершин?
4. Объясните, что такое цикл.
5. Может ли в цикле рёбер быть меньше, чем вершин?
6. Какой граф называют связным?

Слайд #3

Классная работа
Задача о Кёнигсбергских мостах, эйлеровы пути и эйлеровы графы
... 12. 23

Слайд #4

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

Слайд #5

На рисунке 33 показаны три графа из ниток.
Первые два удалось выложить одной ниткой, а третий — нет.
Потребовалось две нитки.

Слайд #6

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

Слайд #7

Название «эйлеров» объяснить легко.
По сути, мы доказали теорему, которую задолго до нас доказал Леонард Эйлер , решая знаменитую задачу о семи Кёнигсбергских мостах.
Леонард Эйлер — великий математик. Эйлер родился в Швейцарии в 1707 г. В 1727 г. Эйлер приехал в Санкт-Петербург. Вклад Эйлера в мировую математику огромен и неоценим. В Рос­сии Эйлер принимал участие в создании университета при Петербургской академии наук, писал учебники, возглавлял работу по созданию первого географического атласа России.

Слайд #8

В старинном городе Кёнигсберге (ныне Калининград) семь мостов через реку Преголя, которую во времена Эйлера называли Прегель (рис. 34). Древняя городская легенда гласила, что тот, кто сумеет обойти весь город, ровно по разу побывав на каждом из семи мостов, обретёт счастье и богатство. Кто только ни пытался это сделать, но никому не удавалось.

Слайд #9

Леонард Эйлер доказал, что пройти по каждому из семи мостов ровно один раз невозможно, откуда бы путник ни начинал свой путь.

Слайд #10

На самом деле Эйлер решил более общую задачу, доказав следующую теорему.

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

Слайд #11

Участки суши изобразим вершинами, мосты — рёбрами графа (рис. 35). Посмотрите ещё раз на план города и убедитесь, что мосты на графе показаны верно.
Теперь мы тоже можем решить задачу о мостах.
В получившемся графе все четыре вершины имеют нечётную степень: вершины А, В и Г имеют степень 3, а вершина Б — степень 5. Значит, обойти такой граф эйлеровым путём невозможно.

Слайд #12

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

Вопросы

Слайд #13

В классе:
Учебник стр. 91 – 92;
№ 142, № 143, № 146

Слайд #14

№ 142
Ответ: 1 и 3

Слайд #15

№ 143
Ответ: 1, 2 и 4

Слайд #16

№ 146
Ответ: нет, нельзя

Слайд #17

Дома:
п. 21; № 144, № 145, № 147