Теория графов. Задача коммивояжера

    Содержание

Введение                                                                   

I. Основные понятия                                               

1.Эйлеровы графы.                                                             

2. Кротчайшие пути.                                                         

3. Деревья.                                                                                        

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

1.Общие описание.                                                                  

2.Методы решения ЗК.                                                      

   а. Жадный алгоритм.                                                       

   б. Деревянный алгоритм.                                                 

   в. Метод ветвей и границ.                                               

III. Выводы.                                                                          

Литература.

                                             Введение.

ТЕОРИЯ ГРАФОВ - это область дискретной матема­тики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов-граф и его обобщения.

Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие). Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторе­ний, полученный Л. Эйлером при реше­нии задачи о Кенигсбергских мостах. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый  мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“.  Кенигсбергские мосты схематически можно изобразить так.

Существует еще один вид задач, связанных с путешествиями  вдоль графов. Речь идёт о задачах, в которых требуется отыскать путь, проходящий через все вершины, причем не более одного раза через каждую. Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии( в честь Уильяма Роуэна Гамильтона, знаменитого ирландского математика прошлого века, который первым начал изучать такие линии). К сожалению, пока еще не найден общий критерий, с помощью которого можно было бы решить, является ли данный граф гамильтоновым, и если да, то найти на нём все гамильтоновы линии. 

  Сформули­рованная в середине 19 в. проблема четырех красок  также выглядит как развле­кательная задача, однако попытки ее решения привели к появлению некоторых  исследований графов, имеющих теоретическое и прикладное значение. Проблема четырех красок формулируется так: ”Можно ли область любой плоской карты раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?”. Гипотеза о том, что ответ утвердительный, была сформулирована в середине 19в. В 1890 году было доказано более слабое утверждение, а именно, что любая плоская карта раскрашивается в пять цветов. Сопоставляя любой плоской карте двойственный ей плоский граф, получают эквивалентную формулировку задачи в терминах графов: Верно ли, что хроматическое число любого плоского графа меньше либо равно четырёх? Многочисленные попытки решения задачи оказали влияние на развитие ряда направлений теории графов. В 1976 году анонсировано положительное решение задачи с использованием ЭВМ.

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

1. Граф G(V,E) - комбинаторный объект, состоящий из двух конечных мно­жеств: V - называемого множеством вершин и множества пар элементов из V, т.е. Е  VxV, называемого множеством ребер, если пары неупорядочены, и множеством дуг, если пары упорядочены. В первом случае граф G(V,E) называется неориентированным, во втором ориентированным. Если е = (v1,v2).

eЕ, то говорят, что ребро е соединяет вершины v1,v2, если v1 = v2, то ребро е называет­ся петлей. Две вершины v1,v2 называются смежными, если существует соединяющее их ребро. Аналогично, два различных ребра смежны, если они имеют общую вершину.

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

Путь - это последовательность ребер e1, е2, ... , еm, такая, что ei, ei+1 имеют об­щую вершину. Число ребер называется длиной пути. Если ни одна из вершин не появля­ется более одного раза, то путь называется простым. Ясно, что в простом пути ни одно ребро не используется дважды.

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

В случае ориентированного графа, если путь проходит в направлении дуг, он называется ориентированным. Аналогично определяется ориентированный цикл.

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

3.    Двудольные графы. Это графы, у которых множество вершин можно

разбить на два множества V1, и V2 , и так что каждое ребро графа соединяет только некоторую
вершину из V1 с некоторой вершиной из V2.

4.    Граф единичного n-мерного куба Вn. Вершины графа - n-мерные двоичные наборы. Ребра соединяют вершины, отличающиеся одной координатой.

Факт 1. Любой граф содержит четное число вершин нечетной степени. ♦ Если граф G имеет xi вершин  степени i, то

X1+2x2+…+kxk=2E                                              (1)

поскольку мы подсчитываем число концевых вершин ребер, а каждое ребро имеет точно две концевые вершины. Отсюда получаем, что x1+ x3+ ... + x2s+1-  четное число.  Число ребер в графе существенно влияет на его связность. Заметим, что любой граф можно разбить на связные части - компоненты связности, задав следующее отношение эквивалентности на множестве его вершин: две вершины эквивалентны, если существу­ет путь из одной вершины в другую. Таким образом, связный граф состоит из одной компоненты.

Факт 2. Пусть G - граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам:

               Нижнюю оценку доказывают индукцией по числу ребер в G. Если множество
ребер пусто, то утверждение очевидно. Если в графе G число ребер минимально (скажем m0), удаление любого ребра приводит к увеличению числа компонент на единицу. Зна­чит, в графе k+1 компонента и m0 -1 ребро. По предположению индукции , m0-1n-(k+1)откуда m0 > n - к. Для доказательства верхней оценки считаем каждую компоненту графа G полным графом. Если Ci и Cj - две компоненты с ni и nj вершинами (ni > nj > 1), то заменяя их на полные графы с ni + 1 и nj -1 вершинами, мы, не меняя
числа вершин, увеличиваем число ребер. Действительно,

      Значит, максимальное число ребер имеет граф G , у которого k -1 изолированных вершин и компонента из полного графа на n - к + 1 вершинах. Отсюда и следует верхняя оценка.

Следствие. Любой граф с n вершинами, имеющий более, чем

                                                                                     ре­бер, связан.

                Действительно, если граф имеет k компонент, то по предыдущему, число его ребер не превышает

                Но неравенство:<

справедливо только при к = 1.

  Убедимся теперь в том, что степени вершин существенно влияют на наличие циклов в графе.

Факт 3. Если степень каждой вершины графа G(V,E) не меньше двух, то G содержит цикл.

   Пусть v - произвольная вершина из V. Строим последовательность ребер
(v,v1), (v1,v2), ..., выбирая v1 смежной с v, ... , Vi+1 - смежной с v1, и отличной от vi-1. По условию вершина Vi+1 существует. В силу конечности V на некотором шаге будет вы­брана вершина, уже встретившаяся раньше. Пусть это vk. Тогда часть последовательно­сти ребер между вхождениями vk образует цикл.

2. Пусть G - связный граф, u, v - произвольные вершины. Определим d(u, v) - расстояние между u и v как длину кратчайшего пути из u в v. При этом полагаем  d(u, v) = 0 при u = v.

Ясно, что введенное таким образом расстояние удовлетворяет аксиомам метри­ки:

1.            d(u,v)0

2.            d(u, v) = 0u = v

3.            d(u,v) = d(v,u)

4.            d(u, v)+d(v, w)  d(u, w) (неравенство треугольника)
Для связного графа G диаметр d(G) определяется как`           

d(G) = max d(u,v)

3. Графы G1(V1, E1) и G2(V2, E2) называются изоморфными, если существует биекция f: V1V2, такая, что выполнено

(v1, v2)E(f(v1), f(v2)E2

При этом f называется изоморфизмом графов G1 и G2. Изоморфизм графа G на себя называется автоморфизмом.

Пример 1. Следующие графы имеют только тождественные автоморфмы

Пример 2. Следующий граф имеет, кроме тождественного, автоморфизмы (1,3), (2,4), (13)(24).

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

4. Поскольку графы можно рассматривать как частные случаи бинарных отно­шений, то для них могут быть определены аналогичные операции. Укажем некоторые из них.

Пусть G1 + (V1, E1), G2 = (V2, E2) - два графа.

Объединение графов G1 и G2 есть граф, у которого V = V1  V2,

 Е = E1  Е2.

Соединение графов G1+G2 есть граф, у которого

V = V1  V2, Е = E1  Е2 {(v1, v2)} для всех v1V1, v2V2

Прямое произведение графов есть граф, у которого V = V1V2,

((c1,v2),(v1,v2))E(v1,v1)E и (v2,v2)E2

Пример. Пусть даны графы отображений f1 V1Vi, f2: V2V2. Тогда пря­
мое   произведение      соответствует      отображению
f1  f2: V  V2 V1  V2 где f1  f2(v1,v2) = (f1,(v1), f2(v2))

Пусть f1 и  f2  имеют    и    начальных вершин соответственно. Тогда f1  f2  будет

иметь

Некоторые классы графов допускают характеристическое описание. В качестве примера приведем критерий двудольности графа (Кёниг, 1936 г.)

Теорема. Для двудольности графа необходимо и достаточно, чтобы он не со­держал циклов нечетной длины.

Пусть G = (V, Е) - двудольный граф, С - один из его циклов длины k. Фикси­руем вершину v1 С  и проходим цикл, начиная с v1. Пусть это вершины v1, v2,..., vk. Поскольку концы каждого ребра лежат в разных долях, то k - четное число.

Пусть G = (V, Е) - связный и все его циклы четной длины. Определим разбиение V = V1V2 следующим образом: Фиксируем произвольную вершину v1V и включа­ем ее в V1. Теперь включаем uV1 d(u, v1) - четное число. Остальные вершины включаем в V2.

Покажем, что граф G двудольный. Пусть, напротив, существует ребро (v', v"), где v', v"  V1. Следовательно, d(v1, v'), d(v1, v") - четны. Ребро (v', v") дает цикл нечет­ной длины, содержащий путь от v1 к v', ребро (v', v"), путь от v" к v1. Аналогично пока­зываем, что нет ребер (v', v"), v', v"  V2.

1. Эйлеровы графы.

Эйлеровым путем графа G(V,E) называется путь e1,e2, ..., et такой, что каждое ребро появляется ровно 1 раз, т.е. t = | Е |. Граф G(V,E) называется эйлеровым, если он имеет замкнутый эйлеровый путь, и полуэйлеровым, если существует эйлеров путь, не являющийся замкнутым.

Теорема 1. Связный граф G является эйлеровым тогда и только тогда, когда ка­ждая вершина G имеет четную степень.

 Предположим, что Р является эйлеровым циклом в графе G. Тогда при всяком прохождении цикла через любую вершину графа используется одно ребро для входа и одно ребро для выхода. Поскольку каждое ребро используется один раз, то каждая вер­шина должна иметь четную степень. Обратное утверждение доказываем индукцией по числу ребер в графе G. Пусть граф G связен и степень каждой вершины четна. На осно­вании Факта 3 граф содержит цикл C. Если C содержит каждое ребро, то все доказано. Если же нет, то удаляем из графа G все ребра, принадлежащие циклу C. Получаем но­вый граф G1, возможно несвязный. Число ребер в G1 меньше чем в G, и каждая вершина имеет четную степень. По индуктивному предположению в каждой компоненте графа d имеется эйлеров цикл. В силу связности графа G каждая компонента графа G1 имеет общие вершины с циклом С. Теперь проходим, ребра графа G следующим образом: идем по ребрам цикла С до первой неизолированной вершины графа G1. Затем проходим эй­леров цикл в компоненте графа G1, затем снова двигаемся по циклу С до следующей неизолированной вершины графа G1. Ясно, что процесс заканчивается в исходной вер­шине, что и показывает существование эйлерова цикла.

Аналогичным образом доказывается

Теорема 2. Связный граф G является полуэйлеровым тогда и только тогда, когда в нем существует точно две вершины нечетной степени.  Аналогичное определение можно сделать для ориентированных графов. Ориентированный эйлеров путь это ориен­тированный путь, содержащий каждую дугу точно один раз. Ориентированный граф называется эйлеровым, если в нем существует ориентированный эйлеров путь.

Аналогично теореме 1 можно доказать следующее утверждение.

Теорема 3. Ориентированный граф G(V,E), у которого связан соответствующий скелетный граф, является Эйлеровым тогда и только тогда, когда либо для всех вершин v, di(v) = d0(v), либо существуют точно две вершины v1 и v2 такие, что d0(v1) = di(v1) + 1,

d0(v2) + 1 = di(v2), а для остальных вершин

dI(v) = d0(v).                                                                 (3)

В первом случае любой эйлеров путь является ориентированным циклом, во втором -

начинается в вершине v1 заканчивается в вершине v2

Теорема 4. Пусть G - связный граф, имеющий точно 2s > 0 вершин нечетной степени. Тогда существует s и не существует меньшего числа путей P1, ... , Ps, которые в совокупности содержат все ребра графа G точно по одному разу. При этом каждый из путей P1, ..., Ps начинается в одной нечетной вершине и кончается в другой.

Согласно факта 1 в графе G имеется четное число 2s вершин нечетной степе­ни. Разобьем эти вершины на s пар (v1, w1), ..., (vs, ws). Образуем теперь новый граф G1,= добавив каждой паре (vi, wi), i = 1,s ребро. Тогда G - связный граф, у которого все вер­шины четны. Согласно теореме 1 в графе G1 существует эйлеров цикл С, проходящий по всем ребрам точно по одному разу. Удалим из цикла С добавленные ребра и получим s путей P1, ..., Ps, проходящих каждое ребро точно один раз. Ясно, что каждый путь на­чинается и кончается в нечетной вершине. Пусть теперь имеется t путей t < s P1, ... , Pt, содержащих все ребра графа G. Тогда каждая нечетная вершина должна быть концом пути и, значит, имея 2s нечетных вершин, нельзя покрыть все ребра графа G менее, чем s путями.

Приведем теперь алгоритм построения эйлерового пути в данном эйлеровом графе.

Теорема 5. Пусть G - эйлеров граф. Тогда следующая процедура всегда возмож­на и приводит к построению эйлеровой цепи графа G.

Выходя из произвольной вершины, идем по ребрам графа произвольным обра­зом, соблюдая следующие правила:

1)    стираем ребра по мере их прохождения (вместе с изолированными вершина­ми, которые при этом образуются);

2) на каждом этапе идем по ребру, удаление которого нарушает связность, толь­ко в том случае, когда нет других возможностей.

Убедимся сначала, что указанная процедура может быть         выполнена на каж­дом этапе. Пусть мы достигли некоторой вершины v, начав с вершины u, v  u. Удалив ребра пути из v в u, видим,

что  оставшийся граф G1 связен и содержит ровно две нечет­ных вершины

v и u. Согласно теореме 2 граф G1 имеет эйлеров путь Р из v в и. Посколь­ку удаление первого ребра инцидентного u пути P либо не нарушает связности G1, либо происходит удаление вершины u и оставшийся граф G2 связен с двумя нечетными вер-

шинами, то отсюда получаем, что описанное выше построение всегда возможно на каж­дом шаге. (Если v = и, то доказательство не меняется, если имеются ребра, инцидентные u). Покажем, что данная процедура приводит к эйлерову пути. Действительно, в G не может быть ребер, оставшихся непройденными после использования последнего ребра, инцидентного u, поскольку в противном случае удаление ребра, смежному одному из оставшихся, привело бы к несвязному графу, что противоречит 2). ♦

В качестве одного из применений эйлеровых графов приведем следующее.

Пусть А = {0, 1, ..., m-1} - алфавит из m букв. Ясно, что имеется

mn ,различных слов длины n в алфавите А. Последовательностью де Брейна называется циклическое слово a0 a1…aL-1          в алфавите А, такое, что подпоследовательности      вида         ai ai+1…ai+n-1  i = 0, ..., L-1 состоят из всех возможных L = mn слов длины n. Наиболее важный случай для приложений m = 2. Последовательности де Брейна производятся полноцикловыми регистрами сдвига. Покажем существование последовательностей де Брейна.

Пример.

Определим ориентированный граф Gm,n(V,E) следующим образом

1) V является множеством всех mn-1 слов длины n-1 над A

2) Е является множеством всех mn слов длины n над A

3) дуга (a1, a2 … ,an) имеет начальной вершиной (a1, … ,an-1) и конечной (an, … ,an).

Приведем граф G2,3 :   

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

Пример. Для графа G2,3. имеем эйлеров путь

000, 001, 011, 111, 110, 101, 010, 100, а соответствующую   последовательность де Брейна

00011101

Теорема 6. Для любых целых m и n граф Gm,n имеет ориентирован-

ный эйлеров цикл.

            Покажем сначала, что граф Gm,n сильно связен, а значит его соответствующий скелетный граф связен. Действительно, пусть b1, ... , bn-1

 и c1, ..., cn-1  две вершины. То­гда их соединяет следующий ориентированный путь

(b1, b2, ..., bn-1, c1), (b2, ... , bn-1, c1, c2), ... , (bn-1, c1, ..., cn-1).

Далее dI(v) = d0(v) = m  для любой вершины v.

Действительно, из вершины v = (b1, b2, ..., bn-1) выходят дуги вида:

            (b1, b2, ..., bn-1)

и входят дуги вида (с, b1 ... , bn-1), с  А.

Теперь по теореме 3 в графе Gm,n существуют эйлеровы циклы.

Следствие. Для любых целых m, n последовательности де Брейна существуют.

Теорема 7. Для любых натуральных m, n существует точно

последовательностей де Брейна.

2. Кратчайшие пути.

Пусть G(V,E) - конечный неориентированный граф и пусть заданы две его вер­шины s и t. Требуется найти кратчайший путь (длина пути равна числу входящих в него ребер) от вершины s к вершине t. Сначала мы опишем алгоритм, который находит длину кратчайшего пути.

Алгоритм ДЛИНА

1) Помечаем вершину s пометкой 0. Полагаем i = 0.

2)Находим все непомеченные вершины, связанные ребром с

вершина­ми, имеющими отметку i. Если таких вершин нет, t недостижимо из s,. Ес­ли такие вершины есть, помечаем их i+1.

              3)Если вершина t помечена, переходим к 4). Если нет, то                                           увеличиваем I на 1 и повторяем шаг 2).

            4)Длина кратчайшего пути от s к t равна i+1, стоп.
Корректность алгоритма следует из следующего утверждения.

Факт 1. Вершина v графа G(V,E) помечается в алгоритме пометкой (v) тогда и только тогда, когда длина кратчайшего пути от вершины s к v равна (v).

♦ Доказательство индукцией по i. Ясно, что при i = 0, (v) = 0 влечет v = s и ут­верждение справедливо. Предположим, что утверждение верно для всех вершин v, для которых  (v)  m. Если вершина и не помечена, значит, нет пути от s к u, меньше чем m+1. Если u связана ребром с вершиной, помечной,то ее пометка, во-первых , будет равна m+1 , во-вторых , имеется путь длины m от s к данной вершине и, значит, длина кратчайшего пути от s к u равна m+1. Если u не связана ребром с вершиной, имеющей пометку m, то не существует пути, короче, чем m+1 от s к u, поскольку предыдущая вершина на этом пути имела бы

 пометку m.

Алгоритм ПУТЬ.

1)    Полагаем i =  (t) и помечаем v(i) = t.

2) Находим вершину u такую, что u связана ребром с v(i) и (u) = i-1. Помечаем v(i-1) = u.

3)    Если i = 1, то останавливаемся, и уменьшаем i на 1 и повторяем шаг 2). ♦
Приводимое ниже утверждение позволяет находить число путей фиксированной длины
между любыми двумя вершинами.

Для графа G(V,E), | V | = u определим матрицу смежности, т.е. (nn) - матрицу A = (aij), i,j = l, ... ,u,где

3.  Деревья.

1. Связный граф G(V, E), не имеющий циклов, называется деревом. Следующая теорема перечисляет некоторые основные свойства деревьев.

Теорема 1. Пусть граф G(V, E) имеет п вершин. Тогда следующие утверждения эквиваленты.

1)    G является деревом;

2) G не содержит циклов и имеет n -1 ребер;

3)    G связен и имеет n - 1ребер;

4) G связен, но удаление любого ребра нарушает связность;

5)    любые две вершины графа G соединены ровно одним путем;

6)    G не имеет циклов, но добавление любого ребра порождает ровно один цикл.

♦ При n = 1 утверждение очевидно, поэтому считаем n2. 1) => 2). По опреде­лению G не имеет циклов. Рассмотрим некоторое ребро  = (v1, v2) и удалим его. Полу­чим граф G'. В графе G' нет пути из v1 в v2 , т.к. если бы такой путь был, то в графе G был бы цикл. Значит G' не связен и не имеет циклов. Значит он состоит из двух компо­нент, являющихся деревьями с числом вершин n1 и n2 соответственно (n1 + n2 = n). По индуктивному предположению G' имеет     n1 -1 + n2 -1 ребер. Следовательно, граф G имеет n -1 ребер.

2)  => 3). Если бы G был несвязен, то каждая его компонента представляла бы собой связный граф без циклов. Из предыдущего имеем, что число ребер в каждой ком­поненте меньше на одинo числj ее вершин. Значит, общее число ребер меньше числа вершин по крайней мере на два, что противоречит тому, что G имеет п - 1ребер.

3)     => 4). Удаление любого ребра приводит к графу с n вершинами и n-2 ребрами,
который не может быть связным.

4)  => 5). В силу связности G, каждая пара вершин соединена путем. Если бы данная пара была соединена более, чем одним путем, то они образовывали бы цикл. Но тогда удаление любого ребра в цикле не нарушает связности графа.

5)     => 6). Если бы G содержал цикл, то любые две вершины на цикле соединя­лись бы по крайней мере двумя путями. Добавим теперь к графу G ребро  = (v1, v2).
Тогда образуется цикл, т.к. вершины v1 и v2 уже соединены путем. Ясно, что цикл един­ственный.

6) => 1). Если бы G был несвязен, то добавление ребер, соединяющих вершины из разных компонент, не приводит к образованию цикла. ♦

Следствие. Дерево с более чем одной вершиной имеет по крайней мере две вер­шины степени 1.

♦ Действительно, пусть v1, ..., vn - множество вершин, тогда имеем

В силу связности d(vi)  1 , отсюда и следует утверждение. ♦

2. Для графа G(V, E) определим два полезные понятия.

Вершинный подграф G(V', E') - это граф на множестве вершин              Е' E ребра­ми Е'  Е, такими, что оба конца ребра е'  Е' принадлежат V.

Реберный подграф G(V, E') - это граф, определяемый подмножеством ребер Е' E множеством вершин V  V, состоящим из концевых вершин ребер из Е'. Остовным (покрывающим) деревом графа G(V, E) называется его реберный подграф с множе­ством вершин V, являющийся деревом.

Факт 2. Граф G(V, E) имеет остовное дерево тогда и только тогда, когда он свя­зен. ♦ Предложим процедуру построения остовного дерева. Ясно, что если граф G не связен, то он не может иметь остовного дерева.

Пусть граф связен. Если в графе нет ребра, удаление которого сохраняет связ­ность графа, то G - дерево.

Если такое ребро есть, удалим его и продолжим процедуру. Когда процедура не может быть продолжена, полученный граф является деревом.

Рассмотрим теперь известную проблему нахождения минимального остовного дерева. Пусть G(V, E) неориентированный граф и пусть каждому ребру еЕ поставлено в соответствие положительное число  (е), называемое его весом. Требуется найти связ­ный реберный подграф G'(V’, E'), такой, что V’ = V, причем сумма

минимальна.

Ясно, что граф G(V, E') должен быть деревом. Действительно, если G(V', E') содержит цикл, то тогда любое ребро цикла можно удалить из графа и тем самым уменьшить сум­марный вес ребер графа G(V’, E').

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

1. Общее описание

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

Постановка задачи следующая.

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы привести задачу к научному виду, введём некоторые термины. Итак, города перенумерованы числами jÎТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j1,j2,..,jn,j1), причём все j1..jn – разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин  Сij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал

Относительно математизированной формулировки ЗК уместно сделать два замечания.

Во-первых, в постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jÎТ:

                                            Сij³0; Cjj=∞

(последнее равенство означает запрет на петли в туре), симметричными, т.е.  для всех i,j:

                                               Сij= Сji.

и удовлетворять неравенству треугольника, т.е. для всех:

                       Сij+ Сjk³Cik

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если Сij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае. Условия (2)-(4) по умолчанию мы будем считать выполненными.

Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t=(j1,j2,..,jn,j1) и t’=(j1,jn,..,j2,j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

Зафиксируем на первом и последнем месте в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.

Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j)  проведено, если Сij=0 и не проведено, если Сij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

В терминах теории графов симметричную ЗК можно сформулировать так:

Дана полная сеть с n  вершинами, длина ребра (i,j)= Сij. Найти гамильтонов цикл минимальной длины.

В несимметричной ЗК вместо “цикл” надо говорить “контур”, а вместо “ребра” - “дуги” или “стрелки”.

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

2. Методы решения ЗК

a. Жадный алгоритм

         Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. “Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию “иди в ближайший (в который еще не входил) город”. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди вы ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

            В пользу процедуры “иди в ближайший” можно сказать лишь то, что при старте из одного города она не уступит стратегии “иди в дальнейший”.

            Как видим, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, что полученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этого доказать нельзя, причем не только для жадного логарифма, а для алгоритмов гораздо более мощных. Но сначала нужно договориться, как оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации. Пусть fB - настоящий минимум, а         fA - тот квазиминимум, который получен по алгоритму. Ясно, что fA/ fB≥1, но это – тривиальное утверждение, что может быть погрешность. Чтобы оценить её, нужно зажать отношение оценкой сверху:

                             fA/fB ≥1+ nε,

где, как обычно в высшей математике, ε≥0, но, против обычая, может быть очень большим. Величина ε и будет служить мерой погрешности. Если алгоритм минимизации будет удовлетворять неравенству (5), мы будем говорить, что он имеет погрешность ε.

           Предположим теперь, что имеется алгоритм А решения ЗК, погрешность которого нужно оценить. Возьмем произвольный граф G (V,E) и по нему составим входную матрицу ЗК: