Презентация, доклад по математике: Графы и мосты Кёнигсберга (внеклассная работа)

«Мосты Эйлера».
Теория графов. Мосты Кёнигсберга.

латинского слова «графио» - пишу.

Г

Р

А

Ф

И

О

году, когда Л. Эйлер (1707-1782, российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук), решил широко известную в то время задачу о Кёнигсбергских мостах. Подробнее об этой задаче будет сказано ниже. Этот результат более ста лет оставался единственным в теории графов.

объекты точками, а отношения между ними отрезками или дугами.
В математике определение графа дается так:
Графом называется конечное множество точек, некоторые из которых соединены линиями.
Точки называются вершинами графа, а соединяющие линии – рёбрами.

Рёбра графа

Вершина графа

имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Нечётная степень

Чётная степень

четными, а точки, в которых сходится нечетное число линий, - нечетными.

то ее можно начертить одним росчерком, начиная вычерчивать с любого места;

если в фигуре две нечетные точки (если фигура имеет нечетную точку, то она всегда имеет и вторую нечетную точку), то ее можно начертить одним росчерком, начав вычерчивание в одной из нечетных точек и закончив в другой;

если в фигуре более двух нечетных точек, то ее нельзя вычертить одним росчерком.

(и не проводя по одной линии дважды).

признаки вычерчивания

задачи

физминутка

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

было построено 7 основных мостов. Примерно в эти же годы составлена классическая задача о семи мостах Кёнигсберга. Надо было пройти по всем городским мостам не проходя по одному из них дважды.

1286 году. Само название моста говорит само за себя. Площадь, которая прилегала к нему, была местом оживлённой торговли. Он связывал два средневековых города Альтштадт и Кнайпхоф. Построен он был сразу же в камне. В 1900 году он был перестроен и сделан разводным. По мосту стали ходить трамваи. Во время войны он был сильно разрушен, но восстановлен, пока в 1972 году не был демонтирован

мост . Этот мост связал остров Кнайпхоф с южным берегом Прегеля. В 1907 году мост был перестроен, средний пролёт стал разводным и по нему стали ходить трамваи. Во время войны этот мост сильно пострадал, был восстановлен, а в 1972 году - демонтирован.
В 1972 году вместо Зелёного и Лавочного мостов был построен Эстакадный мост.

году. Он соединил город Кнайпхоф с пригородом Форштадт. Этот мост был наполовину каменным, а пролёты - деревянные настилы. В 1621 году, во время сильного наводнения, мост сорвало и унесло в реку. Мост возвратили на место. В 1886 году его заменили новым, стальным, трёхпролётным, разводным. По нему тоже ходили трамваи. В 1945 году этот мост был разрушен

1397 году и соединял город Альтштадт на северном берегу с островом Кнайпхоф. Название моста характерно для средневекового города, так как кузнецы играли тогда важную роль и были всеми уважаемы. Этот мост тоже был с каменными опорами и деревянными пролётами. В 1896 году его перестроили, пролёты его стали стальными, а вот трамвайные пути обошли стороной. Во время войны он был разрушен. В советское время около опор моста находился плавучий ресторан

построен в 1404 году и связал остров Ломзе ( ныне остров Октябрьский) и город Лёбенихт. До этого на северном берегу Нового Прегеля существовала паромная переправа, но, а название уму дали по названию материала, из которого он был сделан. Таким он простоял 500 лет, и только в 1904 году был заменён новым, а вот название осталось прежним. Очень интересно оформление чугунного ограждения моста - были использованы лесные сюжеты. Мост тоже был разводным, по нему ходили трамваи, во время войны был разрушен, но очень быстро восстановлен. Мост существует и функционирует до сих пор, правда разводной механизм пришёл в негодность

болотистая местность , часто затопляемая во время половодий. Строительство домов на острове началось с 1455 года и тогда же была заложена ивовая дамба, которая в последствии стала улицей Октябрьской. В 1520 году был построен новый мост через Старый Прегель. Этот мост был выше других мостов из-за дамбы, и поэтому ему дали название Высокий мост.

находилась площадь - Бычий рынок. На площади стояли фахверковые склады, а за ними особняки с садами. Здесь же находился дом, где жил Кант ( 1775 - 1783 г.), чтобы Канту попасть на работу, ему достаточно было перейти Медовый мост и свернуть направо, там находился университет "Альбертина". В 1882 году мост был полностью перестроен, средний пролёт стал разводным, перила изготовила фирма "Кузнеца на Печатной". В таком виде мост сохранился до наших дней.
Это был последний, седьмой мост, который фигурирует в задаче Эйлера.

по одной монетке с любого из семи мостов, чтобы вернуться в этот город.

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

каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа.

эйлеровым.
Решая задачу О кенигсбергских мостах, Эйлер сформулировал свойства графа:
Невозможно начертить граф с нечетным числом нечетных вершин.

которые перекинуто семь мостов. Можно ли обойти все эти мосты, не побывав ни на одном из них более раза?

№ 1

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

А

В

С

D

Решение.

все эти мосты, гоняясь за зайцем, не побывав ни на одном из них более одного раза?

А

В

С

D

E

№ 2

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

Решение.

«одним росчерком», начиная с любой вершины.
ЕСЛИ 2 вершины – нечетные, то его нужно начать с одной из нечетных вершин.
Обход невозможен, если нечетных вершин больше 2.

В 1905 году в Кенигсберге был поострен еще один мост. (Слайд 30) История кайзера Вильгельма: Кайзер (император) Вильгельм славился своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. К всеобщему удивлению, кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли. Кайзер положил листок на стол, взял перо, и написал: «приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который так и назвали — мост кайзера. А задачу с восемью мостами теперь мог решить даже ребёнок.

канцлера Вильгельма.
Своему появлению он обязан самой задачи Эйлера.

ИМПЕРАТОРСКИЙ мост(Kaiser-brucke).

ПРИМЕРА РАССМОТРИМ НЕСКОЛЬКО ЗАДАЧ.

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

ЕГО В ВИДЕ НАГЛЯДНОЙ СХЕМЫ И ПОРЯДОК ОРГАНИЗАЦИИ ФИНАЛЬНОЙ ЧАСТИ РОЗЫГРЫША СТАНЕТ ОЧЕВИДНЫМ.

класс завезли 5 компьютеров, которые требуется связать локальной сетью. Известны расстояния между компьютерами. Требуется связать компьютеры таким образом, чтобы общая длина кабеля была бы наименьшей.

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

проволоки, изготовить каркас куба с ребром 10 см?
Решение:
Если куб – граф, тогда он имеет более двух нечетных вершин (8). Значит, невозможно изготовить такой каркас, не ломая проволоки.

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