§ 3. Асимптотические оценки (два примера)

27

лу арифметических операций, сравнений и перемещений мы имеем оценку O(.s(n)), где s(n) —соответствующая сложность используемой сортировки.

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

Для любой сортировки массивов длины n, имеющей некоторую сложность s{n) по общему числу сравнений и перемещений элемен­тов, существует алгоритм построения выпуклой оболочки n точек, заданных массивом своих координат на плоскости, сложность кото­рого по общему числу арифметических операций, сравнений и переме­щений есть O{s{n)).

Пространственная сложность алгоритма Грэхема, очевидно, есть O{n).

Пример 3.2. Пусть G = {V, E) — ориентированный граф без крат­ных ребер и v е V. Вояжем по G, выходящим из вершины v, будем называть любой путь, который

65535. начинается в вершине v,

65535. не проходит ни по одному из ребер дважды,

65535. завершается в вершине, из которой не выходит ни одного непрой-денного ребра

(вояж не обязательно охватывает все ребра G). Примером выходя­щего из вершины 1 вояжа в изображенном на рис. 3 графе служит (1,2,2,3,1,4).

4

1

3

|2~Л

5

7

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

Построение какого-то одного выходящего из данной вершины v вояжа может быть выполнено произвольным блужданием по непрой-денным ребрам графа, завершающимся в вершине, из которой не выходит непройденных ребер. Систематизация блужданий может со-

28 Глава 1. Сложности алгоритмов как функции числовых аргументов

стоять в том, что, попав в некоторую вершину, мы выбираем для продолжения пути ребро, ведущее в вершину с наименьшим доступ­ным номером.

Определяемый этим алгоритмом вояж может захватить и все реб­ра— например, когда граф имеет вид кольца (на рис. 4 изображен такой граф, для которого |E| = |V| = 5). Входом алгоритма является

граф G и вершина v. Если мы рассматри- 3 ваем \E | как размер входа, то для сложно-

5

1

сти любого алгоритма построения вояжа обязательно имеет место нижняя оцен­ка П(|E|)—ввиду, например, того, что для любого фиксированного |E| существу­ет граф, имеющий вид кольца. Возника­ет вопрос, можно ли обосновать верхнюю оценку O(|E|)? Если да, то в итоге это да­ло бы оценку в(|E\).

Рис. 4. Граф в виде кольца

(любой вояж охватывает

все ребра).

Для представления графов, не имею­щих кратных ребер, часто используются матрицы смежности. Матрица смежно­сти— квадратная матрица порядка |V|, состоящая из нулей и единиц (фактиче­ски, булева матрица), в которой элемент с индексами i,j равен единице, если и только если из i-й вершины выходит ребро в j-ю вершину. Такой способ представления действи­тельно удобен во многих задачах. Но когда речь идет о блуждани­ях по графу, при которых однажды пройденное ребро изымается из дальнейшего рассмотрения, более удобным оказывается представле­ние графа в виде массива a₁,a₂, ...,a\_V\ списков смежных вершин. В списке a_i , i = 1, 2,..., |V |, в порядке возрастания содержатся номера вершин, в которые входят ребра, выходящие из вершины с номером i. Для графа, приведенного на рис. 3, имеем

a₁ = (2,4), a₂ = (2,3), a₃ = (1,4), a₄ = (), a₅ = (6), a₆ = (5), a₇ = ();

для графа в виде кольца —

a₁ = (2), a₂ = (3), ..., a_V_₁ = (V\), a_V = (1)

(в этом графе |V| = |E|). Представление в виде массива списков смеж­ных вершин возможно и для графов, имеющих кратные ребра; в этом случае номера вершин в каждом списке располагаются в порядке неубывания.