994812
столько раз учителя, ученики и родители
посетили сайт «Инфоурок»
за прошедшие 24 часа
+Добавить материал
и получить бесплатное
свидетельство о публикации
в СМИ №ФС77-60625 от 20.01.2015
Дистанционные курсы профессиональной переподготовки и повышения квалификации для педагогов

Дистанционные курсы для педагогов - курсы профессиональной переподготовки от 1.410 руб.;
- курсы повышения квалификации от 430 руб.
Московские документы для аттестации

ВЫБРАТЬ КУРС СО СКИДКОЙ ДО 90%

ВНИМАНИЕ: Скидка действует ТОЛЬКО до конца апреля!

(Лицензия на осуществление образовательной деятельности №038767 выдана ООО "Столичный учебный центр", г.Москва)

ИнфоурокМатематикаДругие методич. материалыФрагменты внеклассных занятий по теме "Графы"

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

Напоминаем, что в соответствии с профстандартом педагога (утверждён Приказом Минтруда России), если у Вас нет соответствующего преподаваемому предмету образования, то Вам необходимо пройти профессиональную переподготовку по профилю педагогической деятельности. Сделать это Вы можете дистанционно на сайте проекта "Инфоурок" и получить диплом с присвоением квалификации уже через 2 месяца!

Только сейчас действует СКИДКА 50% для всех педагогов на все 111 курсов профессиональной переподготовки! Доступна рассрочка с первым взносом всего 10%, при этом цена курса не увеличивается из-за использования рассрочки!

ВЫБРАТЬ КУРС И ПОДАТЬ ЗАЯВКУ
библиотека
материалов
Скачать материал целиком можно бесплатно по ссылке внизу страницы.

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

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













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



Общая информация

Номер материала: ДБ-191610

Вам будут интересны эти курсы:

Курс повышения квалификации «Табличный процессор MS Excel в профессиональной деятельности учителя математики»
Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
Курс повышения квалификации «Педагогическое проектирование как средство оптимизации труда учителя математики в условиях ФГОС второго поколения»
Курс профессиональной переподготовки «Математика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Изучение вероятностно-стохастической линии в школьном курсе математики в условиях перехода к новым образовательным стандартам»
Курс профессиональной переподготовки «Экономика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Специфика преподавания основ финансовой грамотности в общеобразовательной школе»
Курс повышения квалификации «Специфика преподавания информатики в начальных классах с учетом ФГОС НОО»
Курс повышения квалификации «Особенности подготовки к сдаче ОГЭ по математике в условиях реализации ФГОС ООО»
Курс профессиональной переподготовки «Теория и методика обучения информатике в начальной школе»
Курс профессиональной переподготовки «Инженерная графика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Развитие элементарных математических представлений у детей дошкольного возраста»
Курс повышения квалификации «Методика преподавания курса «Шахматы» в общеобразовательных организациях в рамках ФГОС НОО»
Курс повышения квалификации «Методика обучения математике в основной и средней школе в условиях реализации ФГОС ОО»
Курс профессиональной переподготовки «Черчение: теория и методика преподавания в образовательной организации»

Благодарность за вклад в развитие крупнейшей онлайн-библиотеки методических разработок для учителей

Опубликуйте минимум 3 материала, чтобы БЕСПЛАТНО получить и скачать данную благодарность

Сертификат о создании сайта

Добавьте минимум пять материалов, чтобы получить сертификат о создании сайта

Грамота за использование ИКТ в работе педагога

Опубликуйте минимум 10 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Свидетельство о представлении обобщённого педагогического опыта на Всероссийском уровне

Опубликуйте минимум 15 материалов, чтобы БЕСПЛАТНО получить и скачать данное cвидетельство

Грамота за высокий профессионализм, проявленный в процессе создания и развития собственного учительского сайта в рамках проекта "Инфоурок"

Опубликуйте минимум 20 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Грамота за активное участие в работе над повышением качества образования совместно с проектом "Инфоурок"

Опубликуйте минимум 25 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Почётная грамота за научно-просветительскую и образовательную деятельность в рамках проекта "Инфоурок"

Опубликуйте минимум 40 материалов, чтобы БЕСПЛАТНО получить и скачать данную почётную грамоту

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