Введение 3
1 Основные понятия Теории Графов 4
1.1 Понятие графа 4
1.2 Степень вершины 6
1.3 Пути и циклы 6
1.4 Связность 8
1.5 Эйлеровы обходы 10
2 Поиск маршрутов на графе 12
2.1 Поиск в глубину. Задача обхода 12
2.2 Кратчайшие пути 13
2.3 Деревья и леса 17
3 Система компьютерной математики Wolfram Mathematica 22
3.1 Основные сведения о Wolfram Mathematica 22
3.2 Основные команды пакета Graph 23
3.3 Решение задач по поиску маршрутов на графе 25
4 Методика применения графов в школьном курсе 41
4.1 Роль элективных курсов в школьном обучении 41
4.2 Разработка элективного курса "Решение задач методом графов"для учащихся 9-ого класса 42
Заключение 77
Библиографический список 78
Современная эпоха стала свидетелем непрерывного развития теории графов, которая за последние десятилетие вступила в новый этап интенсивных разработок. В этом процессе отчетливо просматривается влияние запросов новых приложений: теории передачи сообщений, электрических сетей, теории игр и программирования.
Система Mathematica дает возможности по моделированию и визуализации графов, предоставляет удобный символьный механизм для создания, категоризации и оформления графов - от малого и схематического до большого и сложного. Все эти возможности являются полностью интегрированными с уникальной программируемостью, графикой и динамическим интерфейсом системы Mathematica.
Графы используют во всех отраслях нашей жизни. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты), построении путей транспортировки и доставки, решении задач.
Цель дипломной работы разработать элективный курс для учащихся 9-го класса по поиску маршрутов на графе с использованием пакета Wolfram Mathematica.
Задачи выпускной квалификационной работы:
1. Изучить теоретический материал по Теории графов;
2. Показать способы поиска кратчайшего и оптимального пути;
3. Исследовать среду Wolfram Mathematica;
4. Разработать элективный курс для учащихся 9-ого класса с использованием пакета GeoGebra.
Практическая значимость элективного курса заключается в том, что он может быть использован при подготовке к ОГЭ и ЕГЭ по информатике для учеников средних и старших классов.
Раздел теоретического изложения материала подкреплен примерами
Теория графов в настоящее время является интенсивно развивающимся разделом дискретной математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации: коммуникационные сети, схемы электрических и электронных приборов, химических молекул, отношение между людьми и многое другое.
Т.е. учащиеся, добыв первоначальные знания с помощью занимательных задач, переходят к закреплению и развитию этих знаний на базе решения более сложных задач.
Теория графов привлекательна еще и тем, что в ней наряду с решенными задачами и проблемами существуют задачи нерешенные. А это является малой долей изученного в данной теории и до сих пор остается мощным стимулом для дальнейших исследований различных свойств графов.
В ходе выполнения дипломной работы были:
1. Изучены теоретические материалы по Теории Графов.
2. Показаны способы поиска кратчайшего и оптимального пути.
3. Исследована среда Wolfram Mathematica.
4. Разработан элективный курс для учащихся 9-ого класса.
Таким образом, поставленная цель достигнута и задачи были выполнены.
