Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Фрагменты внеклассных занятий по теме "Графы"

Фрагменты внеклассных занятий по теме "Графы"

  • Математика

Поделитесь материалом с коллегами:

Фрагменты внеклассных занятий по теме «Графы»

I.Фрагмент занятия по теме: «Одним росчерком пера».

(творческие задания, беседа с учителем, поиск решений, математическая игра).

Вначале занятия учитель формулирует задачу о Кёнигсбергских мостах и предлагает ученикам решить её.

«Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кенинсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз»

hello_html_7abc1577.pnghello_html_m3ce92bf8.png

Схема мостов и соответствующий ей граф

Буква Л обозначает левый берег, П – правый, А и Б – острова.

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

Учитель знакомит с содержанием теоретической части.

Граф, допускающий путь, не содержащий кратных ребер и содержащий все ребра, называется эйлеровым. Такой путь тоже называется эйлеровым.

Задача о Кенигсбергских мостах имеет решение тогда и только тогда, когда этот граф является эйлеровым.

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

Пример. Рассмотрим графы, приведенные на рис. 1 («открытое письмо» и «закрытое письмо») и проверим, являются ли они эйлеровыми. Поскольку граф, приведенный слева («закрытое письмо») имеет четыре вершины нечетной степени, то по теореме он не будет эйлеровым. Значит, его невозможно нарисовать, не отрывая карандаш и проходя каждую линию ровно один раз. Граф, приведенный справа, имеет две вершины нечетной степени, следовательно, по теореме он является эйлеровым, и его можно нарисовать, не отрывая карандаш и проходя каждую линию ровно один раз.

hello_html_22807bc.png

рис.1


Задачи.

  1. Начертить граф свершинами (1,2,3,4,5) и ребрами (1,2), (2,3), (3,4), (3,1), (4,5), является ли этот граф эйлеровым?

Ответ: да, это эйлеров граф.





  1. Начертить граф с вершинами (А, Б, В, Г) и ребрами (А,Г), (А,Б), (Б,В), является ли этот граф эйлеровым?

Ответ: да, это эйлеров граф.



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




















Математическая игра: Усадьба Хакенбуш.

Эту игру придумал математик Джон Конвей. Для игры используется картинка с "усадьбой Хакенбуш". А именно: картинка должна быть в рамке; все ее элементы должны быть связаны с рамкой; все соединения линий ограничиваются точками.  За один ход игрок стирает один любой отрезок картинки, ограниченный точками или одной точкой, если отрезок это петля.Если после удаление этой линии, часть линий оказывается не связанной с рамкой, то она удалятся тоже. На рисунке пример, где удалятся линия, выделенная зеленым цветом, и вместе с ней удаляются линии дыма, выделенные красным.Игрок, который удаляет последний элемент картинки выигрывает.


hello_html_1b7e67d0.png


Подведём итоги:

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

  • Граф с двумя нечетными вершинами можно начертить одним росчерком, начиная движение с одной и заканчивая на другой нечетной вершине.

  • Граф с более чем двумя нечетными вершинами нельзя начертить одним росчерком.


II. Фрагмент занятия по теме: «Путешествия по лабиринтам».

(ученик в роли учителя, беседа, поисковые задачи, соревнования, творческое задание).

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

Примерное содержание сообщения учеников.

  • Происхождение задач о лабиринтах относится к глубокой древности и теряется во мраке времен.

  • Слово «лабиринт» (греческое) означает «ходы в подземельях».

  • Возможен ли безвыходный лабиринт?

  • Задача о прохождении лабиринта приобретает практический интерес, поскольку устройство линий электропередач, канализации, сетей дорог, каналов и т.д. – все это более или менее сложные лабиринты.

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

Геометрическая постановка задачи о лабиринтах

Аллеи, дорожки, коридоры, галереи, шахты и тому подобные лабиринты тянутся, изгибаясь во все стороны, перекрещиваются, расходятся по всевозможным направлениям, ответвляются, образуют тупики и так далее. Лабиринт — это граф. Все перекрестки обозначим вершинами, а все аллеи, дорожки, коридоры и т.д. будут ребрами. Если какая-либо точка, движущаяся по ребру графа, может прийти к любой другой вершине, не покидая ребра, приняв это, докажем, что подобная движущаяся точка (например, человек) может последовательно описать все ребра без всяких скачков и перерывов и при этом по каждому ребру она пройдет ровно два раза. Другими словами, лабиринт всегда может быть разрешен.

Решение задачи о лабиринтах

Правило 1. Отправляемся от выбранной вершины (первого перекрестка) и идем по любому ребру, пока не приходим или в тупик (к вершине), или к новому перекрестку (вершине).

Тогда:

  1. Если окажется, что мы попали в тупик, возвращаемся назад и пройденное ребро должно быть уже отброшено, так как мы прошли его два раза (туда и обратно).

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

Пример.

hello_html_m615626a8.gif



Направление движения показано стрелкой hello_html_m55b8ee0c.png. После прихода к пересечению путей выбирается направление, обозначенное стрелкой hello_html_12a1547a.png. Оба пути помечаются черточкой. (Крестиками обозначаются черточки, поставленные при последнем прохождении через перекресток.)

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

Правило 2. Прибыв на известный нам перекресток по новой дороге, мы должны сейчас же повернуть обратно, предварительно отметив этот путь двумя черточками (прибытие и обратное отправление), как показано на рисунке.

hello_html_54108b30.gif



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

hello_html_7f15fc7c.gif



Но если такого пути нет, то выбирается дорога, по которой мы прошли только один раз. Случай этот показан на рисунке.

hello_html_79803760.gif

Правило 4. Правило одной руки. Оно состоит в том, что по лабиринту надо двигаться, не отрывая одной руки (правой или левой) от стены.

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



Задачи

  1. Нарисуйте граф, соответствующий данному лабиринту.


hello_html_m2c2db54.jpg







  1. Убедитесь в том, что, войдя в лабиринт, изображенный на рисунке, можно, касаясь правой рукой стены, дойти до центра и вернуться.

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

  3. Как можно достать из муравейника зернышко.

hello_html_m5d28cfcf.jpg








5. Это лабиринт английского короля Вильгельма III, состоит из аллей и изгородей. Нужно пройти в центр к деревьям и скамейкам под ними. Найдите путь к беседке, расположенной в парке.



hello_html_51c5ddda.jpg













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



Автор
Дата добавления 13.09.2016
Раздел Математика
Подраздел Другие методич. материалы
Просмотров38
Номер материала ДБ-191610
Получить свидетельство о публикации
Похожие материалы

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