Материал: Методические указания к выполнению лабораторных работ по дисциплине «Дискретная математика» для студентов направления подготовки бакалавров. Собенина О.В., Пак А.А

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

Более экономным в отношении памяти (особенно в случае неплотных графов, когда т гораздо меньше n2) является метод представления графа с помощью списка пар, соответствующих его ребрам. Пара (х, у) соответствует дуге (х,у), если граф ориентированный, и ребру (х, у) в случае неориентированного графа (рис. 4). Очевидно, что объем памяти в этом случае составляет 2m. Неудобством является большое число шагов – порядка т в худшем случае, – необходимое для получения множества вершин, к которым ведут ребра из данной вершины.

Рис. 4. Списки ребер, соответствующие графам на рис. 2

Ситуацию можно значительно улучшить, упорядочив множество пар лексикографически и применяя двоичный поиск, но лучшим решением во многих случаях оказывается структура данных, которую называют списками инцидентности. Она содержит для каждой вершины v V список вершин и, таких что v u (или v – и в случае неориентированного

25

графа). Точнее, каждый элемент такого списка является записью r, содержащей вершину r.строка и указатель r.след на следующую запись в списке (r.след=nil для последней записи в списке). Начало каждого списка хранится в таблице НАЧАЛО; точнее, НАЧАЛО[v] является указателем на начало списка, содержащего вершины из множества (u: v u) ((и: v – и) для неориентированного графа). Весь такой список обычно неформально будем обозначать ЗАПИСЬ[v], а цикл, выполняющий определенную операцию для каждого элемента и из этого списка в произвольной, но четко установленной последовательности, соответствующей очередности элементов в списке, будем записывать «fог и ЗАПИСЬ[v] do ...».

Отметим, что для неориентированных графов каждое, ребро (и, v) представлено дважды: через вершину v в списке ЗАПИСЬ[и] и через вершину и в списке ЗАПИСЬ[v]. Во многих алгоритмах структура графа динамически модифицируется добавлением и удалением ребер. Каждый элемент списка может содержать указатель не только к следующему элементу, но и к предыдущему.

Число ячеек памяти, необходимое для представления графа с помощью списков инцидентности, будет, очевидно, иметь порядок т+n. На рис. 5 представлены списки инцидентности, соответствующие графам на рис. 2.

Рис. 5. Списки инцидентности ЗАПИСЬ, соответствующие графам на рис. 2

26

Алгоритмы 1. Алгоритм построения простого графа,

имеющего заданную последовательность степеней

Шаг 1. {d1 , ... ,dn }- последовательность степеней, упорядоченная по невозрастанию. Выберем произвольное dk. 0 и "изымем" dk из последовательности, соединяя вершину хk с первыми dk вершинами, не считая саму вершину хk.

Шаг 2. Упорядочим остаточную последовательность в порядке невозрастания.

Шаг 3. Шаги 1-2 выполнять до тех пор, пока не возникнет одна из следующих ситуаций:

а) все остаточные степени равны 0. В этом случае последовательность степеней является графической. Искомый граф получается в результате выполнения шагов, соответствующих порядку изъятия степеней; б) одна из остаточных степеней отрицательна - это означает, что последовательность {d1,... ,dn} не является графической, т. е. не существует простого графа, который ее реализует.

2. Алгоритм проверки связности неорграфа

Шаг 1. G = (X, U) - данный неорграф. Для произвольной вершины x0 найти множество R(xo). Перейти к шагу 2.

Шаг 2. Если R(x0 )= X , то граф является связным, иначе

граф не является связным. Выдать соответствующее сообщение. Останов.

27

3. Алгоритм нахождения сильных компонент графа

Шаг 1. G = ( X, U ) - данный граф. Определение сильных компонент графа ( СК ) начать с произвольной вер-

для произвольной вершины xk X найти СК(xi ) на X . Пе-

рейти к шагу 3.

Шаг 3. Если X 0, то перейти к шагу 2, иначе останов, так как все сильные компоненты определены.

Вопросы для самопроверки

1.Какие способы задания и представления графов знаете?

2.Какие бинарные операции над графами знаете?

3.Какие унарные операции над графами знаете?

4.Дать определение конденсации графа?

5.Что такое подграф?

6.Какой граф является дополнением полного графа?

7.Что представляет собой степень вершины?

8.Как определяется матрица смежности графа ?

9.Как определяется матрица инцидентности графа ?

10.Как построить матрицу достижимостей графа ?

11.Дать определение сильной компоненты графа.

12.Дать определение связного графа.

28