Дата проведения занятия. Задача о Кенигсбергских мостах: Пройти по всем мостам так, чтобы на каждом побывать лишь один раз и вернуться к тому месту, откуда. - презентация

1 Дата проведения занятия

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

3 Знакомство с теорией графов Цель урока: получить первичные сведения о графах, научиться решать логические задачи с помощью графов.

4 Интерпретация задачи в виде графа: Изобразить данный граф одним росчерком пера Изобразить данный граф одним росчерком пера

5 Степень вершины Степень вершины = количеству ребер, исходящих из этой вершины

6 Степень вершины Закономерность 1: Если все вершины графа четные, то его можно изобразить «одним росчерком пера».

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

8 Степень вершины Закономерность 3:Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». Закономерность 3: Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».

9 Степень вершины Задача не имеет положительного решения, так как данный граф имеет более двух нечетных вершин. Задача не имеет положительного решения, так как данный граф имеет более двух нечетных вершин.

10 Задача о ключе Это план подземелья. В одной из комнат скрыт ключ. Чтобы его найти нужно войти в одну из крайних комнат, пройти через все двери, причем в точности по одному разу через каждую. Ключ скрыт за той дверью, которая будет пройдена последней. Укажите номер комнаты с ключом

11 Интерпретация задачи в виде графа: Укажите номер комнаты с ключом

12 Решение задачи о ключе: 1. Посчитать степень каждой вершины графа 2. Начать движение из нечетной вершины

13 Задача о составе экспедиции: биологбиолог врачврач синоптиксиноптик гидрологгидролог механикмеханик радистрадист AA BB CC DD EE FF GG HH

14 Анализ графовой модели биологбиолог врачврач синоптиксиноптик гидрологгидролог механикмеханик радистрадист AA BB CC DD EE FF GG HH

15 биологбиолог врачврач синоптиксиноптик гидрологгидролог механикмеханик радистрадист AA BB CC DD EE FF GG HH

16 Спасибо за внимание и работу!