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

Поскольку граф можно рассматривать как графическое представление некоторого бинарного отношения, его можно задать той же булевой матрицей, которая задает данное отношение и описана в предыдущей главе. Эта матрица называется матрицей смежности графа. Строки и столбцы матрицы смежности соответствуют вершинам графа, а элемент ее на пересечении строки v_i и столбца v_j имеет значение 1 тогда и только тогда, когда вершины v_i и v_j смежны. В матрице смежности ориентированного графа этот элемент имеет значение 1, если и только если в данном графе имеется дуга с началом в вершине v_i и концом в вершине v_j. Графы, показанные на рис. 3.1, имеют следующие матрицы смежности:

, .

Нетрудно видеть, что матрица смежности неориентированного графа обладает симметрией относительно главной диагонали.

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

, .

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