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

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

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

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

В матрице инцидентности ориентированного графа G, если вершина v_j – начало ребра e_i, то v_j – конец e_i, то e_i – петля, а v_j – инцидентная ей вершина, (пример – табл. 2, б для графа рис. 1.4).

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

Таблица 2

а б

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

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

Таблица 3

а б

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

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

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

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

Таблица 4

а б

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

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

ПОТОКИ В СЕТЯХ

Понятие сети

Сетью будем называть ориентированный связный граф без петель и параллельных рёбер. Потоки в неориентированных графах можно изобразить в виде потоков в соответствующих ориентированных. Поток в петле не влияет на распределение потока между вершинами. Рассмотрим сеть G = (V, E), |V | = n, |E| = m. Пускай каждой дуге е_j E поставлено в соответствие неотрицательное действительное число с_j , которое назовём пропускной способностью дуги е_j. Обозначим через v_i → V множество дуг, выходящих из вершины v_i, через V → v_i – множество дуг, заходящих в вершину v_i.

Потоком в сети G из вершины v_s в вершину v_t величины w называется неотрицательная, определенная на дугах е_j, функция φ: Е → R₊ {0}, такая, что

– = (1)

φ(е_j) ≤ c_j, j = 1, …, m.

Вершина v_s называется источником, вершина v_t – стоком, а остальные вершины – промежуточными узлами. Число Q(v_i) = - называется чистым потоком из вершины v_i относительно φ. Число φ(е) называется потоком по дуге е. Если “реальный” поток по дуге отрицательный, то его можно сделать положительным, выбрав соответствующую ориентацию дуги e. Систему уравнений (1) можно переписать в векторном виде:

ВФ = l, (2)

где В – матрица инцидентной размерности n m, Ф = (φ(e₁) … φ(e_m))^T, l = (0..0w0..0 – w0..0)^T. Поскольку ранг матрицы инциденций равен n – 1, то система уравнений (1) избыточна: φ из v_s в v_t величины w есть поток величины -w из v_t в v_s.

Пример

Рис. 2.1. Поток величины 3

Сеть, изображённая на рис. 2.1, состоит из пяти узлов и восьми дуг. Будем рассматривать поток от v₁ до v₅. Каждой дуге приписаны два числа: первое – величина потока по дуге, второе – пропускная способность дуги. Величина этого потока равна 3. Действительно,

Q(v₁) = 5 - 2 = 3,

Q(v₂) = 7 – (5 + 2) = 0,

Q(v₃) = –4 – 0 +2 + 2 = 0, (3)

Q(v₄) = –4 + 4 = 0,

Q(v₅) = 4 + 0 – 7 = –3.

Систему уравнений (3) можно записать в векторном виде ВФ = l (2):