Сравнение различных схем машинного представления графов. Преимущества, недостатки

Основная терминология

Схемы машинного представления графов.

Сравнение различных схем машинного представления графов. Преимущества, недостатки

1. Основная терминология

Для наших целей граф — это конечное множество вершин , или узлов, и конечное множество ребер , которые суть неупорядоченные пары вершин. Граф называется помеченным, если каждая его вершина имеет некоторую метку – «имя». Чаще всего этой меткой является натуральное число.

Введение графов имеет своей целью облегчить изучение разреженных матриц. Установим связь между матрицами и соответствующими им графами. Пусть - симметричная -матрица. Помеченный граф матрицы - это граф , для которого вершин пронумерованы числами от 1 до и пара вершин графа , т.е. является ребром графа, тогда и только тогда, когда . Здесь - узел с меткой . Рис.1 иллюстрирует структуру матрицы (рис.1(а)) и ее помеченного графа (рис.1(б)).

а б

Рис.1.

Если - произвольная -матрица перестановки (см.лекц.8), то непомеченные графы матриц и совпадают, а соответствующие помечивания различны. Таким образом, непомеченный граф представляет структуру без упоминания о каком-либо конкретном упорядочении. Он изображает класс эквивалентности матриц . Отыскание «хорошей» перестановки для можно рассматривать как отыскание «хорошего» помечивания для ее графа. На рис.2 проиллюстрировано сказанное.

Два узла из графа называются смежными, если . Если , то смежное множество для есть

.

Иначе: есть множество узлов , не принадлежащих , но смежных хотя бы с одним узлом из .

Для степень , обозначаемая через , есть число , где - обозначение числа элементов множества .

Если - различные узлы графа , то путем из в длины называется упорядоченное множество из различных узлов , такое, что , причем . Граф называется связным, если каждая пара различных узлов соединена хотя бы одним путем. В противном случае несвязен и состоит из двух или более связных компонент.

Рис.2.

1. Схемы машинного представления графов

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

Пусть — неориентированный граф с вершинами. Списком смежности для вершины называется множество

Структура смежности графа — это множество списков смежности для всех его вершин. Такую структуру можно реализовать, сохраняя последовательно списки смежности узлов в одномерном массиве длины , и используя дополнительный индексный массив длины , который содержит указатели начала каждого списка смежности в массиве ( — адрес первой свободной ячейки в массиве ) (рис.3). Общая длина массивов при такой схеме хранения — .

Рис.3. Пример структуры смежности графа

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

Рис.4. Модификация структуры смежности графа при добавлении вершины

Данная проблема очевидно остается нерешенной и при использовании для представления графа нижней структуры смежности. Здесь вместо хранения для каждого узла полного списка смежности сохраняются только те узлы из , метки которых больше, чем у , что может значительно сократить запросы к памяти. Для графа, представленного на рис.3, нижняя структура смежности изображена на рис.5. Общая длина массивов при такой схеме хранения — : длина массива уменьшилась в два раза по сравнению с хранением всей структуры смежности, поскольку теперь каждое ребро будет учтено лишь 1 раз (для той из двух инцидентных ему вершин, номер которой меньше).

Одной из наиболее простых схем хранения графа является таблица связей - двумерный массив, который имеет строк и столбцов, где — максимальная степень вершин в . Список смежности го узла сохраняется в ой строке. Для графа, приведенного на рис.3, таблица связей будет иметь вид:

.

Данная схема хранения чрезвычайно проста при реализации, доступ к списку смежности очередного узла - доступ к соответствующей строке матрицы, модификация графа приводит к изменению элементов соответствующих строк матрицы без нарушения общей структуры (если при модификации не изменяется ). Однако эта схема может быть чрезвычайно неэффективной, если большое количество узлов графа имеет степень, (значительно) меньшую, чем максимальная, поскольку ее требования к памяти определяются как «сохраняемых» элементов.

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

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

Рис.6. Схема хранения, основанная на поле связей: исходный граф (а); граф после добавления вершины (б)

1. Сравнение различных схем машинного представления графов. Преимущества, недостатки

Схема хранения графа	Преимущества	Недостатки	Общие запросы к памяти
Основанная на структуре смежности графа	Простая организация поиска соседей текущего узла	Вызывает трудности внесение изменений в структуру смежности графа. Добавление (исключение) узлов (ребер) из графа приведет к модификации всего массива и
Основанная на нижней структуры смежности графа	Простая организация поиска соседей текущего узла Значительное сокращение запросов к памяти по сравнению со схемой, основанной на структуре смежности графа	Вызывает трудности внесение изменений в структуру смежности графа. Добавление (исключение) узлов (ребер) из графа приведет к модификации всего массива и
Таблица связей	Схема проста при реализации, доступ к списку смежности узла - доступ к соответствующей строке матрицы; модификация графа приводит к изменению элементов соответствующих строк матрицы без нарушения общей структуры (если при модификации не изменяется ).	Схема может быть чрезвычайно неэффективной, если большое количество узлов графа имеет степень, значительно меньшую, чем максимальная	- количество вершин, — максимальная степень вершин в
Основанная на поле связей	Наиболее удобна для модификаций графа	Наибольшие запросы к памяти по сравнению со всеми рассмотренными схемами

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

Вопросы

1.