Графы. Уникурсальные кривые. Мосты Эйлера.
занимательные факты по математике (10, 11 класс) на тему

Слайд 1

Графы. Мосты Эйлера. Уникурсальные кривые. МОУ ГСОШ г. Калязин Тверская область. Учитель математики Ладющенкова О.Е.

Слайд 2

Основы теории графов как математической науки заложил в 1736 г. Л. Эйлер, решая задачу о мостах Кенинсберга.

Слайд 3

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

Слайд 4

Графы Граф – это набор точек, некоторые из которых соединены линиями. Эти точки называются вершинами . Соединяющие их линии называются ребрами графа . 2 вершины и 1 ребро 3 вершины и 3 ребра 4 вершины и 5 ребер 6 вершины и 6 ребер

Слайд 5

Слово «граф» первым стал использовать английский математик Джеймс Дж. Сильвестр (1814—1897). Примерами графов могут служить любая карта дорог, схема линий метрополитена, электросхема, чертеж многоугольника и т. д. Граф называется связным, если его нельзя разбить на два, не разрывая в какой-нибудь вершине. В связном графе можно, двигаясь по ребрам, перейти из любой вершины в любую другую. Связный граф Несвязный граф

Слайд 6

Теорема: Граф можно обойти, пройдя по каждому ребру только один раз в том случае, если граф связный и нечетных вершин у него 0 или 2. При этом если нечетных вершин две, то маршрут начинается в одной из них, а заканчивается в другой. Если нечетных вершин нет ни одной, то маршрут может начаться в любой вершине и в ней же окончиться.

Слайд 7

10 20 3 0 4 0 10 20 3 0 4 0 10 20 1 балл 2 балла 3 балла

Слайд 8

Задача1(1 балл). Не отрывая карандаша от бумаги и не проводя по одной линии дважды, начертить “открытый конверт”: 2 4 4 4 3 3

Слайд 9

1. Не отрывая карандаша от бумаги и не проводя по одной линии дважды, начертить “открытый конверт”: Да! Нечетных узлов два. 2 4 4 4 3 3

Слайд 10

Задача2 ( 1 балл).Не отрывая карандаша от бумаги и не проводя по одной линии дважды, начертить “закрытый конверт”: 3 3 3 3 4

Слайд 11

Не отрывая карандаша от бумаги и не проводя по одной линии дважды, начертить “закрытый конверт” Нет! Нечетных узлов более двух. 3 3 3 3 4

Слайд 12

Задача № 3(1 балл). Оса забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли оса последовательно обойти все двенадцать ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место она не может.

Слайд 13

Задача № 3. Оса забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли оса последовательно обойти все двенадцать ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место она не может. Каждая вершина куба есть узел, причем нечетный. Таких узлов больше двух (вершин 8), значит, оса не сможет обойти все 12 ребер куба, не проходя дважды по одному ребру. Решение:

Слайд 14

Задача № 4(1 балл) Встретились три подруги Белова, Краснова и Чернова. На одной из них было черное платье, на другой — красное, на третьей — белое. Девочка в белом платье говорит Черновой: «Нам надо поменяться платьями, а то у всех троих цвет платьев не соответствует фамилиям». Кто в какое платье был одет ?

Слайд 15

Задача4. Эту задачу можно решить с помощью рисунка. Обозначим на рисунке фамилии девочек буквами Б, Ч, К, соединим пунктирной линией букву Б и белое платье, что будет означать: «Белова не в белом платье». Далее получим еще три пунктирные линии, соответствующие минусам в таблице. Белое платье может быть только на Красновой — букву К и белое платье соединим сплошной линией, что будет означать «Краснова в белом платье», и т. д.

Слайд 16

Задача 5(2 балла). Уникурсальные кривые. Можно ли начертить каждую из фигур, не отрывая карандаша от бумаги и не проводя более раза по одной и той же линии.

Слайд 17

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

Слайд 18

Задача 6(2 балла).Можно ли нарисовать фигуру одним росчерком, не отрывая карандаша от бумаги и не проводя по одной линии дважды?

Слайд 19

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

Слайд 20

Задача 7(2 балла). Какие фигуры можно нарисовать одним росчерком?

Слайд 21

Задача 7. Какие фигуры можно нарисовать одним росчерком? Образец:

Слайд 22

Задача №8(2 балла). Почтальон Печкин разнес почту во все дома деревни, после чего зашел с посылкой к дяде Федору. На рисунке показаны все тропинки, по которым проходил Печкин, причем, как оказалось, ни по одной из них он не проходил дважды. Каков мог быть маршрут почтальона Печкина? В каком доме живет дядя Федор?

Слайд 23

Задача №8 Почтальон Печкин разнес почту во все дома деревни, после чего зашел с посылкой к дяде Федору. На рисунке показаны все тропинки, по которым проходил Печкин, причем, как оказалось, ни по одной из них он не проходил дважды. Каков мог быть маршрут почтальона Печкина? В каком доме живет дядя Федор? Ответ: Тропинки образуют сеть с двумя нечетными узлами — у почты и дома № 5. Начало маршрута на почте, а конец у дома №5 — там живет дядя Федор.

Слайд 24

Задача 9(3 балла). Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

Слайд 25

Задача 9. Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями. Теперь сразу видно, что долететь с Земли до Марса нельзя.

Слайд 26

Задача №10(3 балла). На рисунке изображен план подвала из десяти комнат. Можно ли пройти через все двери всех комнат, запирая каждый раз дверь, через которую вы проходите? С какой комнаты надо начать движение?

Слайд 27

Задача №10 На рисунке изображен план подвала из десяти комнат. Можно ли пройти через все двери всех комнат, запирая каждый раз дверь, через которую вы проходите? С какой комнаты надо начать движение? Решение: Заменяя комнаты точками, а двери — дугами, отрезками, получим фигуру с двумя нечетными узлами 8 и 1, она является уникурсальной, т. е. можно пройти через все двери комнат, запирая каждый раз ту, через которую прошли. Ответ: можно, начав движение с комнаты 8 или 1.