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

Очень часто граф представляется в виде матрицы смежности А_n*n, в которой а_ij=1, если (v_i,v_j) принадлежит Е, а_ij=0 в противном случае.

Для простых неориентированных графов матрица смежности симметрична, т.е. A_ij=a_ji. В случае взвешенного графа полагается a_ij=w_ij где w_ij — вес ребра.

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

Используя матрицу смежности, можно определить все пути между вершинами v_i и v_j и их длины, определить все возможные пути, циклы, простые и элементарные пути и т.п.

Рассмотрим представление орграфа G₁ и неориентированного графа G₂ в виде матриц смежности. СМ рисунок.

Если в графе ребер (дуг) много, то такое представление достаточно компактное, в противном случае получается разреженная матрица.

При разработке программ, предназначенных для работы с графами, необходимо контролировать правильность задания параметров графа. Естественно, при числе вершин графа, меньших 2, не приходится говорить о матрице смежности. Если m — число вершин графа и n — число дуг, очевидными являются требования: m≥2, n≥1 и n≤m*(m - 1) для ориентированного или n≤m*(m - 1)/2 для неориентированного графа. Здесь учитывается тот факт, что в ориентированном графе вершины могут быть соединены прямыми и обратными дугами.

Риc. Ориентированный (G\) и неориентированный (G2) графы -,G2 G1

Рис. Матрицы смежности ориентированного (Gi) и неориентированного (G2) графов