Задача Эйлера о мостах Кёнигсберга
презентация к уроку алгебры (8 класс) по теме

Слайд 1

Задача Эйлера о мостах Кёнигсберга. Разработано учителем математики и информатики МАОУ лицея № 17 Павловой И.А.

Слайд 2

Не каждому городу выпадает честь быть отмеченным в такой точной науке, как классическая математика. Кенигсберг же благодаря своим мостам и великому учёному – энциклопедисту XVIII века Леонарду Эйлеру вошел в число математических знаменитостей. Решив головоломку о Кёнигсбергских мостах, Эйлер положил начало совершенно новой области исследований, выросшей впоследствии в самостоятельный раздел математики- теорию графов и топологию.

Слайд 3

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

Слайд 4

В начале XX века в Кёнигсберге был построен Императорский мост. Теперь система мостов города образовывала граф, имеющий Эйлеров путь.

Слайд 5

XX век опять изменил карту города. В 1945 году при бомбёжке города были разрушены многие мосты, в 70-тые годы был построен эстакадный мост, к 750-летию города был восстановлен Императорский мост. Сейчас задачу Эйлера о мостах надо рассматривать для пешеходов и для автомобилей. Мы предполагаем, что в будущем наш город будут украшать новые мосты, а в задаче Эйлера появятся новые исходные условия.

Слайд 6

Современная карта мостов (конец XX века).

Слайд 7

Современная карта мостов (начало XXI века).

Слайд 8

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

Слайд 9

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

Слайд 10

Нулевой граф Граф, состоящий из «изолированных» вершин, называется нулевым графом Рис. 2 . Нулевой граф

Слайд 11

Неполный граф Графы, в которых не построены все возможные ребра, называются неполными графами. Рис. 3. Неполный граф

Слайд 12

Степень графа Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной. Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

Слайд 13

Заметим, что если полный граф имеет n вершин, то количество ребер равно n(n-1)/2 Задание 1 . Существует ли полный граф с семью ребрами? Решение : Зная количество ребер, узнаем количество вершин. n(n-1)/2=7. n(n-1)=14. Заметим, что n и (n-1) – это два последовательных натуральных числа. Число 14 нельзя представить в виде произведения двух последовательных натуральных чисел, значит, данное уравнение не имеет решений. Следовательно, такого графа не существует. ОТВЕТ

Слайд 14

Построить полный граф, если известно что он содержит в себе 7 вершин. Составьте схему проведения розыгрыша кубка по олимпийской системе, в которой участвуют 10 команд. Задание 2.

Слайд 15

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

Слайд 16

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

Слайд 17

« Из всего, что воздвигает и строит человек, повинуясь жизненному инстинкту, нет ничего лучше и ценнее мостов. Они важнее чем дома, священнее храмов, ибо они более общие. Они принадлежат всем и каждому, равные со всеми, нужные, воздвигнутые всегда на месте, где сходится максимальное количество человеческих нужд, они более долговечны, чем прочие сооружения…» Иво Андрич.