lecture_04

Матрица смежности

Матрица смежности – это двумерный массив размером n n:

	8	0;	если вершина i не смежна вершине j;
Graf[i; j] =		вес ребра (дуги);	если вершина i смежна вершине j;
	<	вес вершины;	если i = j.
	:

Козлов Александр Иванович	Институт программных систем
Структура графов

Матрица смежности

Матрица смежности – это двумерный массив размером n n:

	8	0;	если вершина i не смежна вершине j;
Graf[i; j] =		вес ребра (дуги);	если вершина i смежна вершине j;
	<	вес вершины;	если i = j.
	:

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

Козлов Александр Иванович	Институт программных систем
Структура графов

Матрица смежности

Теорема 1. Если A – матрица смежности графа G, то матрица Am обладает следующим свойством: элемент в i-й строке, j-м столбце равен числу путей из i-й вершины в j-ю, состоящих из ровно m ребер.

Размер занимаемой памяти: O(jV j2)

Козлов Александр Иванович	Институт программных систем
Структура графов

Матрица инцидентности

Матрица инцидентности – это двумерный массив размером n m:

Graf[i; j] =	0;	если вершина i не инц. ребру j;
	вес ребра (дуги в i);	если вершина i инц. ребру j.

Козлов Александр Иванович	Институт программных систем
Структура графов

Матрица инцидентности

Матрица инцидентности – это двумерный массив размером n m:

Graf[i; j] =	0;	если вершина i не инц. ребру j;
	вес ребра (дуги в i);	если вершина i инц. ребру j.

Матрица инцидентности лучше всего подходит для операции ¾перечисление ребер, инцидентных вершине v¿.

Козлов Александр Иванович	Институт программных систем
Структура графов

Матрица инцидентности для ориентированного графа

8

1; если ребро (i; j);

<

Graf[i; j] = 1; если ребро (j; i);

: 0; во всех остальных случаях.

Козлов Александр Иванович	Институт программных систем
Структура графов

Матрица инцидентности для ориентированного графа

8

1; если ребро (i; j);

<

Graf[i; j] = 1; если ребро (j; i);

: 0; во всех остальных случаях.

Размер занимаемой памяти: O(jV jjEj).

Козлов Александр Иванович	Институт программных систем
Структура графов

Список ребер

Список, где каждому ребру графа соответствует строка, в которой хранятся две вершины, инцидентные ребру

Козлов Александр Иванович	Институт программных систем
Структура графов

Список ребер

Список, где каждому ребру графа соответствует строка, в которой хранятся две вершины, инцидентные ребру

Размер занимаемой памяти: O(jEj). Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными. Этот способ хранения графа особенно удобен, если главная операция, которая чаще всего выполняется, это перечисление ребер или нахождение вершин и ребер, находящихся в отношениях инцидентности.

Козлов Александр Иванович	Институт программных систем
Структура графов

Структура смежности графа

Структура смежности графа состоит из списков вершин графа, смежных с каждой вершиной.

Козлов Александр Иванович	Институт программных систем
Структура графов