Представление графов с помощью матриц

1.5.1. Матрицы инцидентности и списки рёбер

Задать граф, значит, задать множество его вершин и рёбер, а также отношение инцидентности. Когда граф G – конечный, для описания его вершин и рёбер достаточно их занумеровать. Пускай v₁, v₂,…, v_n – вершины графа G; e₁, e₂,…, e_m – его рёбра. Отношение инцидентности можно обозначить матрицей , которая имеет m строк и n столбцов. Столбцы соответствуют вершинам графа, а строки – его рёбрам. Если ребро е_і является инцидентным вершине v_j, то , в другом случае . Это матрица инцидентности обычного графа G, являющаяся одним из способов его определения (для графа на рис. 1.5.1), она задана в табл. 2, а.

Рис. 1.5.1 Обычный граф

В матрице инцидентности ориентированного графа G, если вершина v_j – начало ребра e_i, то ; если v_j – конец e_i, то ; если e_i – петля, а v_j – инцидентная ей вершина, , где α – любое число, отличное от 1, 0 и –1, в других случаях (пример – табл. 2, б для графа рис. 1.5.2).

Рис. 1.5.2 Ориентированный граф

Таблица 2

а б

В каждой строке матрицы инцидентности для неориентированного или ориентированного графа только два элемента отличны от нуля (или один, если ребро является петлёй). Потому такой способ задания графа не достаточно экономный. Отношение инцидентности можно задать ещё списком рёбер графа. Каждая строка этого списка соответствует ребру, в нём записаны номера вершин, инцидентных ему. Для неориентированного графа порядок этих вершин в строке произвольный, для ориентированного первым записывается номер или другое наименование начала ребра, а другим – его конца. В таблице 3, а и б приведены списки рёбер для графов, изображённых на рис. 1.5.1 и 1.5.2.

По списку рёбер графа можно легко определить матрицу инцидентности. Действительно, каждая строка этого списка соответствует строке матрицы с тем же номером. Для неориентированного графа в строке списка записываются номера элементов строки матрицы инцидентности, которые равняются 1, а для ориентированного графа в этой строке первым записывается номер элемента строки матрицы, который равен -1, вторым – номер элемента, который равен 1.

Таблица 3

а б

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

Матрица смежности графа – это квадратная матрица , столбцам и строкам которой соответствуют вершины графа. Для неориентированного графа δ_ij равняется количеству рёбер, инцидентных i -й та j -й вершинам, для ориентированного графа этот элемент матрицы смежности соответствует количеству рёбер с началом в і -й вершине и концом в j -й. Таким образом, матрица смежности неориентированного графа симметрична (δ_ij = δ_ji), а ориентированного – необязательно. Если она всё-таки симметрична, то для каждого ребра ориентированного графа существует ребро, которое соединяет те же вершины, но направлено в противоположную сторону. Очевидно, ориентированный граф с симметричной матрицей смежности канонично соответствует неориентированному графу, который имеет ту же матрицу смежности.

Матрицы смежности рассмотренных выше графов (см. рис. 1.5.1 и 1.5.2) приведены в таблице 4.

Матрица смежности полностью определяет соответствующий неориентированный или ориентированный граф. Число его вершин равняется размерности матрицы n, i -й и j -й вершинам графа инцидентны ребер. Для неориентированного графа , и все его ребра определяются верхним правим треугольником матрицы, расположенным над диагональю, включая последнюю.

Таблица 4

а б

Количество их равняется сумме в этом треугольнике, то есть . Рёбра ориентированного графа определяются всеми элементами матрицы смежности. В обоих случаях с помощью матрицы смежности легко строится, например, список ребер, который определяет граф. Элементу матрицы смежности, расположенном в і -й строке и j -м столбце, соответствует строк списка ребер (при =0 нет ни одной строки), в каждом из которых записываются номера і, j. Для неориентированного графа эти строки соответствуют только элементам названного выше верхнего правого треугольника матрицы смежности, то есть элементам с , а для ориентированного графа нужно рассматривать все элементы .

Итак, граф можно представить разными способами. Он может быть изображён на рисунке, задан матрицей инцидентности, списком рёбер или матрицей смежности. Графический вид зависит от формы линий и взаимного расположения вершин. Вид матриц и списка рёбер зависит от нумерации вершин и рёбер графа.

Дата добавления: 2015-08-09