4.6. Представление графов списками инцидентности. Оценка пространственной сложности алгоритмов.

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

Под пространственной характеристикой сложности алгоритма понимают оценку О(f(n₁, n₂, …, n_k)) требуемой памяти компьютера в зависи­мости от мощностей n₁, n₂, …, n_k множеств исходных дан­ных при неограниченном уве­личении этих мощностей.

По определению классического анализа O(f(x)) вводится следующим образом.

Пусть x₀ — некоторое предельное значение.

Если для функций и g(x) существуют такие постоянные A > 0 и δ > 0, что

|g(x)| ≤ A |f(x)| при |x - x₀| < δ, x ≠ x_0, то говорят, что g является ограниченной по сравнению с f функцией в некоторой окрестности точки x₀ и пишут

g(x) = O(f(x)) при x → x₀.

Последнее выражение читается следующим образом: «g(x) есть O большое от f(x) при x стремящемся к x₀».

Таким образом, выражение O(f(x)) представляет асимптотическую оценку, которая имеет место лишь в некоторой окрестности x₀.

Естественным образом это определение переносится и на случай x → ∞, что представляет теоретический интерес при оценке сложности алгоритмов.

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

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

1, log (x) , x, x log (x), x², …, x^m (m — больше нуля), c^x (c > 0), x! (при натуральном x), x^x (x > 0) и другие.

Символ О(f(x₁, x₂, …, x_k)) функций многих переменных вводится аналогично тому, как и для функций одного переменного.

На практике при оценке пространственных затрат алгоритмов функцию О(f(n₁, n₂, …, n_k)) определяют как асимптотически потребное число ячеек памяти при n₁, n₂, …, n_k → ∞.

При оценке пространственной сложности размещения графов имеем f(n_v, n_u), где n_v, n_u — соответственно число вершин и ребер графа.

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

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

Аналогично, в случае представления графа матрицей инцидентности, имеем асимптотическую оценку O(n_un_v). Фактически она также сводится к предыдущей поскольку, если граф имеет хотя бы одно ребро, то всегда найдется такая постоянная A > 0, что An_u = n_v.

Исследования показали, что пространственные затраты можно оценивать не квадратом, а — первой степенью, если изменить способ представления графов. В качестве альтернативы был предложен способ, именуемый: представление графов списками инцидентности.

Такое представление в программировании базируется на понятиях указателя, записи и списка.

Пусть имеем некоторое множество переменных: A, B, C, … . Поставим каждой из этих переменных в однозначное соответствие некоторое число. Это число будем име­новать указателем на переменную, например А, и обоз­начать @A в формулах либо →А на графиках. Указатель на несуществующую переменную условимся обозначать специальным символом — nil.

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

Под записью понимают поименованное упорядоченное множество переменных. Например, переменные ‹x, y, z› мо­жно поименовать так: A = ‹x, y, z›. При этом пред­полагается, что переменные x, y или z представляют любые математические объекты, например, скаляры, векторы, и т.д.. Эти переменные именуются полями записи. Для того, чтобы адресоваться, скажем, к полю x записи A применяют обозначение: A.x.

Под списком понимают упорядоченную последовательность записей, в которой каждая предыдущая запись содержит в качестве одного из полей указатель на последующую запись. Кроме того определен указатель на первую запись как на начало списка, а последняя в качестве поля указателя содержит nil. Таким образом, список любого числа записей полностью определяется указателем на его начало.

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

Списки инцидентности на примере представления графа, изображенного на рисунке 4.9, представлены на рисунке 4.10.

Из описанного построения видно, что каждый список инцидентности представляет множество ребер, инцидентных данной вершине графа. Множество всех списков, отвечающих каждой из вершин некоторого графа G, представляет данный граф.

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

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

Например, граф, изображенный на рисунке 4.9, представляется следующим семейством:

v₂, v₃,  , v₂, v₄,  ,  v₄,v₆ , v₅ .

v1			v2			v3		nil
v2	nil
v3			v2			v4		nil
v4	nil
v5			v6			v4		nil
v6			v5	nil

Рисунок 4.10

Такой способ представления графов обладает тем преимуществом, что общее количество числа ячеек памяти, необходимых для представления графа, определяется всего лишь как O(n_v+n_u). Кроме того, структура мобильна в отно­шении к преобразованиям графа, связанных с добавлением или уменьшением числа его ребер: ребро просто включается в спи­сок либо удаляется из списка.

Отметим, что в различных языках программирования имеются эффективные средства организации и обработки списков.