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

Пусть D=(V,X) ориентированный граф, V={v₁,...,v_n}, X={x₁,...,x_m}.

Матрица смежности ориентированного графа D − квадратная матрица

A(D)=[a_ij] порядка n, где

Матрица инцидентности − матрица B(D)=[b_ij] порядка n´m, где

Матрицей смежности неориентированного графа G=(V,X) называется квадратная симметричная матрица A(G)=[a_ij] порядка n, где

                                        .

Матрица инцидентности графа G называется матрица B(G)=[b_ij] порядка n´m, где

Связность. Компоненты связности

Подграфом графа G (ориентированного графа D) называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G (D).

Подграф называется собственным, если он отличен от самого графа.

Говорят, что вершина w ориентированного графа D (графа G) достижима из вершины v, если либо w=v, либо существует путь (маршрут) из v в w.

Граф (ориентированный граф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.

Компонентой связности графа G (сильной связности ориентированного графа D) называется его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (ориентированного графа D).

Матрицы достижимости и связности

Пусть A(D) – матрица смежности ориентированного псевдографа D=(V,X) (или псевдографа G=(V,X)), где V={v₁,…, v_n}. Обозначим через A^k=[a^(k)_ij] k-ю степень матрицы смежности A(D).

Элемент a^(k)_ij матрицы A^k ориентированного псевдографа D=(V,X) (псевдографа G=(V,X)) равен числу всех путей (маршрутов) длины k из v_i в v_j.

Матрица достижимости ориентированного графа D − квадратная матрица T(D)=[t_ij] порядка n, элементы которой равны

Матрица сильной связности ориентированного графа D − квадратная матрица S(D)=[s_ij] порядка n, элементы которой равны

Матрица связности графа G − квадратная матрица S(G)=[s_ij] порядка n, элементы которой равны

Пусть G=(V,X) – граф, V={v₁,…, v_n}, A(G) – его матрица смежности. Тогда

S(G)=sign[E+A+A²+A³+… A^n-1] (E- единичная матрица порядка n).

Утверждение 3. Пусть D=(V,X) – ориентированный граф, V={v₁,…, v_n}, A(D) – его матрица смежности. Тогда

1) T(D)=sign[E+A+A²+A³+… A^n-1],

2) S(D)=T(D)&T^T(D) (T^T-транспонированная матрица, &- поэлементное умножение).

Расстояния в графе

Пусть - граф (или псевдограф). Расстоянием между вершинами  называется минимальная длина пути между ними, при этом , , если не  пути.

Расстояние в графе удовлетворяют аксиомам метрики

1) ,

2)  (не в ориентированном графе)

3)

4)  в связном графе (не в ориентированном графе).

Пусть  связный граф (или псевдограф).

Диаметром графа G называется величина .

Пусть .

Максимальным удалением (эксцентриситетом) в графе G от вершины  называется величина .

Радиусом графа G называется величина

Центром графа G называется любая вершина  такая, что .