Машинное представление графов и сетей.

Задать граф (орграф) — значит описать множества его вершин (узлов) и ребер (дуг), а в случае взвешенного графа или сети, описать также функцию весов с: Е→R.

Мы будем предполагать, что вершины графов и узлы сетей за­нумерованы натуральными числами от 1 до n. Поэтому для опи­сания множества вершин (узлов), если не указана какая-нибудь дополнительная информация, достаточно задать одно число — число вершин (узлов) n.

Для представления множества ребер (дуг) имеется много раз­личных способов. Мы разберем здесь лишь основные из них. Но вначале сформулируем условия, по степени выполнения которых определяют, удачно или неудачно то или иное представление графа (орграфа).

1. Требуемый объем памяти.

2. Удобство доступа к информации для ответа на вопросы:

a) имеется ли в графе (орграфе) ребро {v,w} (дуга (v,w))?

b) к каким вершинам (узлам) ведут ребра (дуги) из V?

c) какова степень вершины (узла) v?

3. Удобство доступа к информации для осуществления сле­дующих процедур:

a) добавить к графу (орграфу) ребро {v,w} (дугу (v,w));

b) удалить из графа (орграфа) ребро {v,w} (дугу (v,w));

Разберем несколько способов машинного представления гра­фа (орграфа) G = (V,E), где n= |V |, m= | Е |.

Матрица смежностей. Она определяется как матрица А раз­мера n n, в которой A[v,w]=l тогда и только тогда, когда ребро {v,w} (соответственно дуга (v,w)) имеется в графе (орграфе), и A[v.w]=0 в противном случае.

А= А=

Рис 2.3. а) Неориентированный граф и его матрица смежностей,

б) Ориентированный граф и его матрица смежностей.

Легко видеть, что матрица смежностей неориентированного графа является симметричной.

Представление графа матрицей смежностей удобно для тех алгоритмов, которым многократно нужно выяснять, есть ли в графе ребро (дуга), соединяющее заданные вершины v и w, ибо это осуществляется за один шаг — одно обращение к матрице. Матрица смежностей удобна и в том случае, когда многократно нужно корректировать граф, добавляя в него или удаляя из него ребра. Поэтому сточки зрения пунктов 2.а, З.а, З.б представление графа матрицей смежностей является очень хорошим. Однако, для ответа на вопросы 2.6 и 2.в нужно просмотреть всю строку матрицы с номером v. Следовательно, сложность ответа на лю­бой из этих вопросов для фиксированной вершины есть О(n).

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

Взвешенный граф (или сеть) G = (V,E,c), может быть задан в ЭВМ матрицей весов А. в которой полагают A[v,w] = c({v,w}) - весу ребра {v,w} (или весу дуги c((v,w)) ), и A[v,w] = ∞ — для ребер (дуг), отсутствующих в графе (сети). Иногда, в зависимо­сти от специфики конкретной задачи, уточняют знак бесконечно­сти, выбирая либо +∞, либо - ∞.

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

Задача сортировки формулируется следующим образом: дана последовательность из n элементов a₁,...,a_n, выбранных из мно­жества, на котором задано отношение линейного порядка. Требу­ется найти перестановку s = (s(l),…,s(n)) индексов, для которой a_s(1) ≤ a_s(2) ≤ ... ≤ a_s(n), т.е. расположить элементы данной последо­вательности в неубывающем порядке (или в невозрастающем, т.е. a_s(1) ≥ a_s(2) ≥ ... ≥ a_s(n)).

Сортировка — практически важная и теоретически интересная задача. Она является неотъемлемой частью многих алгоритмов решения задач дискретной оптимизации. Решая задачу сортиров­ки, мы введем полезную структуру данных — представление массива в виде двоичного дерева данных. Такая структура пред­ставляет самостоятельный интерес и часто используется на прак­тике.