Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v3(3-4)/golubev-213-228.pdf Дата изменения: Fri May 8 16:51:18 2009 Дата индексирования: Mon Oct 1 23:56:15 2012 Кодировка: Windows-1251

Задача о гамильтоновом пути в графе с заданной размерностью пространства циклов
Д.В. Голубев
В работе рассматривается алгоритм для решения "задачи о существовании гамильтонова пути"в случае произвольного простого связного неориентированного графа. Целью рассмотрения является получение различных характеристик данного алгоритма, построение классов графов, на которых алгоритм дает решение задачи за полиномиальное время. Кроме того, устанавливается зависимость времени работы алгоритма от такого параметра графа, как размерность пространства циклов. Данная задача о существовании гамильтонова пути является N P полной в случае произвольного графа, так же как и близкие ей задачи "о существовании гамильтонова цикла "задача о коммивояжере"и др. Задача разрешима за полиномиальное время в случае, если граф не имеет вершин степени более двух, либо в случае, когда граф является деревом. В то же время на планарных, кубических, двудольных графах задача остается N P -полной. Здесь мы рассмотрим алгоритм динамической развертки графа (ДРГ). Этот алгоритм (предложенный С.В. Алешиным и В.И. Малыгиным) относится к методам динамического программирования и основан на сокращении перебора путем отсечения многократно повторяющихся подмножеств вершин графа. Кроме того, будут рассмотрены некоторые варианты алгоритма ДРГ, где сокращение перебора будет осуществляться еще и за счет отсечения неперспективных подмножеств по отношению к какому-либо полиномиально проверяемому признаку негамильтоновости графа.

1 Основные обозначения и алгоритм динамической развертки графа
Пусть G = (V , E ) - граф с множеством вершин V = {v0 , ...vn } и набором ребер E , без параллельных ребер и петель, кроме того, граф G связный


(для несвязных графов задача имеет очевидное решение, а проверка на связность является полиномиальной по сложности). Постановка задачи такова: существует ли гамильтонов путь с началом в v0 и концом в vn . Обозначим pk (vi0 , vik ) путь (vi0 , vi1 , ..., vik ) длины k , где vim = vij при m = j и для любого 0 j < k верно, что (vij , vij+1 ) E . Через G(V , E , v0 , vn ) будем обозначать граф с выделенной парой вершин v0 , vn V. Алгоритм ДРГ последовательно порождает некоторые подмножества путей, берущих начало в v0 , по следующей схеме. На первом шаге алгоритм порождает пути длины 1, соответствующие ребрам, инцидентным вершине v0 . Если на k -ом шаге алгоритм породил множество путей P k длины k с началом в v0 , то на (k + 1)-м шаге он строит P k+1 всевозможные продолжения путей из P k длины k +1. После этого элементы P k+1 делятся на классы эквивалентности таким образом, что в один класс попадают пути, содержащие одинаковое множество вершин, и, кроме того, с совпадающими последними вершинами. Говоря более точно, два пути p1 +1 (v0 , vs ) и p2 +1 (v0 , vt ) k k из P k+1 принадлежат одному классу, если vs = vt и {v |v p1 +1 (v0 , vs )} = k {v |v p2 +1 (v0 , vs )}. k Взяв в каждом классе эквивалентности по одному представителю и отбросив те, где встречается vn при k + 1 не равном n, алгоритм образует из них P k+1 . Выбор разбиения P k+1 этим способом оправдан тем, что если у какого-то представителя класса есть продолжение до гамильтонова пути, то и у всех представителей того же класса есть то же продолжение до гамильтонова пути. Таким образом, алгоритм строит P 1 , P 2 , ..., P n . Если P n не пусто, и существует представитель с последней вершиной vn , то граф G имеет гамильтонов путь из v0 в vn , если же на каком-то шаге соответствующее P k окажется пустым, либо P n не имеет представителя с последней вершиной vn , то такого пути нет. Сложность обработки алгоритмом одного пути из P k можно оценить сверху как C n2 . Оценка получается из того, что один путь может породить n потомков, а каждый из получившихся надо сравнить с другими представителями из P k+1 , что может быть сделано за линейное время, если организовать P k+1 в виде соответствующего дерева. В некоторых случаях оценку можно снизить до линейной, например, если взять класс графов с ограничением на степень вершины d(v ) K . Для удобства приведем наглядную интерпретацию работы алгоритма (рис.1)

214


Рис. 1. Граф, порожденный алгоритмом ДРГ. Будем считать, что алгоритм порождает некоторый граф DR (G), вершины которого разделены по n + 1 ярусам (0, 1, . . . , n), причем при k > 0 каждой вершине на k -ом ярусе приписан путь из P k , а на нулевом ярусе единственной вершине приписана вершина графа G v0 . Ребрам DR (G) будут приписаны ребра из E , и DR (G) может иметь ребра только между соседними ярусами. Строится DR (G) так: нулевому ярусу принадлежит вершина с меткой v0 , первому - |P 1 | вершин с приписанными им попарно различными метками из P 1 . Каждая вершина первого яруса соединена с единственной вершиной нулевого яруса ребром, которому приписано ребро из E , совпадающее с меткой вершины первого яруса. Соответственно на k -м ярусе расположено |P k | вершин с приписанными им попарно различными метками из P k . Ребра между ярусами k и k +1 присутствуют по следующему правилу: пусть vk вершина на k -ом ярусе с меткой pk , vk+1 вершина на (k + 1)-ом с меткой pk+1 , они соединены ребром с меткой e, если соответствующий путь pk можно продолжить ребром e из E , так, чтобы получить путь в том же классе эквивалентности, что и путь pk+1 . Сложностью алгоритма ДРГ на графе G(V , E , v0 , vn ) будем считать число вершин в графе DR (G) и будем обозначать его LR (G). Фактически, LR (G) равно суммарному числу путей различной длины, не превышающей n, то есть LR (G) = n=1 |P i | + 1. Из оценки, сделанной i для сложности обработки одного пути, можно оценить число элементарных операций, выполненных алгоритмом на G(V , E , v0 , vn ), сверху числом LR (G)C n2 .

215


2 Оценки сложности алгоритма ДРГ
Обозначим C размерность пространства циклов графа. Для связного графа C = |E | - |V | + 1.

мерностью пространства циклов C . Тогда LR (G) 2C n. 2) Для любого > 0 и любого целого C > 0 существует граф G(V , E , v0 , vn ) с размерностью пространства циклов C такой, что выполнено неравенство

Теорема 1 1) Пусть G(V , E , v0 , vn ) граф с числом вершин n и раз-

LR (G) > 2C n(1 - ).
Очевидно, что из вершины v0 в каждую вершину может быть только один путь, следовательно, число вершин в DR (G) равно 20 n. Каждая вершина графа G присутствует только 1 = 20 раз. Пусть доказано для графа с размерностью пространства циклов C , что любая вершина может участвовать только 2C раз в качестве последней в pi вершинах структуры k DR (G). Тогда рассмотрим граф с размерностью пространства циклов C + 1 и его произвольную вершину vk . Возможны следующие случаи: Случай А. Существует ребро (vk , vi ), такое что при выбрасывании этого ребра размерность пространства циклов уменьшится на единицу. Обозначим через FG (vk ) число путей pl , которые имеют vk своим концом. m Докажем, что FG (vk ) 2C +1 . Рассмотрим G (V , E , v0 , vn ), где E = E \ (vk , vi ), и рассмотрим DR (G ). Из предположения индукции FG (vk ) 2C и FG (vi ) 2C . Теперь вновь добавим ребро (vk , vi ) и посмотрим, сколько появится путей, не участвующих в DR (G ) и кончающихся в vk . Ясно, что если ребро (vk , vi ) pl , то оно уже было учтено в DR (G ). Таким m образом, нужно оценить число путей, кончающихся ребром (vi , vk ), но их не может быть больше FG (vi ), то есть FG (vk ) FG (vk ) + FG (vi ) 2C +1 Случай Б. Не существует ребра (vk , vi ), такого что при выбрасывании этого ребра размерность пространства циклов уменьшается на единицу. В этом случае граф G делится ребром (vk , vi ) на две компоненты связности. Обозначим через v ту вершину из vk , vi которая лежит в одной компоненте связности с v0 , а другую соответственно v . Очевидно, что любой путь из v0 в v содержит v , то есть FG (v ) FG (v ). С другой стороны, если путь кончается в v , то он не содержит ребра (v , v ), но при его добавлении получится путь, кончающийся в v , то есть FG (v ) FG (v ). Отсюда FG (vi ) = FG (vk ). Так как C > 0, то существует ребро (vm , vs ) при выбрасывании которого размерность пространства циклов уменьшится на единицу. Из связности графа G следует существование пути (vk , vi1 , vi2 , . . . , vit , vm ). Последовательно 216

Доказательство: 1) Используем индукцию по C . При C = 0 G дерево.


проходя через ребра (vk , vi1 ), (vi1 , vi2 ) и так далее, будем получать FG (vk ) = FG (vij ). Действительно, FG (vk ) = FG (vi1 ), и далее, если vi1 также не инцидентна ребрам, при выбрасывании которых размерность пространства циклов не меняется, то переходим к равенству FG (vk ) = FG (vi1 ) = FG (vi2 ) и так далее, пока либо vil не подпадет под случай А, либо мы придем к vm и снова подпадем под случай А. В первом случае имеем

FG (vk ) = FG (vi1 ) = FG (v2 ) = . . . = FG (vil ) 2C +1 ,
во втором

FG (vk ) = FG (vi1 ) = FG (v2 ) = . . . = FG (vit ) = FG (vm ) 2C +1 . 2
C +1

Таким образом, для любой вершины v справедлива оценка FG (v ) , а так как
n

LR (G) =
k=1

FG (vk ) + 1 2C +1 n,

то первая часть теоремы доказана. 2) Рассмотрим граф G(V , E , v0 , vn ) (рис. 2),

Рис. 2. где v0 = 1, vn = n + 1. Рассмотрим вершины от 2C + 2 до n + 1. Любая из этих вершин такова, что любое выходящее из нее ребро при выбрасывании не меняет размерность пространства циклов, то есть FG (vi ) = FG (vk ), vk , vi {2C + 1, . . . , n + 1}. Теперь подсчитаем число путей, имеющих конец в (2C +1)-й вершине графа. Вычислим FG (2C +1) индукцией по C .

Рис. 3.

C = 1. Очевидно, что пути два (1, 2, 3) и (1, 3), они разные. Предположим, что для C = k подсчитано. Тогда рассмотрим C = k + 1. Любой путь, кончающийся в вершине 2C + 1 проходит через 2C - 1.
217


Если путь p кончается в 2C - 1, то путями, кончающимися в 2C + 1 будут (p, 2C, 2C + 1), (p, 2C + 1). Если два пути p и p разные, то и (p, 2C, 2C + 1), (p, 2C + 1), (p , 2C, 2C + 1), (p , 2C + 1) будут, очевидно, различными (из попарного сравнения), то есть путей, кончающихся в 2C + 1 будет в два раза больше, чем путей, кончающихся в 2C - 1. Следовательно, их 2C . Отсюда, для vk {2C + 1, . . . , n} FG (vk ) = 2C и таких вершин n - 2C , то есть всего в DR (G) не менее (n - 2C )2C вершин. Для любого > 0 рассмотрим отношение

2C n - 2C (n - 2C ) 2C 2C 2C =C= . Cn 2 2n n C Очевидно, что при n > 2 неравенство из пункта 2) теоремы выполнено, то есть теорема доказана полностью. Из оценки, полученной в теореме, следует, что если у класса графов 2 размерность пространства циклов растет как K n2 , то LR (G) 2K n . Покажем теперь, что оценки, полученные в теореме, могут эффективно применятся лишь при росте размерности пространства циклов не более порядка K n. Это разъясняется следующей теоремой о сложности LR (G) в случае полного графа G. Очевидно, что сложность LR (G ) для произвольного подграфа G графа G меньше LR (G).

Теорема 2 Если G(V , E , v0 , vn ) полный граф, то LR (G) < n 2 2 n . 2 Доказательство. Рассмотрим разбиение по ярусам структуры DR (G).
Подсчитаем число вершин DR (G) на k -ом ярусе при k = 0, n. Ясно, что концами соответствующих путей могут быть все вершины кроме v0 и vn , то есть {v1 , v2 , v3 , . . . , vn-1 } множество концов. В полном графе может k -1 быть Cn-2 (не совпадающих как множества вершин) различных путей длины k - 1 к конечной вершине vi . Таким образом на k -ом ярусе ровно k -1 k-1 (n - 1)Cn-2 вершин. Оценим Cn-2 через n:
k-1 Cn-2 Cn2 2 Cn2 - [ n ]-1 [n]

3

n!
nn ! 22

!

.

По формуле Стирлинга: x! = 2 xx+1/2 e-x+/12x , x > 0, 0 < < 1. Отсюда n! 2 nn+1/2 (-n+1 /12n+n/2+n/2-2 /6n-2 /6n) e = nn = !! 2 ( n )n/2+n/2+1 22
2

=

nn+1/2 2 ( n )n 2

+1

e(

1 /12n-2 /3n)

.

218


Оценив 1 = 1, 2 = 0, получим

1 e 2

(1 /12n-2 /3n)

1 e1/ 2

12n

1 < e1/ 2 n 2
-1/2

24

1 = 0,416 . . . < . 2

Соответственно

n! 1n nn < !! 2 n/2 22

n+1/2

2n-1 n

-1/2

,

k -1 то есть Cn-2 < 2n-1 n-1/2 , а так как в DR (G) n ярусов (на нулевом ярусе одна вершина, на n-ом не более n), то можно оценить LR (G) < n(n - 3 n 2 2 n , что и требовалось доказать. n-1 -1/2 1)2 n <2 Параметр C размерность пространства циклов графа дает возможность разделить все множество графов на несколько классов, если установить зависимость C (n) заданный рост размерности пространства циклов с ростом n. Две предыдущие теоремы дают следующую таблицу:

C (n) K log n K log n K n, K 1 max LR (n) 2K n n2 nK 2K n n min{2

Kn

Kn K n2 n, 2n n3/2 /2} 2n n3/2 /2

где Lmax (n) оценка сверху для произвольного представителя соответствующего R класса графов с числом вершин n и размерностью пространства циклов C (n). При C (n) = K n, K > 1, ясно, что рост 2K n n быстрее 2n n3/2 /2 и, следовательно, существует такое N (K ), что для любого n > N (K ): 2K n n > 2n n3/2 /2, то есть применимость теоремы 1 фактически ограничена случаем C (n) < n. Наличие графов "большой"сложности установлено второй частью теоремы 1. Таблица дает возможность получить представление о структуре всего множества графов по отношению к полиномиальной разрешимости задачи о существовании гамильтонова пути с помощью алгоритма ДРГ. Если класс графов обладает характеристикой C (n) < K log2 n, задача о существовании гамильтонова пути на нем полиномиально разрешима и степень полинома не превышает K + 3.

3 Модифицированный алгоритм ДРГ и позитивная проверка на негамильтоновость
Рассмотрим произвольный путь pk (v0 , vk ) P k в алгоритме ДРГ, k < n. Пусть граф G (V , E , vk , vn ) такой, что V = {v |v P k } vk , E = {(vi , vj )|vi V , vj V , (vi , vj ) E }. 219


Очевидно, если G не имеет гамильтонова пути из vk в vn , то в действительности рассматривать pk (v0 , vk ) не требуется. Существует довольно много признаков, по которым можно сказать, что граф не имеет гамильтонова пути из одной вершины в другую, но нас будут интересовать только те из них, которые можно проверить полиномиально. Назовем модифицированной динамической разверткой графа (МДРГ) алгоритм ДРГ, в котором из множества P k на каждом шаге удаляются некоторые пути, дополнение к которым подпадает под какой-то из заранее заданных полиномиально проверяемых признаков негамильтоновости в указанном смысле. Как будет показано, в общем случае МДРГ мало выигрывает по сравнению с ДРГ в плане понижения верхней оценки сложности, но в то же время существует ряд случаев, когда МДРГ дает понижение средней сложности алгоритма на заданном классе графов. Сложностью МДРГ, как и в случае ДРГ, будем считать число вершин в соответствующем графе DR (G). Определение. Граф G(V , E , v0 , vn ) называется гамильтоновым из v0 в vn , если существует гамильтонов путь, соединяющий v0 с vn . Определение. Назовем проверку графа на негамильтоновость позитивной, если: 1) для некоторого класса графов G, для любого представителя G(v0 , vn ) этого класса, если G(v0 , vn ) не гамильтонов из v0 в vn , то проверка дает правильный ответ об этом за полиномиальное время от 2n; 2) если граф G(V , E , v0 , vn ) G, то граф G0 , полученный из G(v0 , vn ) добавлением к нему G (V , E , v0 , vt ) путем отождествления vt и v0 должен принадлежать классу G, для любого G (v0 , vt ) гамильтонова графа из v0 в vt . Примером непозитивной проверки служит любой алгоритм, сверяющий данный граф с некоторым конечным множеством графов, не имеющих гамильтонова пути. Примером позитивной проверки может служить проверка на связность. Действительно, если граф не связен, то он и не гамильтонов, к тому же добавление к одной из компонент связности дополнительного числа вершин и ребер повлиять на связность в целом не может. Другими позитивными проверками являются проверка на висящие вершины (вершины степени один), на двудольность графа с разницей вершин в разных долях, превышающей единицу, и т.д. Важным является следующее: позитивная проверка выделяет (в некотором смысле) причину негамильтоновости графа, а не просто вычисляет, гамильтонов граф или нет. Приведенные позитивные проверки для графа со степенью вершин не более трех имеют линейную сложность относительно числа вершин в графе, а в произвольном случае квадратичную. ДРГ же имеет в общем случае экспоненциальный рост сложности, поэтому имеет смысл применять МДРГ, так как это может существенно сократить 220


число вершин структуры DR в целом и соответственно уменьшить не только LR (G), но и сложность по времени. Возникает вопрос, как меняется сложность МДРГ, если мы будем "наращивать"мощность проверки, то есть расширять класс G. Ситуация с max LR,P (G(n)) разъясняется следующей теоремой:
G(n)

Теорема 3 Пусть P произвольная позитивная проверка для класса
графов G и G не является всем множеством негамильтоновых графов, тогда для любого n > N (P ) существует граф G(v0 , vn ), такой что

LR,P (G(v0 , vn )) const 2n

-K (P )

.

Доказательство. Так как G не является всем множеством негамильтоновых

графов, то существует G (V , E , v0 , vl ) негамильтонов граф из v0 в vl такой что проверка P не дает ответа на вопрос: гамильтонов граф или нет. Будем считать, что G имеет минимальное число вершин среди всех графов, обладающих таким свойством. Обозначим число его вершин K (P ). Теперь рассмотрим полный граф G (V , E , v0 , vn-K (P ) ) и отождествим v0 и vn-K (P ) . В результате такого отождествления мы получим граф G (рис.4). Покажем, что на графе G сложность МДРГ не меньше, чем сложность ДРГ на графе G , то есть, что LR,P (G) LR (G ).

Рис. 4. Рассмотрим любой путь pk DR (G ). Ему соответствует pk DR,P (G), имеющий точно те же вершины, что и pk . Докажем это индукцией по k . Для k = 0 очевидно. Пусть для k = m доказано. Тогда рассмотрим i i i произвольный путь pi +1 = (v0 , v1 , . . . , vm , vm+1 ), он получен из некоторого m j i j i j pj = (v0 , v1 , . . . , vm = vm ) добавлением ребра (vm , vm+1 ). Допустим, что m i pm+1 в DR,P (G) не получен. Это означает, что граф, полученный из G j j j j j j j выбрасываниемребер (v0 , v1 ), (v1 , v2 ), . . . , (vm-1 , vm ) и вершин (v0 , v1 , . . . vm ), i с начальной вершиной vm+1 и конечной vl не гамильтонов и отбрасывается проверкой P . Но так как G полный граф, то в нем существует гамильтонов путь из любой вершины в любую с любым порядком вершин между ними, 221


j j i в частности, с таким: (v0 , v1 , . . . , vm , vm+1 , . . . , vn-K (P ) ), но последний кусок i i vm+1 , . . . , vn-K (P ) гамильтонов путь в G без py из вершины vm+1 в m вершину vn-K (P ) . Причем ни одна из вершин G не участвует в нем (кроме, естественно vn-K (P ) ). Таким образом G (G \ pj ), G (G \ m i pj ) = v0 и в (G \ pj ) существует гамильтонов путь из vm+1 в v0 . По m m определению позитивной проверки путь pi +1 не может быть отброшен, m то есть LR,P (G(v0 , vn )) LR (G ) const 2n-K (P ) ,

и граф удовлетворяет условию теоремы. Обозначим Gi множество негамильтоновых графов со степенью вершин P не более i, на которых проверка P дает ответ, что граф негамильтонов.

Утверждение 1 Пусть P произвольная позитивная проверка и G

не является всем множеством негамильтоновых графов, у которых степень вершины не более четырех. Тогда для любого n > N (P ) существует граф G4 (v0 , vn ), такой что степень его вершин не более четырех и справедлива оценка: n-K LR,P (G4 ) 2 3 .

4 P

Доказательство. Рассмотрим граф G(V , E , v0 , vk ) на 3k - 1 вершинах

(рис. 5). Оценим снизу число различных гамильтоновых путей из 1 в m = 3k - 1 следующим образом: рассмотрим граф на вершинах от 1 до 2k - 1 как граф в пункте 2) доказательства теоремы 1. Из 1 в 2k - 1 существует 2k путей. Легко видеть, что любой из этих путей может быть дополнен до гамильтонова пути, причем единственным образом (рис. 6), то есть в DR,P (G) не менее 2k вершин.

Рис. 5. 222


Рис. 6. Рассмотрим, как и в предыдущем случае, граф G (v0 , vK (P ) ) минимальный негамильтонов (считаем d(v0 ) < 3) и не принадлежащий G4 . Возьмем P в качестве G4 объединение G и G с отождествленными вершинами v0 и v3k-1 . Как и в доказательстве предыдущей теоремы, получим соответствующую n-K оценку LR,P (G4 (v0 , vn )) 2 3 .

не является всем множеством негамильтоновых графов со степенью вершин не более трех. Тогда для любого n > N (P ) существует граф G3 (v0 , vn ), такой что степень его вершин не более трех, и справедлива оценка n-K LR,P (G3 ) 2 6 .

Утверждение 2 Пусть P произвольная позитивная проверка, и G

3

Доказательство. Оценка получается из рассуждений, аналогичных предыдущему
доказательству, но при рассмотрении графа G(V , E , v0 , vr ) (рис. 7).

Рис. 7. 223


здесь оценка LR,P (G) 2k и, соответственно,

LR,P (G3 ) 2

n-K 6

.

4 Оценки сложности для МДРГ с проверкой на висящие вершины
Теперь обратимся к рассмотрению МДРГ с проверкой на висящие вершины (то есть вершины степени один) и получим ряд оценок для сложности алгоритма на различных классах графов. Ясно, что оценки сверху, полученные в предыдущем разделе, остаются в силе, но вполне естественно, что МДРГ с проверкой на висящие вершины имеет свои особенности. Далее будем считать, что все рассматриваемые графы связные и без висящих вершин, если не оговорено иначе. Определение. Пусть G(V , E , v0 , vn ) граф, тогда назовем вершину v = v0 , vn обладающей свойством " если: 1) ей инцидентно не менее трех ребер; 2) она соединена ребрами не более чем с одной вершиной степени два; если v = v0 то она обладает свойством " если: 1) ей инцидентно не менее двух ребер; 2) она соединена с вершинами степени больше двух. ~ Определение. Назовем конденсацией графа число K , равное количеству вершин, обладающих свойством "".

~ Теорема 4 Пусть K конденсация графа G(V , E , v0 , vn ), и G граф со
степенями вершин не более трех (v0 не более двух). Тогда справедлива оценка: ~ LR,V (G) 2K n.

~ Доказательство. Докажем теорему индукцией по K .

~ K = 1. То есть существует только одна вершина v , обладающая свойством "". Рассмотрим DR,V (G). Пусть pk = (v0 , . . . , vk ) произвольный путь. Покажем, что pk не может породить два пути на (k + 1)-м ярусе, если vk = v . Действительно, пусть порождены два пути pk+1 = (v0 , . . . , vk , vk+1 ) и pk+1 = (v0 , . . . , vk , vk+1 ). Тогда оба графа G \ ({v0 , . . . , vk } (vk , vk+1 )) и G \ ({v0 , . . . , vk } (vk , vk+1 )) не имеют вершин степени меньше двух, за исключением может быть vn . Но вершина vk не обладала свойством " и поэтому как минимум одна из вершин vk+1 , vk+1 имела степень два в графе G \ {v0 , . . . , vk-1 }. При порождении пути pk+1 (pk+1 ) степень vk+1 (vk+1 ) понижается на единицу, то есть один из путей pk+1 (pk+1 )
224


отбрасывается проверкой на висящую вершину и, следовательно, pk не может породить два пути, если vk = v . Если же vk = v , очевидно, можно ~ породить максимум два пути. Таким образом при K = 1 на любом ярусе может быть не более двух вершин, а значит LR,V < 21 n. ~ Теперь пусть для K = l неравенство выполнено, проверим его для ~ K = l + 1. Сначала покажем, что если выбросить из графа G путь (v0 , . . . , vk-1 ) и ребро (vk-1 , vk ), где хотя бы одна из вершин v1 , . . . , vk-1 обладает свойством " то конденсация графа G = G \ ({v0 , . . . , vk-1 } (vk-1 , vk )) уменьшится. Ясно, что степени вершин в G не больше степеней в G, а значит, если вершина не обладала свойством " то и приобрести она его не может. То есть свойством ""в G могут обладать только те вершины, которые имели его в G. Но в G на одну такую вершину меньше. Теперь рассмотрим DR,V (G), где G имеет конденсацию l+1 и рассмотрим первый ярус, на котором встретится вершина со свойством "". Ясно, что на этом ярусе присутствует ровно одна вершина (из рассуждений, ~ аналогичных доказательству при K = 1), так же, как и на всех предыдущих ярусах, если они есть. На следующем ярусе k + 1 может быть не более двух вершин. Рассмотрим их по отдельности (рис. 8).

Рис. 8.

pk+1 = (v0 , . . . , vk , vk+1 ) и pk+1 = (v0 , . . . , vk , vk+1 ). Если взять графы G = G \ ({v0 , . . . , vk } (vk , vk+1 )) и G = G \ ({v0 , . . . , vk } (vk , vk+1 )), то, очевидно что: k+L
R,V

(G (v

k+1

, vn )) + LR,V (G (v

k+1

, vn )) LR,V (G(v0 , vn )),

так как любой путь pk+m порожден либо из pk+1 , либо из pk+1 , и условия порождения структур DR,V (G ), DR,V (G ) менее строгие, чем условия порождения DR,V (G). А поскольку G и G получены из G выбрасыванием пути (v0 , . . . , vk ) и соответствующего ребра, то G и G имеют конденсацию не более l, то есть по предположению индукции LR,V (G ) (n - k )2l и LR,V (G ) (n - k )2l , откуда LR,V (G) k + (n - k )2l+1 n2l+1 , что и требовалось доказать. Можно показать, что справедлива также 225


~ Теорема 5 Пусть K конденсация графа G(V , E , v1 , vn ), и G граф
со степенями вершин не более t, 3 < t < n - 1 (степень v1 не более t-1). Тогда справедлива оценка:

LR,V (G) 2K

~ log(t-1)

n.

~ Пользуясь параметром K , во многих случаях можно уменьшить оценку, полученную при использовании размерности пространства циклов. С другой стороны, конденсация и размерность пространства циклов не ~ ~ являются независимыми. Ясно, например, что K 2C . Число K может быть строго фиксировано при одних значениях C и меняться в довольно широких пределах при других. При этом, чем меньше C по отношению ~ к числу вершин, тем больше свободы для значений K на [0, 2C ]. Пусть граф G связный, с n вершинами, не имеет вершин степени один, не имеет вершин степени больше трех, и C размерность пространства циклов. Обозначим k3 количество вершин степени три, k2 количество вершин степени два, тогда имеем уравнения на количество ребер и вершин: k3 + k2 = n 3k3 + 2k2 = 2(n - 1 + C ) 2k2 + 3n - 3k2 = 2n - 2 + 2C k2 = 3n - 2n + 2 - 2C = n - 2C + 2 k3 , - 2
Если считать, что граф G выбран случайно с такими параметрами, то для любой вершины степени три можно вычислить вероятность того, что она обладает свойством " в зависимости от n и C . Обозначим:

N = 3(2C - 3) + 2(n - 2C + 2), M = 3(2C - 3).
Тогда:
2 1 CN CN 3 CN 3 0 CN CN 3 CN

p(n, C ) = = 6 N (N - 1)(N - 2) = =

-M

+

-M

= =

M (M - 1)(N - M ) M (M - 1)(M - 2) + 2 6 M -2 N -M + 2 6 3N - 3M + M - 2 6
226

6M (M - 1) N (N - 1)(N - 2)

= =

6M (M - 1) N (N - 1)(N - 2)


=

M (M - 1)(3N - 2M - 2) (6n - 6C + 1)(6C - 9)(6C - 10) = . N (N - 1)(N - 2) (2n + 2C - 5)(2n + 2C - 6)(2n + 2C - 7)

Если пренебречь зависимостью вероятностей обладания свойством ""для разных вершин, мы получим биномиальное распределение вероятностей для значений конденсации графа. Естественно, что при таком предположении среднее значение конденсации будет совпадать с математическим ожиданием биномиального распределения с параметром p(n, C ). Обозначив среднее ~ ~ значение K через E (K ), получим:

~ E (K ) = (2C - 2)

(6n - 6C + 1)(6C - 9)(6C - 10) (2n + 2C - 5)(2n + 2C - 6)(2n + 2C - 7)

(1)

Если размерность пространства циклов C (n) = M log2 n, то с ростом ~ n E (K ) 0 и, соответственно, средняя сложность алгоритма на классе графов с ростом размерности пространства циклов C (n) = M log2 n растет практически линейно, а не как nM +1 . Использование формулы (1) позволяет не только улучшить оценку для класса графов с C (n) = M log n (где линейность средней сложности легко объяснима за счет резкого уменьшения вероятности p(n)), но и сделать выводы об устройстве класса с C (n) = M n при малых M , и тем самым обосновать оценку средней сложности для этого класса E (LR,V (G)) 2 n2 n , где = 9(1-M ))M , что может быть существенно меньше M . (1+M 3 Теперь откажемся от ограничения на степень вершины. Рассмотрим классы C (n) = M log n и C (n) = M n. Так как степень вершины не ограничена тремя, то вершин степени два будет не меньше, чем в только что рассмотренном случае, кроме того, если степень вершины больше трех, то это только уменьшает вероятность наличия у нее свойства "". Таким образом, можно оценить эту вероятность p (n, C (n)) сверху через уже полученное значение:

p (n, C (n))

(6n - 6C (n) + 1)(6C (n) - 9)(6C (n) - 10) (2n + 2C (n) - 5)(2n + 2C (n) - 6)(2n + 2C (n) - 7)

~ Исходя из этого, получим оценку и для математического ожидания E (K ): ~ E (K ) (2C (n) - 2) (6n - 6C (n) + 1)(6C (n) - 9)(6C (n) - 10) (2n + 2C (n) - 5)(2n + 2C (n) - 6)(2n + 2C (n) - 7)

В силу предыдущей теоремы для класса C (n) = M log n имеем оценку для средней сложности:

E (LR,V (G)) n(n - 2)E

~ (K )n

= n2E

~ (K )n log(n-2)

,

227


~ но при n E (K )n log n 0, а значит, начиная с некоторого n, рост средней сложности не более чем линейный. Такой же результат получается, если рассмотреть случай C (n) = M (log n)k для любого k . В случае роста C (n) = M n можно также получить оценку средней сложности: в случае, если степень вершины ограничена константой t, она имеет следующий вид: E (LR,V (G)) n2log
(t-1) n

.

Список литературы
[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Пер. с англ. М., Мир, 1982. [2] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. М., Мир, 1979. [3] Справочник по специальным функциям под ред. М. Абрамовица и И. Стиган. Пер. с англ. М., Наука, 1979. [4] Севастьянов Б.А. Курс теории вероятностей и математической статистики. М., Наука, 1982. [5] Харари Ф. Теория графов. Пер. с англ. М., Мир, 1973.

228