Графы. Применение графов к решению задач

4.

Все ли фигуры у вас получилось нарисовать? (все, кроме фигуры №1). Как вы думаете почему? Как это связано с количеством четных и нечетных вершин?

Сделаем вывод:

Если все вершины графа четные, то нарисовать фигуру возможно, и начать можно с любой вершины (№4).

Если же из этих вершин две нечетные, то нарисовать фигуру можно, но только начинать необходимо в одной из этих двух нечетных вершин, а заканчивать во второй нечетной вершине (№2, №3).

Если в графе более двух нечетных вершин, то нарисовать фигуру невозможно (№1).

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

4). Город Кенигсберг расположен на берегах и двух островах реки Преголя. Части города соединены между собой семью мостами. В воскресные дни горожане совершили прогулки по городу. И возник вопрос, можно ли выбрать такой маршрут, чтобы пройти по каждому мосту только один раз и вернуться в начальную точку пути?

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

Ответ: обход по всем мостам только один раз невозможен, т.к. все вершины графа нечетные.

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

Задачи для самостоятельного решения:

1). Алина решила маме на день рождения подарить букет цветов (розы, тюльпаны или гвоздики) и поставить их или в вазу или в кувшин. Сколькими способами это можно сделать?

2). Ранним утром Миша Маша, Андрей обменялись приветствиями каждый с каждым. Сколько всего было приветствий. Решите задачу с помощью графа. Нарисуй граф в рабочей тетради.

3). В квартирах №1,2,3 жили три друга: Айдар, Тима и Саша. Известно, что в квартирах №1 и 2 жил не Айдар. Тима жил не в квартире №1. В какой квартире жил каждый из друзей.

4). Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

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

6). Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру. Подпрыгивать и перелетать с места на место не разрешается.

Актуально о образовании:

Эмпирическая база исследования и характеристика выборки
Наше исследование проводилось на базе учебного заведения, школы №11, 2 класс в коллективе 12 человек и 3 класс в коллективе 15 (см. таблицу №1) Таблица №1 Класс количество средний возраст класса количество девушек средний возраст девушек количество юношей средний возраст юношей 2 12 8,7 6 8,2 6 8,5 ...

Личностно-ориентированное педагогическое взаимодействие учителя и учеников при компьютерном обучении
Педагогика сотрудничества, деятельностный подход к учебному процессу, активация учащихся, индивидуализация обучения – все эти тенденции современной педагогики заставляют задуматься о кардинальном переосмыслении роли учителя в учебном процессе. Авторитарная схема синхронного управления классом из не ...

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