4. Списки смежности

Данный способ представления графов в значительной степени лишен избыточности, присущей табличным представлениям.

Пусть G = (V, U)  некоторый граф, для которого

V = {v₁, ... , v_n} и U = {u₁, ... , u_k}.

Образуем два массива, которые обозначим как A и B.

Массив A состоит из n элементов, по одному для каждой вершины графа, а B  столько элементов, сколько существует концов различных ребер в G.

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

Для графа, изображенного на рис. 5.3., такие списки имеют вид:

Вершина	Список
a b c d e f	L(a) = f c b L(b) = d L(c) = e L(d) = d b f L(e) = L(f) = d

Здесь список L(e) является пустым.

Элементы списков L(v₁)L(v_n) последовательно записываются в массив B.

В первый, второй и последующие элементы массива A помещаются значения номеров элементов в B, которые являются в массиве B началами списков L(v₁), L(v₂) и т.д.

Если при этом некоторый список L(v_i) оказывается пустым, значение ссылки в элементе A(i) полагается равным 0. Такое представление графов является полным, поскольку в нем элементами массива A представлены все вершины, а массив B представляет все ребра графа. Множество ребер, выходящих из произвольной вершины v_i представлено своими концами в части массива B, начинающейся с элемента A(i) и заканчивающейся либо в элементе A(j) – 1, где j = min t ( t > i  A(t)  0), либо в последнем элементе массива B.

Для рассматриваемого графа массивы A и B имеют вид:

A 1 4 5 6 0 9

B f c b d e d b f d

Здесь с помощью стрелок изображены ссылки на элементы массива B, с которых начинаются вхождения списков L(v₁)  L(v_n).

5.3. Изоморфизм графов

Рассмотрим графы, изображенные на рис. 5.4.

a b 1 2

e f 3 4

G₂

g h 5 6

G₁ 7 8

c d

Рис. 5.4

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

Графы G₁ и G₂ называются изоморфными графами. Приведем точное определение понятия изоморфизма.