Возможности реализации графовых задач в пакете mathematica

ВОЗМОЖНОСТИ РЕАЛИЗАЦИИ ГРАФОВЫХ ЗАДАЧ В ПАКЕТЕ MATHEMATICA

«Допущена к защите» Руководитель:____________________ (подпись) «___»___________________ 2017 г.	Работу выполнила: студентка 131 группы математического факультета направления подготовки 44.03.05 Педагогическое образование, профили «Математика» и «Информатика» Черепанова Александра Владимировна ________________________________ (подпись)
Дата защиты: «___»_________2017 г. Оценка: _________________________ Руководитель:____________________ (подпись)	Руководитель: канд. пед. наук, доцент Шеремет Галина Геннадьевна

ПЕРМЬ

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ. 3

ГЛАВА 1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.. 5

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ.. 7

ГЛАВА 4. ЗАДАЧИ ПО ТЕОРИИ ГРАФОВ.. 13

ГЛАВА 5. РЕАЛИЗАЦИЯ ГРАФОВЫХ ЗАДАЧ В ПАКЕТЕ MATHEMATICA.. 18

ЗАКЛЮЧЕНИЕ. 22

СПИСОК ЛИТЕРАТУРЫ.. 23

ВВЕДЕНИЕ

Универсальные математические пакеты предоставляют новые широкие возможности для совершенствования образования на всех, без исключения, его этапах от целенаправленного обучения до комплексной подготовки обучаемого к профессиональной деятельности и самореализации. Велика роль пакетов прикладных программ, в том числе, при изучении математики. Облегчая решение сложных задач, они снимают психологический барьер в изучении математики и делают этот процесс интересным и более простым. При грамотном применении их в учебном процессе пакеты обеспечивают повышение уровня фундаментальности математического образования. Математические программы дают возможность реализовать стандартными средствами важнейшие с дидактической точки зрения принципы "Максимальная наглядность и удобство работы" и"От простого к сложному". Эти принципы развивают и формируют у учащихся навыки самостоятельной познавательной деятельности, необходимые при дальнейшем обучении в ВУЗе.При выборе того или иного программного средства для использования его в своей работе преподаватель неизбежно встаёт перед необходимостью предпочтения того или иного из них. Особое место среди систем компьютерной математики занимает "Mathematica"- признанный мировой лидер в области программного обеспечения математических исследований за совершенство технологии.Цель работы состоит в изучении возможности применения пакета Mathematica при обучении теории графов в средней школеДля достижения поставленной цели необходимо решить следующие задачи:1) представить основные положения теории графов;2) проанализировать функции и возможности пакет Mathematica;3) подбор задач по графам, составление алгоритма их решения в пакете WolframMathematica.Объект исследования:обучение математике в средней школе.Предмет исследования:обучение теории графов средствами математических пакетов (пакет Mathematica).

Курсовая работа состоит из: введения, двух глав, заключения, списка литературы, насчитывающего 15 наименований.

Курсовая работа включает 24 страницы и 17 иллюстраций.

Во введении описывается актуальность исследования, цель, задачи, объект и предмет исследования.

Первая глава содержит информацию об истории возникновенияграфов.

Вторая глава содержит информацию об основных понятиях теории графов.

В заключении содержатся результаты и выводы исследования.

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

Определение 1. Графом G называется пара (V,E), где V={v₁,…,v_n} – непустое множество вершин графа, E = {e₁,e₂,…,e_m} – множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Обычно граф изображают на плоскости в виде точек (они соответствуют вершинам графа) и непрерывных линий, соединяющих некоторые из этих точек (они обозначают ребра графа). Пусть ребро е соединяет вершины u и v. В этом случае пишут e = [u,v] и говорят, что

1) u и v являются концами ребра е;

2) вершины u и v смежны;

3) вершины u и v инцидентны ребру е, ребро е инцидентно вершинам u и v. рис. 4

Определение 2. Степенью вершины называется количество инцидентных ей ребер.

Определение 3. Вершина называется изолированной, если она не инцидентна ни одному ребру; вершина называется концевой, если ей инцидентно только одно ребро.(рис.4)

Степень вершины v обозначается через deg(v). В графе (рис.4) вершина – изолированная, так как deg(v₁) = 0; вершина v₂смежна с вершинами v₃ и v₄ и инцидентна ребрам [v₂, v₃] и [v₂, v₄], следовательно, deg(v₂) = 2; вершина v₃смежна с вершинами v₂ и v₄и инцидентна ребрам [v₂, v₃] и [v₃, v₄], поэтому, deg(v₃) = 2;вершина v₄]смежна с вершинами v₂, v₃ и v₅ , инцидентна ребрам [v₂, v₄], [v₃, v₄] и [v₄, v₅], следовательно, deg(v₅) = 3; вершинаv₅– концевая, поскольку deg(v₅) = 1; она смежна только с вершиной v₄ и инцидентна только ребру [v₄, v₅].

Утверждение 1. Если в графе количество вершин n≥2, то в нем найдутся хотя бы две вершины с одинаковой степенью.

Докажем это утверждение от противного. Пусть все вершины графа имеют разные степени. Для удобства будем считать, что deg(v₁) = 0, deg(v₂) = 1,…, deg(v_n) = n – 1. Но согласно последнему равенству вершина v_nсмежна со всеми вершинами графа, в том числе и с вершиной v₁, а равенство deg(v₁) = 0 означает, что v₁– изолированная вершина. Получили противоречие. Следовательно, в любом графе с количеством вершин n≥2 обязательно найдутся две или более вершины с одинаковой степенью.

Кроме наглядного изображения на плоскости, граф можно задать с помощью списков смежности, матрицы смежности и матрицы инциденций. В списках смежности для каждой вершины графа указываются все вершины, смежные с ней. Этого достаточно, чтобы однозначно определить исходный граф. Матрицы смежности и инциденций тоже однозначно определяют граф. Но для задания графа матрицей смежности (инциденций) необходимо пронумеровать его вершины (и ребра).

Определение 4. Эксцентриситетомвершины u называется число Ɛ(u) равное максимальному расстоянию от вершины u до остальных вершин графа, т.е.

Ɛ(u) = maxp(u,v), v∈V

Определение 5. Радиусомграфа G называется число r(G), равное минимальному эксцентриситету его вершин, т.е.

r(G) = minƐ(v), v∈V

Орпеделение 6. Диаметромграфа G называется число d(G), равное максимальному эксцентриситету его вершин, т.е.

d(G) = maxƐ(v), v∈V

Известно, что для любого графа G выполняется соотношение

r(G) ≤ d(G) ≤ 2* r(G)

Орпеделение 7. Центромграфа G называется множество его вершин, имеющих минимальный эксцентриситет.

Пример. Рассмотрим граф G, изображенный на рис.. Эксцентриситеты его вершин:

Ɛ(v₁) = 4, Ɛ(v₂) = 3, Ɛ(v₃) = 4, Ɛ(v₄) = 3, Ɛ(v₅) = 2, Ɛ(v₆) = 3.

Следовательно, его радиус и диаметр r(G) = 2, d(G) = 4, а центр – вершина v₅ .

рис. 5

ЗАКЛЮЧЕНИЕ

В ходе работы были изучены такие понятия как граф, степень вершины, вершина, эксцентриситет вершины, радиус графа, диаметр графа, центр графа. Проанализированы функции и возможности пакета Mathematica такие как Graph, EdgeWeight, VertexLabels, EdgeLabels, VertexStyle, EdgeStyle, WeighteAdjacencyMatrix, FindSpanningTree, HighlightGraph. Подобраны две задачи на взвешанные графы и составлен алгоритм их решения в пакете Mathematica.

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

Mathematica интуитивно понятен, легко осваивается на практике и не требует для изучения и применения чтения толстых книг, ведения конспектов и заучивания сложных правил.

Mathematica соответствует психологии школьника в том смысле, что решение интересующей проблемы можно получить в течение короткого периода времени, а не тренировать у компьютера усидчивость.

СПИСОК ЛИТЕРАТУРЫ

1. Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика: Учебное пособие. – Ростов на Дону: «Феникс», Харьков: «Торсинг», 2009. – 144 с.

2. Балюкевич Э.Л. Дискретная математика [Электронный ресурс]: учебное пособие/ Балюкевич Э.Л., Ковалева Л.Ф., Романников А.Н. – Электрон. текстовые данные. – М. : Евразийский открытый институт, 2009. – 173 c. – Режим доступа: http://www.iprbookshop.ru/10661. – ЭБС «IPRbooks» (дата обращения: 23.04.2017)

3. Годунова Е.К. Введение в теорию графов. Индивидуальные задания [Электронный ресурс]/ Годунова Е.К. – Электрон. текстовые данные. – М. : Прометей, 2012. – 44 c. – Режим доступа: http://www.iprbookshop.ru/23979. – ЭБС «IPRbooks» (дата обращения: 12.05.2017)

4. Журбенко И.Г. О материалах для факультативных занятий // Математика в школе. – 2009. - №2. – с.53.

5. Мельников О.И. Графы в обучении математике // Математика в школе. – 2003. – №8.

6. Мельников О.И. Занимательные задачи по теории графов. Учебно –методическое пособие. – НТООО «ТетраСистемс». – 2001.

7. Мельников О.И. Теория графов в занимательных задачах. Изд.3–е, испр. и доп. – М. : Книжный Дом «ЛИБРОКОМ», 2009.

8. Морозенко В.В. Дискретная математика: учеб.пособие / Перм. ун–т. – Пермь, 2006.

9. Поспелов А. Д., Алексеев В. Б. Дискретная математика. Лекции. МГУ. – 2002. – 44 с.

10. Проблема семи мостов кёнигсберга. – Режим доступа: https://ru.wikipedia.org/wiki/Задача_о_семи_кёнигсбергских_мостах (дата обращения: 16.03.2017)

11. Судоплатов С.В., Овчинниова Е.В. Элементы дискретной математики: Учебник. – М. : ИНФРА-М, Новосибирск. Изд–во НГТУ, 2002.

12. Судоплатов. С. В. Дискретная математика : учебник и практикум для академического бакалавриата / Судоплатов С.В, Овчинникова Е.В. – 5–е изд., испр. и доп. – М. : Издательство Юрайт, 2017. – 279 с. – (Университеты России). – ISBN 978-5-534-00871-5.

13. Теория графов. – Режим доступа: https://ru.wikipedia.org/wiki/Теория_графов (дата обращения: 11.04.2017)

14. Храмова Т.В. Дискретная математика. Элементы теории графов [Электронный ресурс]: учебное пособие/ Храмова Т.В. – Электрон. текстовые данные. – Новосибирск: Сибирский государственный университет телекоммуникаций и информатики, 2014. – 43 c. – Режим доступа: http://www.iprbookshop.ru/45466. –ЭБС «IPRbooks» (дата обращения: 23.05.2017)

15. Хусаинов А.А. Дискретная математика [Электронный ресурс]: учебное пособие/ Хусаинов А.А. – Электрон. текстовые данные. – Комсомольск-на-Амуре: Амурский гуманитарно-педагогический государственный университет, 2010. – 77 c. – Режим доступа: http://www.iprbookshop.ru/22304. –ЭБС «IPRbooks» (дата обращения: 17.04.2017)

ВОЗМОЖНОСТИ РЕАЛИЗАЦИИ ГРАФОВЫХ ЗАДАЧ В ПАКЕТЕ MATHEMATICA

«Допущена к защите» Руководитель:____________________ (подпись) «___»___________________ 2017 г.	Работу выполнила: студентка 131 группы математического факультета направления подготовки 44.03.05 Педагогическое образование, профили «Математика» и «Информатика» Черепанова Александра Владимировна ________________________________ (подпись)
Дата защиты: «___»_________2017 г. Оценка: _________________________ Руководитель:____________________ (подпись)	Руководитель: канд. пед. наук, доцент Шеремет Галина Геннадьевна