120px-XXV+.jpg Helpwiki.jpg Gosuslugi.jpg Vystavka.jpg Использование интерактивной доски Panaboard LogoRobo2-120.jpg

ПскоВики переехала на новую площадку
Некоторые гиперссылки, созданные ранее, могут не работать, так как URL- адрес изменился на http://wiki1.pskovedu.ru

Исследование учащихся в проекте Необычное в обычном или Чудеса в математике

Материал из ПскоВики — сайта педагогического сообщества Псковской области

Перейти к: навигация, поиск

Содержание

Тема исследования

Графы в математике

Цели исследования

  • Изучить определение и свойства графа
  • Рассмотреть применение теории к решению задач
  • Подготовить задачи по теме исследования

Ход исследования

  1. Изучение литературы и Интернет-источников по теме
  2. Систематизация материала, отбор нужной информации
  3. Коллективная работа группы по обсуждению содержания Вики-статьи
  4. Консультация с учителем по содержанию подготовленного материала
  5. Создание вики-статьи
  6. Оценивание работы группы и каждого её участника на основе требований, сформулированных в памятке

Введение

Тема нашего исследования «Графы». Хотим сразу отметить, что она не имеет никакого отношения к дворянскому титулу, введённому в России Петром Первым.

Рассматривая занимательные книги по математике, мы встречаемся с заданиями такого вида:

Risgr1.JPG

1. Голодная лиса вышла из вырытой под деревом норы и начала бродить по лесу от дерева к дереву в поисках добычи. Чёрной линией изображён путь лисы. Наконец она устала и легла отдохнуть под одним из деревьев (дерево загораживает лису и её не видно). Где сейчас лиса? Под каким деревом находится её нора? Сколько решений имеет задача?


Risgr2.JPG




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




Risgr3.JPG

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



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

Понятие и свойства графа

Вернёмся к последней задаче. Многие горожане заинтересовались этой задачей. Однако придумать решение никто не смог. Потом этот вопрос привлёк внимание учёных разных стран. Решить проблему удалось знаменитому математику Леонарду Эйлеру. (Об этой задаче и её решении он писал из Петербурга 13 марта 1736 года итальянскому математику и инженеру Маринони.) Причём, он решил не только эту конкретную задачу, но и придумал общий метод решения подобных задач.

Risgr5.JPG

Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии. В результате получилась вот такая фигура(см. рис.)

Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки называют вершинами графа, а линии, которые соединяют вершины, - рёбрами графа. Вершины, из которых выходит нечётное число рёбер, называются нечётными вершинами, а вершины, из которых выходит чётное число рёбер, называются – чётными.

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

  • Если все вершины графа чётные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф.
  • Граф с двумя нечётными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечётной вершины, а заканчивать на другой нечётной вершине.
  • Граф с более чем двумя нечётными вершинами, невозможно начертить одним росчерком.

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

В задаче про лису две нечётные вершины, значит, нора лисы находится в одной из них, а сама лиса – во второй, или наоборот, т.е. задача имеет два решения.

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

Граф получить на листе бумаги очень просто. Надо взять карандаш и нарисовать на этом листке, не отрывая карандаша от бумаги и не проводя дважды по одной линии, что угодно. Отметить точками «перекрёстки» и начальную и конечную точки, если они не совпадают с «перекрёстками». Получившуюся фигуру можно назвать графом. Если начальная и конечная точки рисунка совпадают, то все вершины окажутся чётными, если же начальная и конечная точки не совпадают, то они окажутся нечётными вершинами, а все остальные будут чётными.

Risgr4.JPG

Льюис Кэрролл, автор книги «Алиса в стране чудес», любил давать своим знакомым следующую головоломку. Он просил обвести фигуру, изображённую на рисунке, не отрывая карандаша от бумаги и не проводя дважды по одной линии. Подсчитав чётность вершин, убеждаемся, что эта задача легко решается, причём начинать обход можно с любой вершины, т. к. они все чётные. Однако, он усложнял задачу тем, что требовал, чтобы при обводке линии не пересекались. Справиться с этой проблемой можно следующим способом. Раскрасим фигуру так, чтобы её граничащие части оказались разного цвета. Затем разъединим пересекающиеся линии таким образом, чтобы закрашенная часть представляла из себя единый кусок. Теперь остаётся обвести по краю одним росчерком закрашенную область – это и будет искомая линия.

Задачник

Зная свойства графа, полученные Эйлером, теперь легко можно решить такие задачи:

Задача 1: Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?

Задача 2. Оса забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли оса последовательно обойти все 12 рёбер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место она не может.

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

Risgr6.JPG

Задача 4. На рисунке изображён план деревни. Тракторист заметил, что, если по каждой улице деревни он проедет только по одному разу, то закончит свою поездку на том перекрёстке, где находится гараж. С какого перекрёстка начал своё движение тракторист и где находится гараж? Сколько имеется вариантов решения?

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

Risgr9.JPG

Задача 6. Нарисуйте эти фигуры, не отрывая карандаша от бумаги и не вычерчивая дважды одну и ту же линию.

Risgr7.JPG

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

Risgr10.JPG

Задача 8. Река разделяет город на четыре части, соединённые шестью мостами. Один турист решил обойти все мосты, побывав на каждом из них только один раз. Как это можно сделать, если не требовать обязательного возвращения в тот же район города, из которого начался обход? Добавьте на рисунок ещё один мост так, чтобы: а) можно было совершить переход через все мосты из любой части города; б) совсем нельзя было совершить переход через все мосты, побывав на каждом по одному разу.

Risgr8.JPG

Задача 9. На рисунке дан план квартиры. Разрывы в линиях обозначают двери. Маленькому мальчику захотелось за один обход пройти через все двери свое квартиры по одному разу. Его папа помог ему в этом. С какой комнаты мальчик мог начать свой путь?

Задача 10. Докажите, что число нечётных узлов графа всегда чётно.




Заключение

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

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

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

Источники информации

  • Асарина Е.Ю., Фрид М.Е. Математика выводит из лабиринта. Серия «Занимательная математика» (СЕЗАМ) – М.: ТОО ПКП «Контекст», 1995
  • Березина Л.Ю. Графы и их применение. Пособие для учителей. – М.: Просвещение, 1979.
  • Болховитинов В.Н., Колтовой Б.И., Лаговский И.К. Твоё свободное время. Занимательные задачи, опыты, игры. М., «Детская литература», 1975.
  • Лойд С. Математическая мозаика. Сост. и ред. М. Гарднер/ Пер. с англ. – М.: «РИПОЛ», 1995.
  • Малыгин К.А. Элементы историзма в преподавании математики в средней школе. – М.: Учпедгиз, 1958.
  • Олехник С.Н., Нестеренко Ю.В., Потапов М.К. Старинные занимательные задачи. – М.: Наука, 1988.
  • Шарыгин И.Ф., Ерганжиева Л.М. Наглядная геометрия. Учебное пособие для V – VI классов. – М.: МИРОС, КПЦ «МАРТА», 1992.
  • Энциклопедический словарь юного математика/ Сост. А.П. Савин. – М.: Педагогика, 1989.


Вернуться на страницу проекта Необычное в обычном или Чудеса в математике

Личные инструменты
Site Statistics