Глава 5. Реализация графовых задач в пакете Mathematica

Задача 1. На строительном участке нужно создать телефонную сеть, соединяющую все бытовки. Для того, чтобы телефонные линии не мешали строительству, их решили проводить вдоль дорог. Схема участка изображена на рис.10, где бытовкам соответствуют вершины графа и указаны длины дорог между ними.

рис10.

 

рис11.

рис12.

рис13.

рис14.

Задача 2. Почтальон должен разнести почту по всем улицам своего участка. На схеме указаны расстояния между перекрёстками. Буквой П обозначается почта (рис.3). Найдите кратчайший маршрут почтальона.

рис15.

рис16.

рис17.

ЗАКЛЮЧЕНИЕ

В ходе работы были изучены такие понятия как граф, степень вершины, вершина, эксцентриситет вершины, радиус графа, диаметр графа, центр графа. Проанализированы функции и возможности пакета 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)