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

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

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

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

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

ИнфоурокМатематикаКонспектыУрок "Начала теории графов" (9 класс)

Урок "Начала теории графов" (9 класс)

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

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

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

Урок «Начала теории графов»

факультативного курса «теория графов и их приложения» (9 класс)



Начнем изучать теорию графов с задачи, вводя новые понятия по ходу рассмотрения: «Шахматный турнир проводится по круговой системе. Это означает, что каждая пара игроков встречается между собой ровно один раз. В турнире участвуют семь школьников. Известно, что Ваня сыграл шесть партий, Толя - пять, Леша и Дима - по три, Семен и Илья - по две, Женя - одну. С кем сыграл Леша?»

Для решения этой задачи школьнику не требуется как-либо специальных знаний из теории графов, достаточно лишь начальных сведений – понятий вершины и ребра, графа и подграфа, смежности вершин, степени вершины. Чтобы показать это изложим решение данной задачи сначала на интуитивном уровне, а затем формализуем его.

Представим школьный турнир в виде графа: пусть каждому из школьников соответствует одна вершина графа, и в случае, если два школьника сыграли партию, соединим соответствующие вершины ребром. Для краткости обозначим вершины: вершина 1 соответствует Ване, вершина 2 — Толе, вершина 3 — Леше, вершина 4 — Диме, вершина 5 — Семену, вершина 6 — Илье и вершина 7 — Жене.

На первом этапе решения зададим пустой граф (рис. 1)

K:\Все, что было на ноуте\Избрание\Портфолио Е.А.Моторина\Синергетика\1.png

Рис. 1

Выберем школьника, сыгравшего партии со всеми остальными - он должен сыграть на одну партию меньше числа участников, то есть 6 партий. В нашем случае – это Ваня, которому соответствует вершина 1. Соединим ее ребрами со всеми остальными вершинами – ведь Ваня сыграл со всеми школьниками, им сопоставленными. Отметим кружком вершину 1 как вершину для которой установлены все связи и которые не изменятся (рис. 2)

K:\Все, что было на ноуте\Избрание\Портфолио Е.А.Моторина\Синергетика\2.png

Рис. 2

Далее замечаем, что Женя сыграл всего одну партию, и ее он мог сыграть только с Ваней. Поэтому вершину 7, которая соответствует Жене тоже можно отметить кружком (рис. 3)

K:\Все, что было на ноуте\Избрание\Портфолио Е.А.Моторина\Синергетика\3.png

Рис. 3

Выберем школьника, сыгравшего партии со всем, кроме Жени, так как известно, что Женя сыграл только с Ваней. Он должен был сыграть 5 партий, причем одну из них с Ваней, и она уже отмечена на графе. В нашем случае, это Толя. Тогда наш граф примет вид как на рис. 4.

K:\Все, что было на ноуте\Избрание\Портфолио Е.А.Моторина\Синергетика\4.png

Рис. 4

Замечаем, что для Семена (вершина 5) и Ильи (вершина 6), которые сыграли по 2 партии также установлены все школьники, с которыми они сыграли, и эти вершины тоже можно отметить (рис. 5).

K:\Все, что было на ноуте\Избрание\Портфолио Е.А.Моторина\Синергетика\5.png

Рис. 5

В графе остались лишь две неотмеченные вершины, которые соответствуют Леше и Диме, сыгравшим по 3 партии. Поскольку в графе уже присутствуют ребра, соответствующие двум партиям, сыгранным Лешей и двум партиям, сыгранным Димой, а все остальные вершины – отмечены, то Леша с Димой эту третью партию могли сыграть только друг с другом (рис. 6).

K:\Все, что было на ноуте\Избрание\Портфолио Е.А.Моторина\Синергетика\6.png

Рис. 6

Итак, мы получили граф полностью отражающий все партии, сыгранные участниками турнира. Установим, с кем сыграл Леша. Ему соответствует вершина 3, которая соединена ребрами с вершинами 1, 2 и 4. Таким образом, Леша сыграл с Ваней, Толей и Димой.

При решении этой задачи на интуитивном уровне, нам потребовались лишь понятия графа, вершины и ребра. Однако после того, как эта задача решена, целесообразно ввести понятия смежности вершин, степени или валентности (обозначим ее deg (v)) вершины и подграфа, а затем разобрать более формализованное решение этой задачи. Представим этот вариант решения (изображения подграфов G1 и G2 для краткости изложения приводить не будем).

Пусть G — граф встреч игроков. Поскольку deg (1) = 6, то эта вершина соединена со всеми вершинами графа G, а так как deg (7) = 1, то она смежна только с вершиной 1. Рассмотрим подграф G1, порожденный множеством вершин {2, 3, 4, 5, 6}. Этот подграф получается из графа G удалением вершин 1 и 7 и всех ребер, выходящих из этих вершин. Поэтому в графе G1, который имеет 5 вершин (рис. 7 а), степени вершин будут deg (2) = 4, deg (3) = deg (4) = 2, deg (5) = deg(6) = 1.


J:\Все, что было на ноуте\Избрание\Портфолио Е.А.Моторина\Синергетика\7.png

Рис. 7

В графе G1 вершина 2 будет смежной со всеми вершинами, а вершины 5 и 6 — только с вершиной 2. Рассмотрим граф G2, порожденный множеством вершин {3,4}. Этот граф получается из графа G1 после удаления вершин 2, 5, 6 и всех ребер, выходящих из этих вершин. В графе G2 степени вершин 3 и 4 равны единице (см. рис. 7 б).

Возвратив удаленные вершины 2, 5, 6, получим граф G1. Возвратив теперь удаленные вершины 1 и 7, получим требуемый граф G (см. рис. 6). По этому графу можно также определить, с кем встречались остальные школьники.

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

Для занятий по теории графов со старшими школьниками, способными к построению и формализации алгоритмов решений, целесообразно также использовать средства специализированных математических пакетов. В качестве такового, можно предложить бесплатный математический пакет Scilab, имеющий в своем составе библиотеку Metanet, позволяющую оперировать с графами [3].


Литература

  1. Мельников О.И. Теория графов в занимательных задачах. Изд. 3-е, испр. и доп. - М.: Книжный дом «ЛИБРОКОМ», 2009

  2. Моторина Е.А. Роль и место теории графов в курсе математики общеобразовательной школы / Е.А. Моторина // Педагогические технологии в современном образовании. Часть II: материалы II Международной научно – практической конференции (г. Чебоксары, 16 июня 2014г.). – Образовательный центр «INCEPTUM», 2014. – 526с.

  3. Моторина Е.А. Графы в Scilab [Текст] / Е. А. Моторина // Педагогическое мастерство: материалы V междунар. науч. конф. (г. Москва, ноябрь 2014 г.). – М.: Буки-Веди, 2014.



Study of the Elements of Graph Theory in Optional Classes in Secondary School

E.A. Motorina


Gymnasium No 3, Russia, 414000 Astrakhan, pl. Shaumyan, 1a

e-mail: motorina.instes@gmail.ru


The article discusses the role of graph theory as a model to help solve problems in various areas of human activity are considered competence, which contributes to the formation of the study of graph theory in school, is an illustration for an example of the problem.

Краткое описание документа:

Предлагаемый материал представляет собой конспект урока "Начала теории графов" факультативного курса "Элементы теории графов и их приложения" (9 класс). Академик И.М.Яглом, в предисловии к книге О.Оре «Графы и их применение» отмечает, что несмотря на значительную важность для прикладной науки, «учение о графах очень подходит для изложения начинающим, поскольку соединяет большую геометрическую наглядность с математической содержательностью и с возможностью обходиться без громоздкого аппарата». Именно поэтому изучение теории графов можно рекомендовать в старших классах общеобразовательной школы.

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

Номер материала: ДВ-467538

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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