Цели занятия: изучить основные понятия теории графов, научиться определять степень вершин графа, рисовать полный граф с заданным количеством вершин, рисовать граф, который является дополнением к заданному графу.
Задачи занятия.
Образовательные: дать знания об основных понятиях теории графов.
Развивающая: формирование и развитие у учащихся познавательных способностей; развитие познавательного интереса к предмету; развитие логического и пространственного мышления; развитие умения планировать свою деятельность.
Воспитательная: воспитание интереса к изучаемому предмету, навыков внимания, аккуратности, умения сосредотачиваться, коллективного труда, самостоятельной работы.
Вид занятия: комбинированный.
Тип занятия: занятие формирования и совершенствования знаний.
Форма проведения занятия: лекция, коллективная работа, индивидуальная работа.
Оснащение и методическое обеспечение занятия.
- Доска.
- Цветной мел (или маркеры).
- Цветные магниты.
План занятия
- Организационный момент.
- Постановка целей и задач.
- Изложение нового материала
- Закрепление изученного материала.
- Работа у доки.
- Анализ ошибок
- Самостоятельная работа.
- Подведение итогов занятия.
- Оценка степени реализации поставленных целей.
- Оценка работы студентов.
- Задание к следующему занятию. Рекомендации к его выполнению.
- Общая оценка всего занятия.
Ход занятия
1. Организационный момент.
Минибеседа о готовности студентов к уроку, создание деловой и доброжелательной атмосферы, подготовка аудитории к уроку. Проверка отсутствующих.
2. Постановка целей и задач.
Преподаватель сообщает тему, цель и задачи занятия:
- Тема нашего занятия: “Графы”.
- Цель и задачи нашего занятия: изучить основные понятия графов, научиться определять степень вершин графа, рисовать полный граф с заданным количеством вершин, рисовать граф, который является дополнением к заданному графу.
3. Изложение нового материала.
Все рисунки изображаются на доске (можно для наглядности использование цветного мела для рисования ребер графа и цветных магнитов для изображения вершин графа).
Исторически сложилось так, что теория графов зародилась в ходе решения головоломок почти триста лет назад. Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топологии и комбинаторики. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнига в 30-е годы XX столетия.
В настоящее время графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистики, логистики, экономики, биологии, медицине. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.
Графы получили широкое распространение в различных областях нашей жизни, т.к. они являются естественным и удобным способом изображения и дальнейшего анализа различных сложных сетей. Примеры графов в нашей жизни: схема электротранспорта в городе (висит в каждом троллейбусе и трамвае); схема метро (в городах, где построен метрополитен); иерархические структуры такие как генеалогическое древо, иерархия подчинения в армии, иерархия подчинения на предприятии; схемы проведения чемпионата по футболу, теннису и пр.; структура газопровода или нефтепровода в регионе и т.д.
Что общего у вышеперечисленных схем? Все они состоят из точек (кружков) и отрезков, соединяющих пары точек. Рассмотрение таких схем и приводит к понятию графа.
Определение 1. Графом G называется множество точек и множество линий, соединяющих некоторые пары точек. Точки называют вершинами или узлами, отрезки – ребрами графа.
Пример 1: граф с шестью вершинами и шестью ребрами (рис. 1).
Рисунок 1.
Пример 2: граф с тремя вершинами и тремя ребрами (рис. 2).
Рисунок 2
Пример 3: граф с семью вершинами и шестью ребрами (рис. 3).
Рисунок 3
Обычно вершины обозначают заглавными буквами (A,B,C,D…), а ребра – парой вершин, которое ребро соединяет: (А,B), (A,D) и т.д.
Определение 2. Ребро, соединяющее две вершины, называется инцидентным этим вершинам. При этом сами вершины, которые соединены ребром – смежными.
Пример 4: На рис. 1 ребро (DE) инцидентно вершинам D и E; а сами вершины D и E будут смежными.
Определение 3. Число ребер, инцидентных вершине М называется степенью этой вершины и обозначается deg(M).
Пример 5: На рис. 3 степень вершины D равна трем, степень вершины F равна нулю, а степень вершины E равна двум, т.е. deg(D)=3, deg(F)=0, deg(E)=2.
Определение 4. Если степень вершины равна нулю, то такая вершина называется изолированной.
Пример 6: На рис. 3 вершина F изолирована.
Определение 5. Если степень вершины равна единице, то такая вершина называется висячей.
Пример 7: На рис. 3 вершина G висячая.
Определение 6. Если ребро соединяет одну и ту же вершину, то такое ребро называется петлей.
Пример 8: На рис. 3 вершина Е имеет петлю.
Определение 7. Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром.
Пример 9: На рис. 4 полный граф с четырьмя вершинами.
Рисунок 4
Определение 7. Дополнением графа G
называется граф 
с теми
же вершинами, что и граф G, и теми и только теми
ребрами, которые необходимо добавить к графу G,
чтобы получился полный граф.
Пример 10: На рис. 5 произвольный граф G, а
на рис. 6 граф , являющийся дополнением к графу G
Рисунок 5
Рисунок 6
4. Закрепление изученного материала.
5. Работа у доки.
У доски выполняются следующие упражнения
Задание 1. Дан граф G (рис. 7-12). Для каждой вершины определить ее степень.
1.1.
Рисунок 7
1.2.
Рисунок 8
1.3.
Рисунок 9
1.4.
Рисунок 10.
1.5.
Рисунок 11
1.6.
Рисунок 12
Пример выполнения этого задания:
Дан граф G. (рис. 13) Для каждой вершины определить ее степень
Рисунок 13
Решение:
Для каждой вершины считаем ребра, которые ей инцидентны, т.е. те, которые выходят из этой вершины. Изолированная точка имеет степень, равную нулю, а если вершине инцидентна петля, то она дает вклад в степень, равный двум, так как оба конца приходят в эту вершину.
deg(A)=3, deg(B)=2, deg(C)=2, deg(D)=4, deg(E)=3, deg(F)=3, deg(G)=1, deg(I)=0
Ответ: deg(A)=3, deg(B)=2, deg(C)=2, deg(D)=4, deg(E)=3, deg(F)=3, deg(G)=1, deg(I)=0
Задание 2. Нарисуйте полный граф с n вершинами.
2.1. n=2
2.2. n=3
2.3. n=5
2.4. n=6
Задание 3. Нарисуйте граф , являющийся дополнением графа G
(рис. 14-17).
3.1.
Рисунок 14
3.2.
Рисунок 15
3.3.
Рисунок 16
3.4.
Рисунок 17
Пример выполнения этого задания:
Дан граф G (рис. 18). Нарисуйте граф , являющийся
дополнением графа G.
Рисунок 18.
Решение:
В графе G 5 вершин, значит, в полном графе
из каждой вершины должно исходить по 4 ребра
(тогда эта вершина будет соединена с остальными
вершинами). Поэтому, дополнением графа G будет
граф (рис. 19),
который содержит те же вершины и недостающие
ребра:
Рисунок 19
4.2. Анализ ошибок.
Преподаватель акцентирует внимание на допущенных ошибках, чтобы студенты не допустили их при выполнении самостоятельной работы и при выполнении домашнего задания. При необходимости напоминает некоторые теоретические моменты.
4.3. Самостоятельная работа.
Студентам раздаются карточки заданием:
а) Нарисуйте произвольный граф G, содержащий не менее 5 вершин и не более 10.
б) Для каждой вершины определите степень.
в) Нарисуйте граф , являющийся дополнением графа G.
5. Подведение итогов занятия.
5.1. Оценка степени реализации поставленных целей.
Преподаватель оценивает степень реализации поставленных целей и задач
5.2. Оценка работы студентов.
Преподаватель вместе со студентами дает общую оценку работы всей группы в целом и некоторых студентов в частности.
5.3. Задание к следующему уроку. Рекомендации к его выполнению.
Задание 4. Дан граф G. Для каждой вершины определить ее степень
4.1.
Рисунок 20
4.2.
Рисунок 21
4.3.
Рисунок 22
Задание 5. Нарисуйте полный граф с n вершинами.
5.1. n = 4
5.2. n = 7
Задание 6. Нарисуйте граф , являющийся дополнением графа G
(рис. 23-24).
6.1.
Рисунок 23
6.2.
Рисунок 24
6. Общая оценка всего занятия.
Преподаватель вместе со студентами дает общую оценку занятия, работы всей группы. Обсуждаются удачные и неудачные моменты. Преподаватель всех благодарит за участие и сообщает о завершении занятия.
Список литературы.
- Спирина М.С. Дискретная математика: Учебник для студ. учреждений сред. проф. образования. – М.: Издательский центр “Академия”. 2004.
- Березина Л.Ю. Графы и их применение: пособие для учителей. –М.: Просвещение, 1979.