_112. Матрицы графов

Пусть D = (V, X) – орграф, где V = {v1, …, vn}, X = {x1, … , xm}.

Определение. Матрицей смежности орграфа D называется квадратичная матрица A(D) = [aij] порядка П, у которой

Определение. Если вершина V является крнцом ребра Х, то говорят, что V и Х – инциндентны.

Определение. Матрицей инциндентности оргафа D называется матрица размерности П´Т B(D) = [bij], у которой

Пример. Записать матрицы смежности и инцидентности для графа, изображенного на рисунке.

V1 X4 V2

Составим матрицу смежности:

	V1	V2	V3
V1	0	1	0
V2	1	0	1
V3	1	0	0

Т. е. - матрица смежности.

Матрица инциндентности:

	X1	X2	X3	X4
V1	-1	0	1	1
V2	1	-1	0	-1
V3	0	1	-1	0

Т. е.

Если граф имеет кратные дуги (ребра), то в матрице смежности принимается Aij=K, где K – кратность дуги (ребра).

С помощью матриц смежности и инциндентности всегда можно полностью определеить граф и все его компоненты. Такой метод задания графов очень удобен для обработки данных на ЭВМ.

Пример. Задана симметрическая матрица Q неотрицательных чисел. Нарисовать на плоскости граф G(V, X), имеющий заданную матицу Q своей матрицей смежности. Найти матрицу инциндентности R графа G. Нарисованть также орграф , имеющий матрицу смежности Q, определить его матрицу инциндентности С.