Теория графов – это раздел дискретной математики, который изучает характеристики графов. Она имеет очень широкое практическое применение. Зачастую, задачи, которые возникают в экономике, химии, электротехнике, планировании транспортных перевозок, управлении предприятием, торговле и образовании, можно сформулировать как задачу теории графов.
Теория графов также находит свое приложение, к примеру, в геоинформационных системах (ГИС). Дома, которые уже существуют и те, что вновь проектируются, здания, улицы и тому подобное, рассматривают как вершины, а дороги, которые их соединяют, инженерные сети, провода электропередачи и тому подобное – как рёбра. Использование разнообразных расчетов, которые производят на таких графах, дает возможность поиска кратчайшего объездного пути или ближайшего продуктового магазина, составить план оптимального маршрута.
Граф (в широком смысле) – это множество узлов или вершин, которые соединены рёбрами. Граф состоит из двух компонентов: вершин и дуг, которые соединяют между собой данные вершины.
При представлении графов зачастуюприменяется такая совокупность обозначений:
– всякой вершине соотносится точка на плоскости,
– если между вершинами имеется ребро, то такие точки соединяют отрезком или стрелкой.
Для графа, которыйизображен на рис. 1:
– кружочки A, B, C, D, E – вершины графа;
– линии a, b, c, d, e, f, g – дуги.
Рис. 1. Составные части графа
Алгоритмы, которые предназначены для выполнения задачи оптимизации, как правило, представляют собой последовательность шагов, и на каждом из них имеется множество выборов. Так называемый «жадный» алгоритмпозволяет сделать выбор, который кажется наилучшимв данное время. То есть проводится локально оптимальный выбор, считая, что это приведет к оптимальному решению глобальных задач. Жадный алгоритм во многих задачах приводит к нужному результату, хотя и не всегда приводят к оптимальному решению. Жадные алгоритмы обладают необходимой мощностью, и подходят для решения довольно-таки большого круга задач.
К жадным методам относят алгоритм,построенный на графах, изобретенный нидерландским ученым Эдсгером Дейкстрой в1959 году. Алгоритм Дейкстры – это алгоритм, применяемый для поискасамого кратчайшего пути от одних вершин графа до других. Алгоритм можно использовать только для тех графов, чьи ребра не имеют отрицательного веса.
Фирме, осуществляющей перевозку скоропортящегося товара, дано задание на доставку товара из Ставрополя в Будённовск, при этом существует несколько путей, по которым возможно доставить товар. Расстояние между городом Ставрополь и селом К. – 26 километров, между г. Ставрополем и селом П. – 19 километров, междуг. Ставрополем и селом Р. – 86 километров. Между сёлами К. и Д. – 16 километров, между сёлами К. и Л. – 66 километров. Между селом П. и городом Н. составляет 4 километра, между сёлами П. и В. – 51 километр. Между сёлами Д. и В. – 21 километр. Между городом Н. и селом М. – 21 километр. Между сёламиМ. и Л. – 24 километра, между сёлами М. и В. – 34 километра. Между сёламиЛ. и А. – 13 километров, между сёлами Л. и Ж. – 43 километра. Между сёлами А. и Б. – 25 километров. Между сёлами Ж. и Р. – 31 километр, между сёлами Ж. и Б. – 44 километра. Между сёламиБ. и Р. – 22 километра. Между сёлами В. иЖ. – 9 километров. Необходимо найти самый короткий путь из Ставрополя в Буденновск.
Построим граф G, где город Ставрополь обозначим буквой C, Буденновск – Б. Оставшиеся пункты маршрута обозначим соответственно буквами Л, П, Р, Д, Л, Н, М, В, А, Ж, Б. Каждому ребру графа сопоставим числа, которые будут равны расстоянию между пунктами. Необходимо найти наикратчайшийпуть.
Метод Дейкстры позволяет найти наикратчайший маршрут между необходимыми вершинами в графе. Значит, можно использовать данный алгоритм, для решения данной экономической задачи.
Рис. 2. Графическое изображение задачи
Применим формулу метода Дейкстры для решения данной экономической задачи:
, (1)
где D(v) – длина кратчайшего пути от начальной вершины к конечной вершине; величины u, v – неотрицательный вес ребра.
С помощью алгоритма Дейкстры можно найти единственный оптимальный маршрут, который соединяет вершины С и Б графа (см. рис.1).
Пусть вершина С будет являться начальной вершиной. Для этой вершины назначим постоянный ярлык 
. За конечную вершину примем Б.
Рассмотрим вершины, которые являются смежными с вершиной Б.
Для этого назначаем им временные ярлыки:
Y(К)=26, Y(П)=19, Y(Р)=86.
Необходимо выбрать вершину с наименьшим ярлыком – это вершина П, и её ярлык считают постоянным, то есть Y(П)=19.
При повторении этого процесса для вершины П, вершинам присваивают временные ярлыки: Y(Н)=4, Y(В)=51.
Выбирая из всех временных ярлыков, минимальным будет являться Y(Н)=4. Этот ярлык устанавливается постоянным.
С вершиной Н считается смежной только вершина М, тогда Y(М)=19.
При повторении этого процесса для вершины М, вершинам присваивают временные ярлыки: Y(Л)=24, Y(В)=34.
Среди них минимальным будет величина Y(Л)=24. Такой ярлык считают постоянным.
При повторении этого процесса рассматривают вершины, смежные с вершиной Л. Это К, А и Ж. Для них временными ярлыками будут: Y(К)=66, Y(А)=13, Y(Ж)=43. Находим наименьший временный ярлык. Таким является ярлык: Y(А)=13.
С вершиной А смежной является только вершина Б, тогда Y(Б)=25.
В то время, когда дерево составлено, становится возможным найти наикратчайший путь от С до Б. Им будет являться путь дерева, который соединяет вершины С и Б. Выявлено, что это путь, проходящий через вершины К, Н, М, Л и А. Длина такого пути рассчитывается как сумма всех дуг данных вершин (формула (2)).
км. (2)
Рис. 3. Нахождение решения экономической задачи
Таким образом, маршрут из города Ставрополь в город Буденновск, с наименьшим временем доставки товара, включает село П, город Н, село М, село Л и село А. Общая протяженность маршрута составляет 104 километра.