2. Ориентированный граф

Граф называется ориентированным или орграфом, если некоторые ребра имеют направление (рисунок 3). Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет.

Рисунок 3 – Ориентированный граф

3. Неориентированный граф

В неориентированном графе отношения симметричны, то есть (u, v) = (v, u). В неориентированном графе нет дуг, связи называют ребрами.

Рисунок 4 - Неориентированный граф

1.4 Смежность

Пусть D1, D2- вершины, е = (D1, D2) - соединяющее их ребро (рисунок 5). Тогда вершина D1 и ребро е инцидентны, вершина D2 и ребро е также инцидентны.

Рисунок 5 – Смежные вершины

Две вершины называются смежными, если они соединены ребром/дугой (рисунок 5).

Два ребра называются смежными, если они соединены вершиной/узлом (рисунок 6).

Рисунок 6 – Смежные ребра

Смежные вершины - две вершины, инцидентные одному ребру.

Смежные ребра – два ребра, инцидентные одной вершине.

Множество вершин, смежных с вершиной V, называется множеством смежности вершины V и обозначается Г+(V) (рисунок 7).

Рисунок 7 - Множество смежности

1.5 Маршруты и пути

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

Маршрут в графе – чередующаяся последовательность вершин и ребер.

Эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним (рисунок 8).

Рисунок 8 Граф для иллюстрации маршрутов

Указанный маршрут соединяет вершины D_o и D_n, и его можно обозначить D_o,D₁,D₂,...,D_n (наличие ребер подразумевается). Эта последовательность иногда называется (D_o-D_n) - маршрутом. Маршрут замкнут, если D = D_n, и открыт в противном случае.

Цепь – маршрут с различными ребрами.

Простая цепь-маршрут с различными вершинами (а значит, и ребрами).

Цикл- замкнутая цепь.

В помеченном графе J на рисунке 8 D₁ D₂ D₃ D₄ - маршрут, который не является цепью, а D₁ D₂ D₄ D₃ D₂ - цепь, где D₁ D₂ D₄ D₃ - простая цепь и D₂ D₄ D₃ D₂ - простой цикл. 

Обозначим через J_n граф состоящий из одного простого цикла с n вершинами, и через P_n простую цепь с n вершинами. J_n часто называют треугольником. 

2. Постановка задачи коммивояжера и алгоритмы решения

2.1 Задача коммивояжера

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

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

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

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

Особенностью задачи о коммивояжере является необходимость дополнительно учитывать расстояния от города до города, которые предполагаются известными. Эти «расстояния» можно заменить на количество затраченного времени, стоимость проезда или предполагать другие произвольные значения. В общем случае мы даже не предполагаем, что стоимость проезда из I в J обязательно совпадает со стоимостью обратного проезда из I в J. Данная задача соединяет в себе простоту условия и сложность решения, обусловленную большими размерами поискового пространства. 

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