Курсовая с практикой на тему Графы и их применения

Содержание:

Введение  3

Исходные данные. 4

1.
Определение графа. Операции над графами  5

2.
Матричное представление графов. Базовые и доминирующие множества  8

3.
Гамильтонов и эйлеров путь  13

4.
Определение связности графа. 25

5.
Описательные примеры   28

Выводы   29

Список литературы   30

Введение:

Первое
упоминание теории графов относится к 1736 г., когда Леонард Эйлер опубликовал
решение так называемой задачи про кенигсбегрские мосты, а также сформулировал
критерий существования эйлерова цикла в графе. Однако проведение активных
научных изысканий и развитие теории графов, как современного отдельного раздела
математики, началось в XX-м
веке. Именно с этого времени графы становятся одной из самых распространенных и
популярных форм математических моделей в различных областях науки и техники. В значительной
степени это было связано с возникновением электронных вычислительных машин и,
как следствие, появлением значительного числа задач дискретного характера.
Математика переходит от «обслуживания» преимущественно физики к распространению
своих методов в другие сферы человеческой деятельности, связанные с
искусственным интеллектом и коммуникациями.

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

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

Заключение:

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

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

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

Фрагмент текста работы: