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

Мы определили ребро Е графа G как элемент в произведении V ´ V. Как обычно, это произведение можно представить в виде таблицы:

V V		А
B		(А, B)

Элемент (А, B) таблицы соответствует ориентированному ребру (А, B). Мы помещаем в соответствующую клетку таблицы 0 или 1 в зависимости от того, присутствует в графе G соответствующее ребро или нет.

Таким образом, мы получили конечную или бесконечную матрицу смежности вершин М(G), которая полностью описывает граф G, если он имеет лишь однократные ребра. На главной диагонали матрицы располагаются элементы, соответствующие петлям (А, А).

Если G – неориентированный граф, то (А, B) = (B, А) и ему соответствует матрица смежности, симметричная относительно главной диагонали.

Если G имеет кратные ребра, то числа 1 или 0 в соответствующих клетках можно заменить числами 2, 3 и т. д., выражающими кратность соответствующих ребер. Это дает описание графа G матрицей с целыми неотрицательными элементами. И наоборот, любая такая матрица может быть интерпретирована как граф. Пример: для графа составить матрицу и наоборот.

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

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

Графы могут быть описаны также матрицами другого вида. Можно построить матрицу, строки которой соответствуют вершинам, а столбцы – ребрам.

В клетку (А, Е) мы поместим 1, если А – начальная вершина ребра Е, а в клетку (B, Е) поместим –1, если вершина B – конечная вершина ребра Е. Если вершина неинцидентна ребру, то в соответствующие клетки ставят 0. Эта матрица называется Матрицей инцидентности графа G.

E V	E1	E2	E3
A1	1
A2	0
A3	-1
A4	0

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