Мегаобучалка Главная | О нас | Обратная связь


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



2015-12-04 868 Обсуждений (0)
Представление графов с помощью матриц 0.00 из 5.00 0 оценок




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

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

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

В матрице инцидентности ориентированного графа G, если вершина vj – начало ребра ei, то vj – конец ei, то ei – петля, а vj – инцидентная ей вершина, (пример – табл. 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. Обозначим через vi → V множество дуг, выходящих из вершины vi, через V → vi – множество дуг, заходящих в вершину vi.

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

= (1)

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

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

ВФ = l, (2)

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

Пример

Рис. 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):



2015-12-04 868 Обсуждений (0)
Представление графов с помощью матриц 0.00 из 5.00 0 оценок









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

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ...
Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (868)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.009 сек.)