Матричные представления графа
Одной из форм математического представления графа является его представление в виде матриц смежности и инциденций.
Вершины 
и 
являются смежными, если они различны и если существует дуга, идущая из в .
Дугу u называют инцидентной вершине , если она заходит в эту вершину или исходит из нее.
Матрицей смежности R= 
графа 
называется квадратная матрица порядка n (n – число вершин графа), элементы которой ri,j (i=1, 2, …n; j=1,2, …n) определяются следующим образом:
2.6
Матрица смежности полностью определяет структуру графа. Возведем матрицу смежности в квадрат. Элемент 
матрицы R2 определяется по формуле:
2.7
Слагаемое 
тогда и только тогда, когда 
и 
, в противном случае слагаемое 
. Так как из равенства 
следует существование пути длины два (пути, проходящего через две дуги) из вершины в вершину , проходящего через вершину 
, то равно числу путей длины два, идущих из в через .
Если 
является элементом матрицы 
, то 
¹0 равно числу путей длины p, идущих из в .
Пример. На рис. 2.4 задан граф G. построить матрицу смежности и выяснить, сколько путей длины три существует в графе G.
Рис. 2.4
Решение.
Элемент 
, следовательно в данном графе существует единственный путь длиной три – это путь из вершины х1 в вершину х4: (х1 , x2), ( x2, x3 ), (x3, x4)
Все элементы матрицы 
равны нулю. Следовательно, в графе отсутствуют пути длиной четыре.
Матрицей инциденций 
называется прямоугольная матрица размерности n´m (n-число вершин, m – число дуг), элементы которой 
определяются следующим образом:
2.8
Если граф G не содержит петель, то каждый столбец матрицы S содержит единственный элемент, равный 1 (дуга имеет начало) и единственный элемент, равный –1 (дуга имеет конец), а остальные элементы равны нулю.
Пример. Построить матрицу смежности и матрицу инциденций для графа, приведенного на рис. 2.5.
 |
Матрица инциденций будет иметь вид:
| xi /uj | u1 | u2 | u3 | u4 | u5 | u6 | u7 | u8 | u9 |
| x1 | -1 | ||||||||
| x2 | -1 | -1 | |||||||
| x3 | -1 | -1 | |||||||
| x4 | -1 | -1 | |||||||
| x5 | -1 |
Или в более компактной форме матрица смежности R и инциденций S будут иметь вид:
; 
.