Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Элективный курс
«Изучение элементов теории графов с использованием пакета Maple 5»
Данный факультатив предназначен для учащихся старших классов.
Цель данного факультатива – Ознакомить учащихся со средой Maple, с основными понятиями Теории графов. Изучить во время факультативных занятий основные функции пакета NetWorks. Научить применять и использовать Maple для решения поставленных задач.
- развитие у учащихся навыков рационального и сознательного использования новых информационных технологий в различных сферах деятельности; творческое применение новых информационных технологий при создании индивидуальных и коллективных проектов; развитие логического и операционного мышления.
Курс рассчитан на целый учебный год: количество часов – 32.
Тематическое планирование факультатива (курса).
|
№ |
Тема |
Кол-во часов |
|
1 |
Теория графов Вводное занятие (задачи приводящие к графам). Понятия: дерево, лес, цикл, граф, вершина, ребро, изолированная вершина. |
1 |
|
2 |
Основные понятия теории графов.
|
0,5 2 1,5 1 1 |
|
3 |
Деревья. Лес. Понятия: дерево, лес, висячая вершина. Теорема и доказательство. |
1 |
|
4 |
Изображение графа. Необходимое и достаточное условие соответствия двух рисунков одному и тому же графу. |
1 |
|
5 |
Плоские графы.
|
1 2 2 2 |
|
6 |
MAPLE Вводное занятие. Понятие Maple: компоненты, история, возможности. Примеры. |
1 |
|
7 |
Пакет Networks. Обзор пакета NetWorks – пакет графов. |
1 |
|
8 |
Функции создания графов. Функции: new, void, duplicate, complete, random. |
1 |
|
9 |
Функции модификации графов. Функции: addedges, addvertex, connect, delete. |
1 |
|
10 |
Функции контроля структуры графов. Функции: draw, edges, vertices, show, ends, head, tail, incidence, adjacency, eweight, vweight, isplanar, flow. |
2 |
|
11 |
Тест |
4 |
|
12 |
Проектная деятельность |
8 |
|
Итого: |
32 |
МЕТОДИКА ПРОВЕДЕНИЯ НЕКОТОРЫХ
ФАКУЛЬТАТИВНЫХ ЗАНЯТИЙ.
ТЕМА: Путь в графе. Цикл. (1ч.)
Основные определения: путь, цикл, длина путь, длина цикла, простой цикл.
Цели: Дать понятия пути в графе, цикл. Раскрыть сущность длинны цикла и длинны пути. Научить различать «путь» от «простого пути». Ознакомить с теоремой о чётности длинны простых циклов, доказать её. Дать задачи на закрепление пройденного материала.
План урока:
Ход урока:
Как пройти по ребрам на рисунке 1 из А1 в А5?
Вот три последовательности ребер, следуя которым можно попасть из А1 в А5:
1. (А1,А4); (А4,А5).
2. (А1,А2); (А2,А4); (А4,А5).
3. (А1,А4); (А4,А2); (А2,А1); (А1,А4); (А4,А5).
В одних — ребра повторяются, в других — не повторяются. Можно указать маршрут от А1 до А5, содержащий все вершины графа. Таков, например, маршрут: (А1,А2); (А2,А4); (А4,А3); (А3,А1); (А1,А4); (А4,А5). Но не всякую последовательность ре бер, ведущих из А1 в А5, называют путем из А1 в А5.
Путем от А1 до Аn в графе называется такая последовательность ребер, ведущая от А1 к Аn, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.
Вершина А1 — начало пути, вершина An — конец.
Из определения следует, что последовательность ребер (А1,А4); (А4,А2); (А2,А1); (А1,А4); (А4,А5) не является путем в графе.
Заметим, что согласно определению вершины пути могут повторяться, т. е. путь может быть самопересекающимся.
Путь от А1 до Аn называется простым, если он не проходит ни через одну из вершин графа более одного раза.
Решим несколько задач:
1. Найдите два пути, связывающие вершины А1 и А3 в графе (рис.2)
2. На рис. 3 изображен граф Г. Назовите один из путей от А1 до А6. Существует ли путь от А1 до А6, проходящий через все вершины графа?
3. Найдётся ли путь в графе Г от А1 до А8, содержащий все вершины графа (рис.4)?
4. Существует ли простой путь от А1 до А5, проходящий через все вершины графа (рис.1)?
Теперь мы можем дать определение цикла.
Циклом называется путь, в котором совпадают его начальная и конечная вершины.
Простым циклом в графе называется цикл, не проходящий ни через одну из вершин графа более одного раза.
Решение задач:
Какие из этих циклов простые?
Длиной пути называется число ребер этого пути.
Аналогично длиной цикла называется число ребер в этом цикле.
От вершины А1 до вершины А6 графа на рисунке 6 можно пройти четырьмя путями; один из них — длины 1, второй — длины 2 и два пути длиной 6. (Назовите все эти пути.)
Теорема: Если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.
Доказательство. Для графа, являющегося простым циклом, утверждение теоремы очевидно. Допустим, что у графа, все простые циклы которого четной длины, все же найдется цикл нечетной длины. Во всяком непростом цикле существует вершина, через которую, путь проходит более одного раза. В такой вершине цикл разобьется на два, причем один из них, очевидно, будет иметь нечетную длину, а другой — четную. Будем продолжать расчленение нечетного цикла до тех пор, пока не дойдем до простых циклов. Хотя бы один из них обязательно должен иметь нечетную длину. Существование такого простого цикла противоречило бы условию. Следовательно, принятое предположение неверно.
Введение понятия «путь» подвело нас к важному в математике понятию «связность».
Домашнее задание:
1.Найдите в графе (рис.5) циклы, содержащие:
Какие из этих циклов простые?
ТЕМА: Связность графа. (1ч.)
Основные определения: связность/несвязность вершин в графе, связность/несвязность графа.
Цели: Познакомить с основными определениями данной темы. Показать разницу между связным и несвязным графом. Дать теорему о связном графе, доказать её. Дать задачи на закрепление пройденного материала.
План урока:
4. новый материал (теорема и доказательство, самостоятельное доказательство обратной теоремы)
Ход урока:
Решим задачу.
3адача: Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими?
Решение. Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками — ребром. Изобразим графы, которые могут соответствовать такой компании (рис. 7 и 8).
Итак, ситуация, рассмотренная в задаче, вполне возможна. Но случай, рассмотренный на рисунке 8, соответствует не одной, а двум компаниям, участники одной из них не знакомы с участниками другой.
Про граф, изображенный на рисунке 7, говорят, что он связный, так как из каждой вершины по ребрам можно попасть в любую другую. Делаем вывод, что в этом случае каждый через своих знакомых может познакомиться со всеми остальными.
Во втором случае получились два простых цикла, не сцепленные между собой в вершинах. Такой граф называется несвязным. Дадим теперь определения связности вершин в графе и связности графа.
Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.
Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их.
Пример. В графе Г (рис. 9) вершины А и В — связные, а вершины А и Н — несвязные.
Граф называется связным, если каждые две вершины его связные.
Граф называется несвязным, если хотя бы две вершины его несвязные.
Пример. Графы на рисунках 6 и 7 связные. Графы на рисунках 8 и 9 связными не являются.
Порешаем задачки:
1.Нарисуйте граф с пятью вершинами, который не является связным.
Теорема: Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень 2.
Прямая теорема. Если Г — связный граф и степень каждой его вершины равна 2, тогда Г — простой цикл.
Доказательство. Из каждой вершины данного графа в любую другую ведет путь. Начнем путь из какой-нибудь вершины А и пройдем по одному из двух ребер, которым принадлежит эта вершина. Попав во вторую вершину, выйдем из нее по второму ребру и т. д. С необходимостью все ребра графа будут пройдены, и мы вернемся в исходную вершину А (рис. 10). Путь замкнется.
Обратная теорема. Если граф Г — простой цикл, тогда степень каждой его вершины равна двум.
Доказательство. (Самостоятельно) Так как граф Г — замкнутый про стой путь, то из каждой его вершины можно попасть в любую дру гую, не проходя ни через какую вершину более одного раза. Степень каждой вершины такого графа равна двум.
Покажем, что в простом цикле не может быть вершины, степень которой не равна двум.
Если какая-то вершина в графе имеет степень меньше двух, то она не принадлежит никакому простому циклу (рис. 11).
Если какая-то вершина имеет степень больше двух, то никакой простой цикл (по определению) не может содержать все ребра, которым принадлежит эта вершина (рис. 12).
Домашнее задание:
ТЕМА: Деревья. Лес. (2ч.)
Основные определения: дерево, лес, висячая вершина.
Цели: Ознакомить с понятиями дерево, лес. Вспомнить понятия связного/несвязного графа. Сформулировать и доказать теорему о количестве рёбер в дереве с b вершинами. Закрепить пройденный материал решением задач.
План урока:
Ход урока:
Прежде чем перейти к новой теме, выполним несколько упражнений:
Рассмотрим внимательно рисунки которые строили при решении задач 1-4. Что характерно для всех построенных графов? Во-первых они связные; во-вторых, они не содержат циклов. Такие графы выделяют в отдельный класс, представители которого именуются деревьями.
Вспомним определение связного, несвязного графа?
Деревом называется всякий связный граф, не имеющий циклов (рис. 1).
Удобно считать (удобство это скажется, в частности, при дока зательстве теоремы 1), что граф, состоящий из одной изолирован ной вершины, тоже является деревом. А как мы уже знаем изолированная вершина это?
Для каждой пары вершин дерева существует единственный соединяющий их путь.
Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке 1 висячие вершины выделены закрашенными кружками).
Лесом называется несвязный граф, представляющий объединение деревьев (рис. 2 и 3). Всякое ребро в дереве (и в лесе) является мостом.
Постройте какое-нибудь дерево с пятью вершинами и подсчитайте число ребер в полученном графе (Рисуют). Оказывается, что в любом дереве с пятью вершинами всегда будет четыре ребра.
Теорема 1: Дерево с в вершинами имеет (в — 1) ребро.
Для того чтобы из одного дерева Г, не являющегося изолированной вершиной, получить два дерева с теми же вершинами, необхо димо удалить из Г одно ребро. Для образования трех Деревьев необходимо удалить из Г два каких-нибудь ребра. Самое большее из дерева Г с вершинами можно получить в деревьев, каждое из которых является изолированной вершиной. Для этого необходимо удалить в— 1 ребро из дерева Г. Итак, действительно, в дереве с в вершинами в — 1 ребро.
Порешаем задачки на закрепление пройденного материала:
Кубок по настольному теннису разыгрывается по олимпийской системе. Встречи проводятся без ничьих. К очередному туру допу скается только победившая в предыдущем туре команда. Про игравшие выбывают из игры. Для завоевания кубка команда должна победить во всех турах.
На участие в розыгрыше кубка поданы заявки от 16 команд. Схема проведения игр изображается графом на рисунке 6.
Вершины нижнего «яруса» дерева (закрашенные) интерпрети руем как команды, участвующие в розыгрыше кубка, вершины вто рого снизу яруса — как команды-победительницы в 1/16 финала, вершины третьего яруса — как команды-победительницы в 1/8 финала и т. д.
Какую информацию можно получить с помощью этого дерева? Непосредственно с него считываются:
1) число всех участников розыгрыша кубка (число закрашен ных вершин);
2) число этапов проведения розыгрыша (число «ярусов» из вер шин в дереве, не считая нижнего);
3) число команд, участвующих в 1/8 финала, в 1/4 финала, в ½ финала (число вершин соответственно в четвертом сверху ярусе, в третьем сверху ярусе, во втором сверху ярусе);
4) число матчей, которые придется сыграть командам для выявления обладателя кубка (число не закрашенных вершин в графе). Кстати, это число легко определяется и без дерева. (В каждом матче выбывает одна команда. Для того чтобы была выявлена команда-победительница, остальные должны выбыть из соревнования. Поэтому число матчей равно числу команд без одной, а именно 15.)
Домашнее задание:
§ 3. ОРГАНИЗАЦИЯ ПРОЕКТНОЙ ДЕЯТЕЛЬНОСТИ УЧАЩИХСЯ.
Выполнение учебного проекта является завершающим этапом рассматриваемого курса проведения факультатива «Изучение элементов теории графов с использованием пакета Maple 5».
Требования к выполнению проекта
Подготовительный этап:
Бумажное проектирование:
Требование к проекту:
Защита проекта: