ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ 
ИНСТИТУТ ИНФОРМАТИЗАЦИИ ОБРАЗОВАНИЯ РАО
АДМИНИСТРАЦИЯ ГОРОДСКОГО ОКРУГА ТРОИЦК В ГОРОДЕ МОСКВЕ 
РЕГИОНАЛЬНЫЙ ОБЩЕСТВЕННЫЙ ФОНД НОВЫХ ТЕХНОЛОГИЙ В ОБРАЗОВАНИИ «БАЙТИК»
АНО «ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В ОБРАЗОВАНИИ» 
 XXV МЕЖДУНАРОДНАЯ КОНФЕРЕНЦИЯ
 «ПРИМЕНЕНИЕ НОВЫХ ТЕХНОЛОГИЙ В ОБРАЗОВАНИИ»  
«ИТО-Троицк-2014»
25-26 июня 2014 года, г.Москва, г.о. Троицк

ОБУЧЕНИЕ ТЕОРИИ ГРАФОВ С ПОМОЩЬЮ СИСТЕМЫ ДИНАМИЧЕСКОЙ ГЕОМЕТРИИ GEOGEBRA.

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

ОБУЧЕНИЕ ТЕОРИИ ГРАФОВ С ПОМОЩЬЮ СИСТЕМЫ ДИНАМИЧЕСКОЙ ГЕОМЕТРИИ GEOGEBRA.

Большакова Наталья Сергеевна (natabolll@mail.ru)

Мурманский Государственный Гуманитарный Университет (МГГУ)

 

Аннотация. Рассмотрено применение встроенных команд бесплатно распространяемой системы динамическойгеометрии GeoGebra при решении прикладных задач с помощью построения интерактивных графовых моделей.

 

На сегодняшний момент одной из самых популярных систем  динамической геометрииявляется свободно распространяемая кроссплатформенная  система динамической геометрии GeoGebra (СДГ GeoGebra), первая версия которой появилась в 2002 году и за последние двенадцать лет сменила 7 версий (GeoGebra 1.0 (2002), GeoGebra 2.0 (2004 год), GeoGebra 3.0 (2009 год), GeoGebra 3.2 (2009 год), GeoGebra 4.0 (2011 год), GeoGebra 4.2 (2012 год), GeoGebra 4.4 (2013 год)). [Официальный сайт программы http://www.geogebra.org/cms/ru/]. В СДГ GeoGebra чертеж является моделью, которая легко изменяется, при этом оставаясь одним целым (перемещение точек, введение новых числовых значений и т.д.). Сами изменения сразу видны на экране компьютера. При построении чертежей в СДГ GeoGebra можно использовать:

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

2. обладает большим количеством встроенных команд по различным разделам математики (Алгебра (НОД, НОК, упростить и т.д.), Геометрия (Локус, Ломанная, Луч и т.д.), Вероятность (СлучайноеЧисло, НормальноеРаспределение и т.д.) и т.д.);

3. возможности оформления (легко менять цвет и стиль линии, цвет и интенсивность заливки многоугольников и т.д.);

4. организацию анимации;

5. возможность Web-экспорта.

Система динамической геометрии GeoGebra может оказать огромную помощь при создании учебно-методических материалов: от создания качественных рисунков, графиков, схем для вставки в печатные тексты, до разработки интерактивных моделей-иллюстраций к объяснению теории и моделей-заданий.

При помощи цифровых образовательных ресурсов (ЦОР), созданных в СДГ GeoGebra [http://www.geogebra.org/cms/ru/], происходит внедрение системы в учебный процесс как школы (Алферов М.Ю.[1], Алышова Н.С. [2], Безумова О.Л., Котова С.Н., Шабанова М.В.[2] и др.), так и высших учебных заведений (Зиатдинов Р.А.[3], Пикалова В.В.[5]  и др.). Однако систему GeoGebra можно использовать не только в преподавании аналитической, дифференциальной и проективной геометрии, но и других дисциплин, например, дискретной математики, в частности, при обученииосновам теории графов.

Теория графов обладает важной прикладной особенностью для многих предметных областей:

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

2. экономике (теория игр,задача коммивояжёра, логистика и др.);

3. вычислительной технике (электрические схемы, сети и др.);

4. автоматизированном проектирование (критический путь, дерево решений и т.д.) и других науках.

Поэтому изучение теории графов, которая в дальнейшем используется при решении профессиональных задач, актуально и необходимо студентам, обучающихся в вузе по специальностям: 010400 «Прикладная математика и информатика» и 080500 «Бизнес-информатика». Раздел «Основы теории графов» предусматривается учебными планами данных специальностей в курсе Дискретная математика на первом курсе.

Рассматриваемое содержание обучения по теории графов является стандартным для перечисленных выше специальностей, однако наиболее подробно оно представлено в ФГОС-3 специальности 080500 «Бизнес-информатика» в разделе Б2.Б.2 «Дискретная математика». Приведем его содержание, кратко перечислив базовые понятия, теоремы и алгоритмы:

Понятие графа. Псевдографы, мультирафы. Ориентированные и неориентированныеграфы. Подграфы. Способы представления графов. Матрицы смежности и инциндентности. Маршруты, цепи, пути, циклы в графах. Основные типы графов. Операции над графами. Изоморфизм и гомеоморфизм графов. Метрические характеристики графов. Определение центра, радиуса, диаметра, медианыграфа. Достижимость и связность в графах. Алгоритмы определения компонент связности неорграфов и сильных компонент орграфов. Деревья. Понятие остова графа. Методы обхода графа (поиск в глубину и в ширину) иих использование для построения остовов. Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа. Циклы и разрезы в графе. Цикломатическое и коцикломатическое числа графа. Построение матриц фундаментальных циклов и разрезов графа. Обходы графа. Эйлеровы графы, цепи, циклы. Теорема Эйлера. Метод Флери построения эйлерова цикла в графе. Гамильтоновы цепи, пути, циклы в графе. Некоторые прикладные задачи теории графов. Использование алгоритмов теории графов в автоматизированном проектировании.

Создание интерактивных диаграмм графов (полный граф, простая цепь, двудольные графы и т.д.), орграфов, мультиграфов, мультиорграфов, псевдографов и псевдоорграфов в системе динамической геометрии GeoGebra поможет студентам освоить и закрепить базовые понятия теории графов.Так, например, при обучении теме «Изоморфные графы» выполнение задания «Каледоскоп» (создание анимированных диаграмм графов в системе GeoGebra таким образом, что вершины симметрично меняют свое положение, в результате получается динамически меняющиеся изображения диаграмм исходного графа, напоминающие калейдоскоп) может повысить интерес у студентов к изучению теории графов.

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

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

Система динамической геометрии GeoGebra обладает встроенными командами (МинимальноеОстовноеДерево и Коммивояжер), которые находятся в списке команд в разделе «Дискретная математика». С их помощью можно решать ряд задач практического содержания, создавая интерактивные графовые модели в СДГ GeoGebra. Например, можно решить следующую задачу наотыскание самого выгодного гамильтонового маршрута (задача коммивояжёра).

Необходимо составить наиболее эффективный маршрут для катера, который должен развести грузы по островам и вернуться обратно в порт. Координатыостровов следующие: А(-2; 12), B(-2,12; 4,56), C(6,57; -2,34), D(2,23; 5,54), F(11,4; 13,09), G(20,98; -10,95), PS(0;0). Последняя координата - порт. Вычислите, используя встроенные функции ИГС GeoGebra, примерную (с точностью до тысячных) наименьшую длину маршрута катера.

Решение задачи:

 1.Построение вершин (островов). В СДГ GeoGebraизобразим точками острова. С помощью строки ввода (Вид\Строка ввода) построим точки: в круглых скобках вводим координаты точек, целая часть отделяется точкой, координаты отделяются запятой. Для наглядности лучше включить сетку и оси.

2.Нахождение циклического маршрута. Для нахождения маршрута между данными вершинами воспользуемся встроенная команда системы GeoGebraраздел Дискретная математика\Коммивояжёр. В строке ввода пишем Коммивояжёр[Список вершин через запятую]. Соединяем отрезками полученный маршрут, в строке ввода находим сумму длин отрезков. Установим необходимую нам точность: в пункте меню Настройки/ Округление выберем необходимое число разрядов. В результате маршрут катера будет иметь длину 86,624 км.

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

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


 

Список использованных источников
  1. 1. Алферов М.Ю. Дидактические возможности и особенности свободной программы динамической геометрииGeoGebra.// Материалы XXIV Международной конференции «Применение инновационных технологий в образовании», 26 – 27 июня 2013г. г. Москва, г.Троицк, С. 448-451
  2. 2. Алышова Н.С. Использование программыGEOGEBRA на уроках как средство подготовки учащихся к ЕГЭ.//Альманах современной науки и образования, 2013. - № 1. С. 19-21.
  3. Безумова О.Л., Котова С.Н., Шабанова М.В. Компьютерная поддержка решения школьных алгебраических задач GEOGEBRA.//Образовательные технологии и общество, 2013, Т.16. - № 1. С. 564-574.
  4. 4. Зиатдинов Р.А. Геометрическое моделирование и решение задач проективной геометрии в системе GeoGebra.//Материалы конференции «Молодежь и современные информационные технологии», Томский политехнический университет, г. Томск, 2010. - C.168-170.
  5. 5. Пикалова В.В. Сотрудничество с Международным институтом GeoGebra как инструмент совершенствования математической подготовки будущего учителя//Образовательные технологии и общество, 2013, Т.16.- № 1. С. 564-574
  6. 6. Харари Ф. Теория графов. М.: Едиториал УРСС, 2003.  296 с.
Вид представления доклада  Публикация
Уровень  Высшее профессиональное образование
Ключевые слова  Теория графов, система динамической геометрии GeoGebra

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

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

В статусе «Рекомендован к публикации» тезис публикуется на сайте. Статус «Черновик» может быть возвращен либо по запросу участника, либо при неоплате публикации, если она предусмотрена, либо если тезисы превышают требуемый объем.

Статус «Опубликован» означает, что издана бумажная версия тезиса и тезис изменить нельзя. В некоторых крайне редких ситуацих участник может договориться с Оргкомитетом о переводе тезисов в статус «Черновик».

Статус «Отклонен» означает, что по ряду причин, которые указаны в комментариях к тезису, Оргкомитет не может принять тезисы к публикации. Из отклоненных тезис в «Черновики» может вернуть только Председатель программного или председатель оргкомитета.