Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

Изучение элементов теории графов с использованием пакета Mple 5 Данный факультатив предназначен для учащ

Работа добавлена на сайт samzan.ru: 2015-07-05

Элективный курс

«Изучение элементов теории графов с использованием пакета Maple

Данный факультатив предназначен для учащихся старших классов.

Цель данного факультатива – Ознакомить учащихся со средой Maple, с основными понятиями Теории графов. Изучить во время факультативных занятий основные функции пакета NetWorks. Научить  применять и использовать Maple для решения поставленных задач.

- развитие у учащихся навыков рационального и сознательного использования новых информационных технологий в различных сферах деятельности; творческое применение новых информационных технологий при создании индивидуальных и коллективных проектов; развитие логического и операционного мышления.

Курс рассчитан на целый учебный  год: количество часов – 32.

Тематическое планирование факультатива (курса).

Тема

Кол-во часов

1

Теория графов

Вводное занятие (задачи приводящие к графам).

Понятия: дерево, лес, цикл, граф, вершина, ребро, изолированная вершина.

1

2

Основные понятия теории графов.

  1.  Полный граф. Дополнение графа
  2.  Степень вершины. Чётная, нечётная вершина. Теоремы и доказательства.
  3.  Путь в графе. Цикл. Простой цикл. Длина пути. Длина цикла. Теорема и доказательство.
  4.  Связность графа. Связность, несвязность вершин в графе. Связный, несвязный граф. Теорема и доказательство.
  5.  Операция удаления ребра. Мост. Теорема и доказательство.

0,5

2

1,5

1

1

3

Деревья. Лес.

Понятия: дерево, лес, висячая вершина. Теорема и доказательство.

1

4

Изображение графа.

Необходимое и достаточное условие соответствия двух рисунков одному и тому же графу.

1

5

Плоские графы.

  1.  Плоский граф. Грань в плоском графе. Граница грани. Соединение грани. Бесконечная грань.
  2.  Формула Эйлера. Теорема о плоских графов.
  3.  Эйлеровы графы. Эйлеров путь. Эйлеров цикл. Теоремы и доказательства.
  4.  Гамильтоновы циклы и пути в графах. Додекаэдр. Гамильтонов граф. Условия существования гамильтоновых циклов в графе.  

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.  новый материал (путь)
  2.  решение задач для понимания материала
  3.  новый материал (цикл, простой цикл)
  4.  решение задач на закрепление материала
  5.  новый материал (длина пути, длина цикла, теорема и доказательство)
  6.  домашнее задание

Ход урока:

Как пройти по ребрам на рисунке 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.  Найдите в графе (рис.5) циклы, содержащие:
    1.  4 ребра
    2.  6 ребер

Какие из этих циклов простые?

  1.  Изобразите простой цикл с шестью вершинами и посчитайте, сколько у него рёбер. А из скольких рёбер состоит простой цикл, если у него 10 вершин? Если 15 вершин?
  2.  Каково наименьшее число рёбер в простом цикле?

Длиной пути называется число ребер этого пути.

Аналогично длиной цикла называется число ребер в этом цикле.

От вершины А1  до вершины А6 графа на рисунке 6 можно пройти четырьмя путями; один из них — длины 1, второй — длины 2 и два пути длиной 6. (Назовите все эти пути.)

Теорема: Если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

Доказательство. Для графа, являющегося простым циклом, утверждение теоремы очевидно. Допустим, что у графа, все простые циклы которого четной длины, все же найдется цикл нечетной длины. Во всяком непростом цикле существует вершина, через которую, путь проходит более одного раза. В такой вершине цикл разобьется на два, причем один из них, очевидно, будет иметь нечетную длину, а другой — четную. Будем продолжать расчленение нечетного цикла до тех пор, пока не дойдем до простых циклов. Хотя бы один из них обязательно должен иметь нечетную длину. Существование такого простого цикла противоречило бы условию. Следовательно, принятое предположение неверно.

Введение понятия «путь» подвело нас к важному в математике понятию «связность».

Домашнее задание:

1.Найдите в графе (рис.5) циклы, содержащие:

  1.  5 ребер
    1.  10 ребер

        Какие из этих циклов простые?

  1.  Сколько рёбер в простом цикле с b вершинами?

ТЕМА: Связность графа. (1ч.)

Основные определения: связность/несвязность вершин в графе, связность/несвязность графа.

Цели: Познакомить с основными определениями данной темы. Показать разницу между связным и несвязным графом. Дать теорему о связном графе, доказать её. Дать задачи на закрепление пройденного материала.

План урока:

  1.  решение задачи для перехода к новой теме
    1.  новый материал (связность/несвязность вершин в графе, связность/несвязность графа)
    2.  решение задач на понимание и закрепление нового материала

4. новый материал (теорема и доказательство, самостоятельное доказательство обратной теоремы)

  1.  домашнее задание

Ход урока:

Решим задачу.

3адача: Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими?

Решение. Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками — ребром. Изобразим графы, которые могут соответствовать такой компании (рис. 7 и 8).

Итак, ситуация, рассмотренная в задаче, вполне возможна. Но случай, рассмотренный на рисунке 8, соответствует не одной, а двум компаниям, участники одной из них не знакомы с участниками другой.

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

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

Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.

Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их.

Пример. В графе Г (рис. 9) вершины А и В — связные, а вершины А и Н — несвязные.

Граф называется связным, если каждые две вершины его связные.

Граф называется несвязным, если хотя бы две вершины его несвязные.

Пример. Графы на рисунках 6 и 7 связные. Графы на рисунках 8 и 9 связными не являются.

Порешаем задачки:

1.Нарисуйте граф с пятью вершинами, который не является связным.

  1.  «Дорисуйте» граф, изображенный на рис.9, так, чтобы он оказался связным.
  2.  Назовите пути наименьшей и наибольшей длинны от вершины А1 до вершин А2 и А7 в графе на рис.4

Теорема: Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень 2.

Прямая теорема. Если Г связный граф и степень каждой его вершины равна 2, тогда Г простой цикл.

Доказательство. Из каждой вершины данного графа в любую другую ведет путь. Начнем путь из какой-нибудь вершины А и пройдем по одному из двух ребер, которым принадлежит эта вершина. Попав во вторую вершину, выйдем из нее по второму ребру и т. д. С необходимостью все ребра графа будут пройдены, и мы вернемся в исходную вершину А (рис. 10). Путь замкнется.

Обратная теорема. Если граф Г простой цикл, тогда степень каждой его вершины равна двум.

Доказательство. (Самостоятельно) Так как граф Г — замкнутый простой путь, то из каждой его вершины можно попасть в любую другую, не проходя ни через какую вершину более одного раза. Степень каждой вершины такого графа равна двум.

Покажем, что в простом цикле не может быть вершины, степень которой не равна двум.

Если какая-то вершина в графе имеет степень меньше двух, то она не принадлежит никакому простому циклу (рис. 11).

Если какая-то вершина имеет степень больше двух, то никакой простой цикл (по определению) не может содержать все ребра, которым принадлежит эта вершина (рис. 12).

Домашнее задание:

  1.  Нарисуйте граф  с 7-ю вершинами, который не является связным. С 8-ю.
  2.  Напишите все пути от вершины А1 до А8 и А5 (рис.4).

ТЕМА: Деревья. Лес. (2ч.)

Основные определения: дерево, лес, висячая вершина.

Цели: Ознакомить с понятиями дерево, лес. Вспомнить понятия связного/несвязного графа.  Сформулировать и доказать теорему о количестве рёбер в дереве с b вершинами. Закрепить пройденный материал решением задач.

План урока:

  1.  решение задач для перехода к новой теме
    1.  новый материал
    2.  решение задач на закрепление нового материала
    3.  домашнее задание

Ход урока:

Прежде чем перейти к новой теме, выполним несколько упражнений:

  1.  Нарисуйте граф с семью вершинами и шестью рёбрами, не имеющий ни одного цикла.
  2.  Нарисуйте связный граф с семью вершинами и шестью рёбрами.
  3.  Нарисуйте граф с семью вершинами, в котором для любых двух вершин существует один и только один путь связывающий их.
  4.  Постройте связный граф с семью вершинами, каждое ребро которого – мост.

Рассмотрим внимательно рисунки которые строили при решении задач 1-4. Что характерно для всех построенных графов? Во-первых они связные; во-вторых, они не содержат циклов. Такие графы выделяют в отдельный класс, представители которого именуются деревьями.

Вспомним определение связного, несвязного графа?

Деревом называется всякий связный граф, не имеющий циклов (рис. 1).

Удобно считать (удобство это скажется, в частности, при доказательстве теоремы 1), что граф, состоящий из одной изолированной вершины, тоже является деревом. А как мы уже знаем изолированная вершина это?

Для каждой пары вершин дерева существует единственный соединяющий их путь.

Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке 1 висячие вершины выделены закрашенными кружками).

Лесом называется несвязный граф, представляющий объединение деревьев (рис. 2 и 3). Всякое ребро в дереве (и в лесе) является мостом.

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

Теорема 1: Дерево с в  вершинами имеет (в 1) ребро.

Для того чтобы из одного дерева Г, не являющегося изолированной вершиной, получить два дерева с теми же вершинами, необходимо удалить из Г одно ребро. Для образования трех Деревьев необходимо удалить из Г два каких-нибудь ребра. Самое большее из дерева Г с вершинами можно получить в деревьев, каждое из которых является изолированной вершиной. Для этого необходимо удалить в— 1 ребро из дерева Г. Итак, действительно, в дереве с в вершинами в — 1 ребро.

Порешаем задачки на закрепление пройденного материала:

  1.  Какое максимальное число висячих вершин может иметь дерево, обладающее 9 вершинами? Какое минимальное число висячих вершин оно может иметь? Сделайте рисунки таких деревьев.
  2.  Докажите, что лес, состоящий из k деревьев и содержащий b вершин, имеет b-k рёбер.
  3.  Из графа Г (рис.4) удалите часть рёбер так, чтобы новый граф был деревом, содержащим все вершины графа Г.
  4.  Сколько рёбер надо удалить из связного графа, имеющего р рёбер и b вершин, чтобы получить дерево, содержащее все вершины этого графа?
  5.  Приведите примеры графа, из которого нельзя выделить дерево, содержащее все вершины графа.
  6.   Задан граф (рис. 5), какое наибольшее число рёбер можно удалить, чтобы граф остался связным?

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

На участие в розыгрыше кубка поданы заявки от 16 команд. Схема проведения игр изображается графом на рисунке 6.

Вершины нижнего «яруса» дерева (закрашенные) интерпретируем как команды, участвующие в розыгрыше кубка, вершины второго снизу яруса — как команды-победительницы в 1/16 финала, вершины третьего яруса — как команды-победительницы в 1/8 финала и т. д.

Какую информацию можно получить с помощью этого дерева? Непосредственно с него считываются:

1) число всех участников розыгрыша кубка (число закрашенных вершин);

2) число этапов проведения розыгрыша (число «ярусов» из вершин в дереве, не считая нижнего);

3) число команд, участвующих в 1/8 финала, в 1/4 финала, в ½ финала (число вершин соответственно в четвертом сверху ярусе, в третьем сверху ярусе, во втором сверху ярусе);

4) число матчей, которые придется сыграть командам для выявления обладателя кубка (число не закрашенных вершин в   графе). Кстати, это число легко определяется и без дерева. (В каждом матче выбывает одна команда. Для того чтобы была выявлена команда-победительница, остальные должны выбыть из соревнования. Поэтому число матчей равно числу команд без одной, а именно 15.)

Домашнее задание:

  1.  Если в розыгрыше кубка по олимпийской системе участвуют 19 команд, то схема проведения розыгрышей может быть такой, как на рис.7. Шести командам, выбранным по жеребьёвке, придётся провести дополнительные встречи. Объясните:
    1.  Что характеризует число висячих вершин?
    2.  Что обозначают не висячие вершины?
    3.  Сколько матчей необходимо провести для выявления победителя?
  2.  Сколько матчей необходимо провести для того, чтобы выявить по олимпийской системе обладателя кубка среди 147 команд?


§ 3. ОРГАНИЗАЦИЯ ПРОЕКТНОЙ ДЕЯТЕЛЬНОСТИ УЧАЩИХСЯ.

Выполнение учебного проекта является завершающим этапом рассматриваемого курса проведения факультатива «Изучение элементов теории графов с использованием пакета Maple 5».

Требования к выполнению проекта

Подготовительный этап:

  1.  определить тему проекта:
    1.  
  2.  разбиться на группы.

Бумажное проектирование:

  1.  поиск и анализ источников информации;
  2.  исследование предметной области выполняемого проекта;
  3.  бумажное проектирование.

Требование к проекту:

Защита проекта:

  1.  Качество и полнота выполненной работы
  2.  Организация работы в группах
  3.  Наличие в работе творческой деятельности
  4.  Защита работ
  5.  Активность участия на итоговом занятии


1. х гг 20 века однако убедительные доказательства возможности такой трансформации были получены сравнительно
2. Бикини это история любви немки и американца которая разворачивается в конце Второй мировой войны
3. Исчисления предикатов и их применение в логическом умозаключении
4. Реферат- Почему искажается историческая правда (методологический аспект проблемы)
5. Реферат- Житие княгини Ольги XVI века
6. методические рекомендации по производственной практике составлены на основании методических рекомендаций
7.  Добро пожаловать гости дорогие Веселья вам да радости желаем Давно мы вас ждем поджидаем Праздник
8. I Il est midi ce mrdi et en ce moment j~ttends Je suis rriv~ il y une heure ~ onze heures l~heure de mon rendezvous vec l jolie employ~e de l~gence immobili~re qui doit me fire visite
9. лекция ~имараттар мен ~~рылыстарды ~айта салу ~имараттар мен ~~рылыстарды ~айта салу ~ б~л оларды~ ~ыз
10. Кто ищет тот всегда найдет Что найти суждено на дороге лежит Узбекская пословица
11.  Значение древних цивилизаций в истории мировых цивилизацийГлавным субъектом исторического процесса являе
12. Національний доход- суть, виробництво, розподіл і використання.html
13. ~аза~стан Республикасыны~ 2020 жыл~а дейінгі дамуыны~ стратегиялы~ жоспары туралыжарлы~ы; ~аза~стан Респ
14. религия имеет несколько распространенных значений
15. Лабораторная работа 4 Выбор рациональной длины пакета сети ЭВМ 1
16. рактеристик индивидуума или группы индивидуумов на континууме шкале относительно одной из его характерист
17. Калинка Хореографический коллектив Ягодка ДК филиала ООО Газпром трансгаз Моск
18. ТЕМА Социальное неравенство и стратификация Выполнила студентка 2го курса экономическ
19. Шаврина Екатерина Феоктистовна
20. Древнее египетских пирамид ~ этим выражением пользуются когда слово допотопный кажется слишком невыраз