Глава 26. Представление графов

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

Представление графа с помощью квадратной булевской матрицы размером P´P, отражающей смежность вершин, называется Матрицей смежности, Где

Матрица инциденций

Представление графа с помощью матрицы Н Размером P´Q, отражающей инцидентность вершин и ребер, называется Матрицей инциденций, Где для неориентированного графа

А для ориентированного графа

Граф можно задать также посредством Списков:

1) Списком пар вершин, соединенных ребрами (или дугами).

2) Списком списков для каждой вершины множества смежных с ней вершин.

Пример

Пусть даны два графа. Неориентированный граф показан на рисунке 6.2,А, ориентированный – на рисунке 6.2,Б. Построим матрицы смежности, матрицы инцидентности, списки пар вершин и списки списков для данных графов.

Матрица смежности неориентированного графа:

.

Матрица смежности ориентированного графа:

.

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

.

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

Список пар вершин неориентированного графа: ({1,2}, {1,4}, {2,4}, {3,4}).

Список пар вершин ориентированного графа: ((1,2), (1,4), (4,2), (3,4)).

Список списков неориентированного графа: ((2,4), (1,4), (4), (1,2,3)).

Список списков ориентированного графа: ((2,4), Æ, (4), (2)).

< Предыдущая		Следующая >