Дискретная математика: Учебное пособие. Часть 3 - Основы теории графов, страница 4

Элементы матрицы инциденции для ориентированного графа определяют по другой формуле:

          +1, если r_i,j исходит из   вершины x_i;

h_ij=     0, если r_i,j не инцидентна вершинам x_i и x_j;

-1, если дуга r_i,j заходит в вершину x_j.

В каждой строке сумма “+1” и “-1” равна нулю, т. к. “+1” представляет вершину – исток, а “-1” вершину – сток (см. табл. b) для графа на рис. 10).

В каждом столбце матрицы инциденции число “+1” равно полустепени исхода вершины x_i, т.е. d_i⁺, а число “-1” равно полустепени захода вершины x_i , т.е. d_i^-¾.

Матрица смежности. Поскольку смежность есть бинарное отношение между элементами одного множества, то матрица смежности ||r_i,j|| есть квадратная матрица, число строк и столбцов которой равно мощности множества |X|=n. Элементы матрицы смежности определяются соотношением:

                                        1, если x_i смежна x_j;

 r_i,j=  

0, в противном случае.

В табл. с) представлена матрица смежности для неориентированного графа (см. рис. 10). В каждой строке и в каждом столбце матрицы число “1” равно степени вершины, т.е. d_i. Поэтому можно выделить дополнительную строку или столбец для хранения информации о степени каждой вершины графа.