§ 2. Обобщения понятия графа

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

Определение: пара множеств G = <V,E> называется ориентированным графом (орграфом), если V – конечное, непустое множество вершин, а Е – множество упорядоченных пар (A, B) элементов из V. Ориентированное ребро (A, B) будем называть дугой с началом A и концом B. На рисунке дуги изображаются стрелками (рис 2.1).

Определение: пара множеств G = <V,E>, где V – конечное, непустое множество вершин, а Е содержит «параллельные» рёбра (т.е. вершины могут соединяться более чем одним ребром) называется мультиграфом (рис. 2.2).

Определение: пара множеств G = <V,E>, где V – конечное, непустое множество вершин, а Е – множество ребер, содержащее петли, т.е. ребра, соединяющие вершину саму с собой, называется псевдографом (рис. 2.3).

Псевдограф на рис. 2.3 содержит 2 петли e₁ и e₂.

Определение: пара множеств G = <V,E>, где V – конечное, непустое множество вершин, а Е – множество рёбер, состоящих из произвольных подмножеств множества V, называется гиперграфом (рис. 2.4).

На рисунке 2.4 изображен гиперграф с тремя ребрами: e₁= (1,2), e₂= (3,4) и e₃= (4, 5, 6).

§ 3. Представление графов в памяти компьютера

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

В теории графов классическим способом представления помеченного графа порядка n служит матрица смежности А = (a_ij) размера nn, где a_ij =1, если существует ребро (i,j) и a_ij =0 в противном случае (рис. 3.1)

Аналогично определяется матрица смежности для ориентированного графа:

Матрица смежности графа симметрична относительно главной диагонали (для орграфа это свойство матрицы обычно не выполняется).

Основным преимуществом представления графа матрицей смежности является тот факт, что за один шаг можно получить ответ на вопрос: Не существует ли ребро из i в j?. Недостатком же является тот факт, что независимо от числа ребер объем занятой памяти составляет n² ячеек, что в настоящее время совершенно неважно.

Более экономным в отношении памяти ( в случае m  n²) является представление графа списком ребер  массивом B пар вершин, соответствующих его ребрам (рис. 3.3).

Очевидно, объем памяти в этом случае составляет 2m ячеек. Недостатком является большое число шагов  порядка m в худшем случае  необходимое для получения ответа на вопрос, существует ли ребро (i,j).

Лучшим решением во многих случаях оказывается структура данных, которая называется списками смежностей  массив динамических списков вершин смежных для каждой вершины графа (рис.3.4).

Для неориентированных графов каждое ребро (i,j) представлено дважды: через вершину j в списке со ссылкой i и через вершину i в списке со ссылкой j.