Графы и их применение в решении задач

Статья.DOC

Тема: «Графы и их применение в решении задач».

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

Задачи:

- знакомство с задачей о семи кенигсбергских мостах;

- знакомство с математиком Леонард Эйлер;

- научиться рисовать графы, определять четные и нечетные вершины;

- связь между двумя задачами;

- общий метод решения подобных задач.

Этапы работы:

Определение проблемы.

Формулировка задач исследования.

Обсуждение способа построения графа, нахождение четных и нечетных вершин графа.

Нахождение связи между двумя задачами.

Самостоятельная работа над проектом.

Сбор, систематизация и анализ полученных знаний.

Подготовка к защите проекта.

Защита проекта.

Основная часть

На математическом кружке я рассказала детям, что через город Калининград (раньше Кенигсберг) протекает река Преголя. Она делится на два рукава и огибает остров. В 18 веке в городе было 7 мостов. Однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка. Ребята не смогли пройти по всем мостам один раз и закончить путь там, где он был начат. Тогда я нарисовала еще один мост и поставила точно такой же вопрос. Ребята тратили много времени, но результата не достигли. Тогда я предложила научиться решать такие задачи с помощью графов.

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

Итак, получили граф. Суши мы обозначили буквами А, B, C, Д (вершины графа). Соединили их линиями. Количество линий равно количеству мостов. Линии, которые соединяют вершины, называются ребрами графа. Мы заметили, что из вершин В, С, Д выходят по 3 ребра, а из вершины А – 5 ребер.

Все вершины нечетные. Мы не смогли обойти все мосты, побывав на каждом из них один раз.

Попробовали увеличить количество мостов на 1. Их стало 8. Нарисовали граф.

Из вершины Д выходит 4 ребра, из А – 3 ребра, из В – 3 ребра, из С – 3 ребра, из Е – 3 ребра. Одна вершина Д – четная, а четыре вершины – нечетные. Здесь мы тоже не смогли начертить одним росчерком.

Такой путь долгий и тяжелый.

На следующем занятии я предложила знакомую задачу: Какие буквы русского алфавита можно нарисовать одним росчерком?

Конечно, ребята с легкостью справились с этой задачей. Таких букв 15.

Мы предположили, что буквы русского алфавита это графы. Может ключ к разгадке в количестве вершин, ребер, количестве четных и нечетных вершин графа?

Начнем с букв. Возьмем букву Б.

У нее 4 вершины, 4 ребра. Из вершины 1 выходит 1 ребро, из вершины 2 -2 ребра, из вершины 3- 3 ребра, из вершины 4 – 2 ребра. Получили 2 четные вершины и 2 нечетные вершины.

Таким образом, заполнили всю таблицу.

Что же мы заметили?

Если количество нечетных вершин равно 0 или 2, то можно одним росчерком начертить граф. Если только четные вершины (в данном случае буквы В и О) также можно не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии начертить граф. Количество четных вершин может быть четным и нечетным.

У нас возникли вопросы:

- если нечетных вершин не 2, а больше 2?

- зависит ли решение нашей задачи от количества четных и нечетных вершин?

Проверим эту гипотезу.

1. Начертим граф с нечетными вершинами (6 мостов).

В задаче о кенигсбергских мостах также все вершины нечетные.

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

2. Начертим граф только с четными вершинами (9 мостов)

В этом случае можно одним росчерком начертить граф.

Маршрут движения: САЕАВЕДВСД или наоборот. Что мы заметили?

Вывод: Если все вершины графа четные, то можно одним росчерком начертить граф.

3. Начертим граф, где имеются четные и нечетные вершины.

Пусть 9 мостов.

В данном случае нечетных вершин 2.

В этом случае можно одним росчерком начертить граф.

Маршрут движения: САЕАВЕДВСД или наоборот. Что я заметил? Вершины С и Д нечетные.

Если мостов 14?

Из точки А выходят 4 моста, из В- 3 моста, С- 5 мостов, Д- 6 мостов, Е – 6 мостов, F – 4 моста. Две вершины В и С нечетные, а остальные вершины четные.

Маршрут движения: ВАЕСДАСВДЕFДЕFС и наоборот.

Во всех этих двух случаях (для 9, 14 мостов) движение начинали от одной нечетной вершины и заканчивали на другой нечетной вершине. Количество четных вершин не имел значения, а количество нечетных вершин равно 2.

К чему мы пришли?

- Если все вершины графа четные, то можно одним росчерком начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине;

- если две вершины графа нечетные, то можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине;

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

Еще мы обнаружили, что

- число нечетных вершин графа всегда четное;

- если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф, равно половине числа нечетных вершин этого графа.

Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/221468-grafy-i-ih-primenenie-v-reshenii-zadach