Разработка элективного курса по теории ориентированых графов и приложений Муниципальное бюджетное образовательное учреждение «Котлубанская средняя общеобразовательная школа Городищенского района Волгоградской области» Номинация: «Творческие мастерские» Сорокина Анна Андреевна учитель математики п. Котлубань 2012

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

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

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

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

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

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

Содержание программы. Программа курса рассчитана на учащихся старших классов. На изучение курса целесообразно отвести 8 часов. (1 час в 2 недели).

Учебно - методический план Ориентированый граф и его элементы. (1ч) Полустепень исхода d + (v). Полустепень захода d - (v). Цикл и контур орграфа. Сильносвязный (сильный) орграф. (1ч) Односторонний орграф. Конденсация орграфа. (1ч) Основа орграфа. Несвязный орграф. Корневое дерево.(1ч) Связный орграф.(1ч) Смешанный граф. Топологическая сортировка вершин орграфа. Турнир (1ч) Гамильтоновый орграф, (часть 1). (1ч) Гамильтоновый орграф, (часть 2). Обобщение. (1ч)

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

Ориентированные графы пара (V, Х), где Х V 2. элементы множества V называются вершинами орграфа G=(V, Х), а элементы множества Х его дугами. V4V4 V1V1 V2V2 V3V3 x1x1 x2x2 x3x3 x4x4

Смежность и инцидентность Вершины V 1 и V 2 инцидентны дуге x 1. Вершины V 1 и V 2 смежны. Ребра x 1 и x 2 смежны. V1V1 V2V2 x1x1 V1V1 V2V2 x1x1 V3V3 x2x2

Степень орграфа V1V1 V2V2 V4V4 V3V3 V5V5 x1x1 x2x2 x4x4 x7x7 x3x3 x5x5 x6x6 V 5 - изолированная вершина x 7 – петля x 1 и x 2 - параллельные дуги Полустепенью исхода d+(V 3 )=2 Полустепень захода d-(V 3 )=1 Deg (V)= d+(V)+ d-(V) Deg (V 3 )=3

Маршрут Ориентированным маршрутом в орграфе G называется такая последовательность S = (v 0, x 1, v 1, x 2, v 2, x 3, v 3, x 4,.., v n, x n,), его чередующихся вершин v i и дуг х i, что x i = (v i-1, v i ) (i = 1, n). V1V1 V2V2 V3V3 V4V4 x1x1 x2x2 x3x3 x4x4 V 1 X 1 V 2 X 2 V 3 X 3 V 4 X 4 V 2 - маршрут

Цепь V 1 X 1 V 2 X 3 V 2 X 4 V 3 - цепь из V 1 в V 3, длины 3. Цепь – маршрут, в котором все дуги различны V1V1 V2V2 V3V3 x1x1 x2x2 x3x3 x4x4

Путь Путь – маршрут, в котором все вершины, кроме, возможно, крайних, различны. V1V1 V2V2 V3V3 x1x1 x2x2 x3x3 x4x4 V 1 X 1 V 1 X 2 V 2 X 4 V 3 - путь V 1 в V 3, длины 3

Контур Контур – путь, у которого начальная и конечная вершины совпадают. V 1 X 1 V 1 X 2 V 2 X 3 V 2 X 4 V 3 X 5 V 3 X 6 V 1 - контур V1V1 V2V2 V3V3 x1x1 x2x2 x3x3 x4x4 x5x5 x6x6

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

Сильно связный орграф Орграф называется односторонним (односторонне-связным), если для любой пары его вершин, по меньшей мере, одна достижима из другой односторонний

Сильно связный орграф Орграф называется слабым (слабосвязным, связным), если для любых двух его вершины существует по крайней мере один маршрут, соединяющий их слабый

Эйлеровый ориентированный граф Связный орграф, называется эйлеровым, если в нем есть замкнутая эйлерова цепь. e1e1 e5e5 e3e3 e6e6 e4e4 e2e2 v3v3 v2v2 v1v1 v4v4 эйлерова цепь.

Гамильтоновый ориентированный граф Ориентированным гамильтоновым графом называется орграф, имеющий гамильтонов контур. Гамильтоновый контур e1e1 e2e2 e3e3 e4e4 e5e5 e 6 e 7 e 8 e 9

Какое максимальное число висячих вершин может иметь дерево с девятью вершинами? Какое минимальное число висячих вершин оно может иметь? Сделайте рисунки таких деревьев. Задача 1 Решение. Так как дерево с девятью вершинами имеет восемь ребер, то оно может иметь максимальное число висячих вершин, равное восьми (левый рисунок), а минимальное число висячих вершин – два (правый рисунок).

Из графа G удалите часть ребер так, чтобы новый граф был деревом, содержащим все вершины графа G. Задача 2 Решение.

Темы для рефератов и докладов учащихся Графы в головоломках; Графы в головоломках; Графы и игры на шахматной доске; Графы и игры на шахматной доске; Использование графов в школьных учебниках; Использование графов в школьных учебниках; Геометрическая задача о лабиринте; Геометрическая задача о лабиринте; Графы в решении логических задач; Графы в решении логических задач; Графы и подсчет числа изомеров; Графы и подсчет числа изомеров; Графы в генетике; Графы в генетике; Расчет сетевых графиков; Расчет сетевых графиков; Графы и транспортные сети; Графы и транспортные сети; Графы в электротехнике; Графы в электротехнике; Графы в психологии; Графы в психологии; Графы в физике; Графы в физике; Графы с цветными ребрами Графы с цветными ребрами