Решение задач на тему: Теоретическая часть. Основные понятия теории графов. Маршруты и связность

Введение

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем.

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

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

Оглавление

- Введение 3

- Теоретическая часть

- Основные понятия теории графов

- Маршруты и связность

- Задача о кёнигсбергских мостах

- Эйлеровы графы

- Оценка числа эйлеровых графов

- Алгоритм построения эйлеровой цепи в данном эйлеровом графе

- Практическая часть

- Заключение 24

- Литература 25

Заключение

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

Известно, что эйлеровы графы получили широкое распространение и популярность благодаря тому, что многие головоломки и задачи можно решить с использованием знаний теории графов. Частные примеры таких головоломок и сюжетных задач были приведены в практической части. Задачи на отыскание путей через лабиринты, близкие к задачам на эйлеровы графы, находят применение в современной психологии и при конструировании вычислительных машин. Также с практической точки зрения, сейчас графы применяют во многих других областях науки таких как: программирование, физика, химия, биология, экономика и т.д.

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

1. Андерсон, Джеймс А. Дискретная математика и комбинаторика: пер. с англ. - М.: Издательский дом "Вильямс", 2003. - 960с.

2. Березина Л. Ю. Графы и их применение. - М.: Просвещение, 1979.

3. Новиков С.А. Дискретная математика для программистов - СПб.: Питер, 2001. - 304с.

4. Оре о. Графы и их применение. - М.: Мир,1973.

5. Уилсон Р. Введение в теорию графов. - М.: Мир, 1977.

6. Харари Ф. Теория графов. - М.: Мир, 1973.