Матричные представления графов.

Графы можно задавать не только аналитическим и графическим способом, но и с помощью матриц.

Определение. Матрицей смежности A_g = {a_ij) графа G = (X, U) называется квадратная матрица порядка n , элементы которой определяются зависимостью:

1, если в G существует дуга (i,j) (x_i ,x_j смежны)

0, если в G нет дуги (i,j) (x_i ,x_j не смежны)

Пример

u6

u4

u5

u3

u2

Матрица смежности полностью определяет структуру графа.

Например, сумма всех элементов строки X_i матрицы A_g дает полустепень исхода вершины X_i, a сумма элементов столбца Х_k - дает полустепень захода вершины Х_k - .

Определение. Матрица инциденций графа G = (X, U) (обозначается В = (b_ij) ) является матрица размерности m x n , элементы которой определяются следующим образом:

1, если Х_i является начальной вершиной дуги U_j,

bij=

-1, если X_i является конечной вершиной дуги U_j,

0, если Х_i не является вершиной дуги U_j,

2, если U_j является петлей.

	U1	U2	U3	U4	U5	U6
Bg = X1		-1
X2	-1
X3			-1	-1
X4					-1	-1

Поскольку каждая дуга инцидента двум различным вершинам за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент, равный 1, и один - равный - 1, либо все элементы столбца = 0.

Если G является неориентированным графом, то его матрица инциденций определяется также как и выше за исключением того, что все элементы, равные - 1 заменяется на + 1.

Аналитическое задание графа – перечень всех его вершин и дуг:

Пути и маршруты

(1)   (2) (3) (1)-(3)-пути

Путем(ориентированным маршрутом) орграфа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

Дуги U_k=(X_i,X_j) и U_l=(X_j,X_r), имеющие общие концевые вершины, называются смежными.

Две вершины X_i и X_j называются смежными, если какая-нибудь из двух дуг (X_i , Х_j) и (или) (X_j , X_i) одновременно присутствуют в графе. Например, дуги U₁,U₁₀ и U₃,U₆; вершины Х₃,Х₅, смежны.

Дуги U₁,U₈ и вершины Х₁,Х₄ не являются смежными.

Орцепьюназывают такой путь, в котором каждая дуга используется не более одного раза. Например, (1) и (2) - орцепь; (3) - не орцень, т.к. U₆, - дважды включена в путь.

Простой орцепью (элементарным путем)называют такой путь, в котором каждая вершина используется не более одного раза. (2) - простая орцепь, пути (1) и (3) - не простая орцепь.

Маршрутомназывают последовательность ребер U₁, U₂…U_n, в которой каждое ребро U_i, за исключением первого и последнего ребер, связано с ребрами U_i-1 и U_i+1 своими двумя концевыми вершинами. Различают простые и элементарные маршруты

Маршруты:

Черта над символом означает.

что ориентацией пренебрегают

Пример 3.1. Записать граф G = (X,U) аналитически, построить матрицы смежности, инциденций, пропускных способностей дуг и достижимостей. Определить экстремальные значения путей и маршрутов.

Решение.

1. Запишем граф G = (U, X) аналитически X = (Xi, Х₂, X₃, X₄, X₅. X₆)

U=( U₁=(X₁,X₂);U₂=(X₂,X₃);U₃=(X₂,X₄);U₄=(X₃,X₄);U₅=(X₅,X₄);

U₆ =(X₄,X₆);U₇=(X₆, X₅);U₈=(X₁, X₅);U₉=(X₅,X₅)), где X - множество вершин, a U - множество дуг.

2.Строим матрицу смежности А._g.

		X1	X2	X3	X4	X5	X6
	X1								2
	X2
A=	X3									α+=9
	X4
	X5
	X6
										α-=9

где α^- и α⁺ полустепени исхода и полустепени захода вершин Х_j соответственно.

3.Составляем матрицу инциденций В= { b_ik }. Матрица инциденций В

–это прямоугольная матрица размером m x n , где m – число вершин, n – количество дуг, элементы которой определяются:

1, если X_i является начальной вершиной дуги U_k

b_ik =, -1. если X_i является конечной вершиной дуги U_k

0, если X_i не является вершиной дуги Uk

2, если U_k является петлей.

		U1	U2	U3	U4	U5	U6	U7	U8	U9
	X1
	X2	-1
B=	X3		-1
	X4			-1	-1	-1
	X5							-1	-1
	X6						-1

3. Составляем матрицу пропускных способностей дуг С={c_ik}, которая строится на основе матрицы смежности A, заменяя элементы равные 1 соответствующим значением пропускной способности дуги.

4.

		X1	X2	X3	X4	X5	X6
	X1
	X2
C=	X3
	X4
	X5
	X6

5. Строим матрицу достижимостей D= {d_ik}, которая определяется следующим образом:

dik=

1, если вершина Х_k достижимы из X_i,

0, в противном случае

		X1	X2	X3	X4	X5	X6
	X1
	X2
D=	X3
	X4
	X5
	X6

6. Определяем пути их Х в Х , (без учета петли)

Сети

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

P(V)=P(W)=0

Наибольшее распространение среди множества сетей получила транспортная сеть, которая имеет только вход и выход. Каждой дуге такой сети соответствует целое число

C ( ν) ≥ 0, называемое пропускной способностью дуги ν (рис 2.8)

Рис.2.8

Поток сети - это некоторая функция ϕ (ν), удовлетворяющая условиям:

1)φ(ν) ≥ 0, (ν 󠅳 V);

2)φ(ν) ≤ С (ν);

3)∑ φ (ν) - ∑ φ (ν) = 0

ν V ν V

Это означает, что функция Ф (ν), где поток по дуге ν, есть целочисленное положительное число, которое не превышает пропускной способности данной дуги; сумма потоков, входящих в некоторую вершину (не являющуюся входом или выходом), равна сумме потоков, выходящих из этой вершины.

∑ φ(ν) - ∑ φ (ν) = Ф

ν V ν V

где ϕ - величина суммарного потока через вершину .

Для анализа пропускной способности сети используется понятие разрез сети. Все множества вершин можно разбить на взаимодополнительные подмножества А и В, такие что

1) A ≠B, A x и B x;

2) V A;

3) W B.

Следовательно, в подмножестве А содержится вход сети и некоторые промежуточные вершины. Подмножество В, содержит все остальные вершины и в том числе выход сети W.

Подмножество дуг , заходящих в В, называется разрезом сети, а сумм пропускных способностей этих двух составляет пропускную способностьразреза , или просто величину разреза.

С ( ) = ∑ C (ν), ν

Например, разрез Ӏ (рис. 2.8) определяется множеством верши

A = { }, B = { }, дуг = {( }

Пропускной способностью

C ( ) =

Поток φ (ν), проходящий по данной дуге не может превышать пропускную способность дуги С(ν), а, следовательно, его максимальная величина является φ (ν) = V(ν). В этом случае дуга называется насыщенной. Из всех разрезов сети можно выделить один, который обладает наименьшей пропускной способностью С ( , т.е. разрез минимальной величины.

Наибольшая величина потока не может быть более минимального разреза сети, т.е.

= С ( .

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

Ранги вершин проставляются по восходящей от входа к выходу сети так, что каждая последующая вершина имеет ранг восходящий по назначению, чем ранг всех предыдущих ее вершин.

Пример 3.2. определить величину максимального потока и указать минимальный разрез для сети (рис. 3.4.)

Рис. 3.4

Решение.

1. Составим матрицу пропускных способностей дуг для сети (рис.3.4)

		X1	X2	X3	X4	X5	X6
	X1
	X2
=	X3
	X4
	X5
	X6

Укажем один из путей из вершины в вершину . Например, , отмечаем значения соответствующих пропускных способностей дуг в матрице чертой над числами: . Определим минимальное из них, т.е. Величину вычитаем из чисел {6,5,10} в матрице , получим матрицу .

Рассмотрим второй путь из в , т.е. , отмечаем значения соответствующих пропускных способностей дуг в матрице чертой над числами: . Определим минимальное из них, т.е. = 1. Величину вычитаем из чисел {1, 3, 12} в матрице , получим матрицу .

Аналогично получаем остальные матрицы.

Указать путь из вершин больше нельзя. Составим матрицу , вычитая элементы матрицы из соответствующих элементов матрицы . Строим сеть (рис. 3.5.) на основании матрицы пропускных способностей дуг . величину максимального потока определим из условия:

сеть с максимальным потоком.

Рис. 3.5.

Минимальным разрезом является величина (рис.3.4)

Равновесие узлов проверяем на сети с максимальным потоком:

Поток входящий в каждый узел равен потоку, выходящему из него (равновесие узлов).