Эйлеровы графы в прикладных задачах

Введение

Теория графов - динамично развивающийся раздел математики. Большое количество окружающих нас объектов и их взаимоотношений могут быть описаны с помощью этой теории. Графы применяются там, где между данными существуют различные нелинейные связи. Например, это могут быть компьютеры, соединённые в сеть. Или это могут быть задачи, которые надо выполнить в каком-то порядке, причём некоторые задачи надо выполнять строго после каких-то других. Существуют алгоритмы, позволяющие вычислить оптимальный порядок выполнения таких задач.
В практическом плане растущее использование алгоритмов работы с графами дает неоспоримые научные и экономические выгоды и определяет необходимость их подробного изучения. Это определяет актуальность настоящей работы.
Цель курсовой работы - выяснить особенности применения эйлеровых графов в различных областях человеческой деятельности при решении прикладных задач.
В результате выполнения настоящей работы должны быть выполнены следующие задачи:
1) изучить основные понятия теории графов и основные характеристики эйлеровых графов;
2) ознакомиться с практическим использованием теории графов в прикладных задачах различных областей знаний;
3) рассмотреть способы решения задач с использованием эйлеровых графов на персональном компьютере.
Объектом исследования настоящей работы является прикладная деятельность человека, связанная с применением эйлеровских графов.
Предметом исследования является теория графов.
Гипотеза: мы предполагаем, что изучение теории графов может помочь разработать эффективные средства для повышения эффективности решения прикладных задач в различных областях деятельности человека.
В ходе нашего исследования были использованы такие методы, как:
 Работа с различными источниками информации.
 Описание, сбор, систематизация материала.
 Наблюдение, анализ и сравнение.
 Разработка программного обеспечения.
Новизна работы заключается в авторской разработке компьютерной программы по теме исследования.
Практическая значимость этой курсовой работы определяется тем, что ее результаты могут быть использованы для дальнейших разработок по текущей тематике.

Глава 1. Общие сведения по теории графов
1.1 История возникновения теории графов

Леонарда Эйлера считают основателем теории графов. Началось все в 1736 году, когда Л.Эйлер в одном из своих писем итальянскому математику и инженеру Мариони сформулировал и предложил решение задачи о семи кёнигсбергских мостах. Эта задача, впоследствии, стала одной из классических задач теории графов.
Среди жителей Кёнигсберга в те поры была распространена байка о том, что можно пройти по всем городским мостам, не проходя ни по одному из них дважды. Дело доходило до заключений крупных пари. Многие кёнигсбержцы пытались решить эту задачу, кто теоретически, кто чисто практически, но никому это не удавалось. Хуже того - не удавалось доказать, что это невозможно. Кипели страсти. До тех пор, пока в 1736 году задача о семи мостах не заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера. Эйлер смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Для справки - в случае семи мостов Кёнигсберга это невозможно.
Для решения этой задачи Эйлер каждый пункт маршрута (остров или берег реки) обозначил кружком на бумаге, а потом соединил линиями те кружки, между которыми существуют мосты. Его действия доказали, что в этой задаче фактическое расположение, форма, длина и другие свойства объектов не представляют интереса, важны только связи между ними. Таким образом был получен первый граф. Кружки – вершины графа, линии – рёбра графа. Размышляя над полученной схемой, Эйлер пришел к следующим выводам:
1 Число нечётных вершин графа должно всегда быть чётное число. Нечетными вершинами он назвал те, к которым ведёт нечётное число рёбер. То есть, не может существовать графа, который имел бы нечётное число нечётных вершин.
2 Если все вершины графа чётные, то его можно нарисовать, не отрывая карандаша от бумаги, при этом начинать можно с любой вершины графа и завершить его в ней же. При этом граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Все вершины графа кёнигсбергских мостов были нечётные. Из этого следовало, что невозможно пройти по всем мостам, не проходя ни по одному из них дважды. Постановка задачи изображена на рисунке 1,