Матричные представления графов

Информация о структуре графа может быть задана матрицей смежности. Матрицей смежности графа G=(X,V), | X|=n называется квадратная матрица , элементы которой определяются следующим образом:

Замечание. Матрица смежности неориентированного графа симметрична. В случае кратных ребер a_ij есть количество ребер, соединяющих вершины x_i и x_j. Для орграфа а_ij определяется как количество дуг, направленных от вершины x_i к вершине x_j.

Теорема 4.3.1. Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одновременными перестановками строк и столбцов (т.е. одновременно с перестановкой i -й и j -й строк переставляются i -й и j -й столбцы).

Согласно этой теореме по матрице смежности граф восстанавливается однозначно с точностью до изоморфизма.

Матрицей инцидентности графа G=(X,V), |Х|=п,|V|=m называется матрица , элементы которой определяются следующим образом:

если G – ориентированный граф, то

 

если G - неориентированный граф, то

 

Замечание. Для ориентированного графа петлю, т. е. дугу вида (х_i, х_i) удобно представлять иным значением в строке х_i, например, 2.

 

Пример. Матричные представления графов проиллюстрированы на рис. 4.13, 4.14.

			(1,2)	(1,3)	(3,2)	(3,4)	(5,4)	(5,6)	(6,5)
			-1		-1
В =				-1
						-1	-1
									-1
								-1

 

			(1,2)	(1,3)	(1,5)	(2,3)	(2,5)	(3,4)	(4,5)	(4,6)	(5,6)
В =

 

Рис. 4.13:

а) ориентированный граф и его матрица инцидентности,

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

 

Рис. 4.14. Матрицы смежности для графов на рис. 4.13

Представление графов в ЭВМ

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

В теории графов классическим способом представления графа служит матрица инцидентности. Это матрица В с n строками, соответствующими вершинам, и т столбцами, соответствующими ребрам. С алгоритмической точки зрения матрица инцидентности является, вероятно, самым худшим способом представления графа, который только можно себе представить. Во-первых, он требует п´т ячеек памяти, причем большинство этих ячеек вообще занято нулями. Неудобен также доступ к информации. Ответ наэлементарные вопросы типа «существует ли дуга (x_i, x_j)?», «к каким вершинам ведут ребра из х_i ?»требует в худшем случае перебора всех столбцов матрицы, а следовательно, т шагов.

Лучшим способомпредставления графа является матрица смежности,определяемая как матрица А =(а_ij)размера n n. Здесь подразумевается, что ребро (x_i, x_j) неориентированного графа идет как от x_i к x_j, так и от x_j к х_i, так что матрица смежности такого графа всегда является симметричной. Это проиллюстрировано на рис. 4.14б.

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

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

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

 

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

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

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

 

Рис. 4.16. Списки инцидентности ЗАПИСЬ,

соответствующие графам на рис. 4.13

Операции над графами

 

Рассмотрим операции над графами.

I. Бинарные операции.

1. Объединение графов. Рассмотрим графы и . Объединение графов и , обозначаемое как , представляет собой такой граф , что множество его вершин является объединением и , а множество ребер – объединением и .

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

3. Кольцевой суммой графов G₁ и G₂ называется граф , где .

Замечание. Объединение, пересечение и другие операции над ориентированными графами определяются точно также, как и в случае неориентированных графов.

Пример. Для графов G₁ =({ x ₁, x ₂, x ₃}, {(x ₁, x ₂), (x ₂, x ₃)}) и G₂ =({ x ₁, x ₂, x ₄}, {(x ₁, x ₂), (x ₄, x ₁)}) (рис. 4.17) найдем , , . По определению имеем

=({ x ₁, x ₂, x ₃, x ₄},{(x ₁, x ₂), (x ₂, x ₃),(x ₄, x ₁)}),

=({ x ₁, x ₂}, {(x ₁, x ₂)}),

=({ x ₁, x ₂, x ₃, x ₄}, {(x ₂, x ₃), (x ₄, x ₁)}).

4. Соединением графов G₁ + G₂ называется граф {(x_i, x_j) | x_i Î X ₁, x_j Î X ₂, x_i ¹ x_j }).

Пример. Для графов G₁ и G₂, показанных на рис. 4.18 а, соединением G₁+G₂ является граф, представленным на рис. 4.18 б.

5. Произведением графов G ₁ и G ₂ называется граф , в котором ((x ₁, y ₁), (x ₂, y ₂))Î V тогда и только тогда, когда x ₁= x ₂ и (y ₁, y ₂)Î V ₂, или y ₁= y ₂ и (x ₁, x ₂)Î V _1.

Пример. На рис. 4.19 изображено произведение графов G ₁=({1, 2}, {(1, 1), (2, 1)}) и G ₂ = ({ a, b, c },{(a, b), (b, a), (b, c)}).

 

II. Унарные операции.

1. Удаление вершины. При удалении вершины из графа удаляются и все инцидентные ей ребра (дуги).Пусть – граф и . Удалить вершину x из графа G – это значит построить новый граф , в котором и получается из V удалением всех ребер, инцидентных вершине x. Пример удаления вершины x из графа:

До удаления вершины x После удаления вершины x

 

2. Удаление ребра (дуги). Пусть – граф и . Удалить ребро (дугу) v – это значит построить новый граф , в котором и . Вот иллюстрация удаления ребра графа:

 

До удаления ребра v. Послеудаления ребра v

При удалении ребра (дуги) его концевые вершины не удаляются. Операцией, являющейся обратной к удалению ребра, является добавление ребра.

3. Слияние или отождествление вершин. Говорят, что вершины и в графе G отождествляются (сливаются), если они заменяются такой новой вершиной , что все ребра (дуги) графа, инцидентные и , становятся инцидентными новой вершине .

4. Стягивание ребра (дуги). Эта операция означает удаление ребра и отождествление его концевых вершин. Граф G ₁ называется стягиваемым к графу G ₂, если граф G ₂ может быть получен из G ₁ в результате некоторой последовательности стягиваний ребер.

Пример. Из графа G, показанного на рис. 4.20, добавлением вершины 5 образуется граф G₁, добавлением дуги (3,1) – граф G₂, удалением дуги (3,2) – граф G₃, удалением вершины 2 – граф G₄, отождествлением вершин 1 и 4 – граф G₅, стягиванием дуги (2,3) – граф G₆.

 

 

5. Подразбиение ребра. Пусть – граф и . Выполнить подразбиение ребра v – это значит построить новый граф , в котором (т.е. z – некая новая вершина) и . С графической точки зрения эта операция означает «внесение в ребро новой вершины». Вот графическая иллюстрация:

 

xx

z

 

yy

До внесения вершины z После внесения вершины z

Граф называется дополнением простого графа, если ребро (x_i, x_j) входит в в том и только в том случае, если оно не входит в V. Другими словами, две вершины смежны в тогда и только тогда, когда они не смежны в G.

Пусть G’ =(X’, V’) является подграфом графа G =(X, V). Подграф G’’ =(X, V \ V’) графа G называется дополнением графа G’ в графе G.

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: