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

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

Задать граф, значит, задать множество его вершин и рёбер, а также отношение инцидентности. Когда граф G – конечный, для описания его вершин и рёбер достаточно их занумеровать. Пускай v1, v2,…, vn – вершины графа G; e1, e2,…, em – его рёбра. Отношение инцидентности можно обозначить матрицей Представление графов с помощью матриц - student2.ru m строк и n столбцов. Столбцы соответствуют вершинам графа, а строки – его рёбрам. Если ребро еі является инцидентным вершине vj, то Представление графов с помощью матриц - student2.ru Представление графов с помощью матриц - student2.ru G, являющаяся одним из способов его определения (для графа на рис. 1.3), она задана в табл. 2, а.

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

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

В матрице инцидентности Представление графов с помощью матриц - student2.ru ориентированного графа G, если вершина vj – начало ребра ei, то Представление графов с помощью матриц - student2.ru vj – конец ei, то Представление графов с помощью матриц - student2.ru ei – петля, а vj – инцидентная ей вершина, Представление графов с помощью матриц - student2.ru Представление графов с помощью матриц - student2.ru (пример – табл. 2, б для графа рис. 1.4).

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

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


Таблица 2

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


а б

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

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

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


Таблица 3

а б

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

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

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

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

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


Таблица 4

а б

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

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


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

Понятие сети

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

Потоком в сети G из вершины vs в вершину vt величины w называется неотрицательная, определенная на дугах еj, функция φ: Е → R+ Представление графов с помощью матриц - student2.ru {0}, такая, что

Представление графов с помощью матриц - student2.ruПредставление графов с помощью матриц - student2.ru = Представление графов с помощью матриц - student2.ru (1)

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

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

ВФ = l, (2)

где В – матрица инцидентной размерности n Представление графов с помощью матриц - student2.ru m, Ф = (φ(e1) … φ(em))T, l = (0..0w0..0 – w0..0)T. Поскольку ранг матрицы инциденций равен n – 1, то система уравнений (1) избыточна: Представление графов с помощью матриц - student2.ru φ из vs в vt величины w есть поток величины -w из vt в vs.

Пример

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

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

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

Q(v1) = 5 - 2 = 3,

Q(v2) = 7 – (5 + 2) = 0,

Q(v3) = –4 – 0 +2 + 2 = 0, (3)

Q(v4) = –4 + 4 = 0,

Q(v5) = 4 + 0 – 7 = –3.

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

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

Наши рекомендации