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

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

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

Определение.

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

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

x1

v1 x4 v2

x2

x3

v3

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

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

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

Т.е.

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

С помощью матриц смежности и инциндентности всегда можно полностью определеить граф и все его компоненты.

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

x4

x3

v2

x2 x5

x6

x1 v1 v3 x7 x8

x10

x11 x9

v4

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

Итого:

Построим теперь ориентированный граф с заданной матрицей смежности.

x4

x5

v2

x2 x7

х3 x6

x1 v1 х8 v3 x10 x11

х9

х17 х15 x14

x16 х13 x12

v4

Составим матрицу инцидентности для ориентированного графа.

Элемент матрицы равен 1, если точка является концом дуги, –1 – если началом дуги, если дуга является петлей, элемент матрицы запишем как ±1.

Таким образом, операции с графами можно свести к операциям с их матрицами.