Методологические основы моделирования

Название	Методологические основы моделирования
Анкор	sobrannye_lektsii_1_2.docx
Дата	07.03.2018
Размер	2.94 Mb.
Формат файла
Имя файла	sobrannye_lektsii_1_2.docx
Тип	Лекция #16341
страница	6 из 19

1 2 3 4 5 6 7 8 9 ... 19

Матрицы смежности и перечисления путей

Напомним, что матрицей смежности А=||a_ij|| помеченного графа G(V,E) с n вершинами называется (nxn)- матрица, в которой а_ij =1 , если вершина v_iсмежна с вершиной v_j и а_ij=0 в противном случае.

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

$d:\рис.дис\рис51.bmp$
Рис.20. Граф с тремя компонентами и его блочная матрица смежности

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

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

Если использовать булеву алгебру, то элемент aⁿ_ij показывает, есть ли между вершинами v_i и v_j путь, длиной меньше или равной n ребер.

При этом о значении диагональных элементов матрицы договариваются заранее исходя из сущности решаемой задачи

	0	1	1	1		1	1	1	1
	1	0	1	0		1	1	1	1
А=	1	1	0	1	; А²₁=	1	1	1	1
	1	0	1	0		1	1	1	1

	0	1	0	0	0		1	0	1	0	0
	1	0	1	0	0		0	1	0	1	0
А₂=	0	1	0	1	0	; А²₂=	0	0	1	0	1
	0	0	1	0	1		0	1	0	1	0
	0	0	0	1	0		0	0	1	0	1

	0	1	0	1	0		1	0	1	0	1
	1	0	1	0	1		0	1	0	1	0
А³₂=	0	1	0	1	0	А⁴₂=	1	0	1	0	1
	1	0	1	0	1		0	1	0	1	0
	0	1	0	1	0		1	0	1	0	1

Графы G₁ и G₂, соответствующие матрицам смежности А₁ и А₂ приведены на рис.21; $d:\рис.дис\рис52.bmp$

Рис.21. Графы G_{1 ,}G₂ и G₃

Граф G₁ после возведения его матрицы смежности А₁ в квадрат становиться полносявзным, т.е. каждая его вершина связана со всеми остальными либо одним ребром в соответствии с матрицей А₁ , либо путем, состоящим из двух ребер в соответствии с матрицей А²₁ .

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

При возведении матрицы А₂ в квадрат в графе G₂ появляются дополнительные связи между вершинами v₁ иv₃(v₃и v₁), v₂ и v₄ (v₄и v₂ ), v₃ и v₅ ( v₅ и v₃) и граф G₂ принимает вид, как показано на рис.22;

$d:\рис.дис\рис53.bmp$

А)

; б)

; в)

; г)

Рис.22.Механизм появления новых связей при возведении в степень {2,3,4}матрицы А₂.
При возведении матрицы А³₂ = А²₂ х А₁ появляются новые пути из тех ребер, связывающие вершины v₁ иv₂ ; v₁ иv₄и.т.д произведя сложение матриц по правилам булевой алгебры, получим :

А_Σ = А₂U А²₂U А³₂U А⁴₂
0 1 1 1 1

1 0 1 1 1

А_Σ = 1 1 0 1 1

1 1 1 0 1

1 1 1 1 0
Граф, соответствующий этой матрице, без учета петель является полносвязным и показан на рис.22.

В матрицах А₂ со степенью меньше 4 элементы а₁₅= а₅₁= 0. Поэтому m = 4 является минимальной степенью, при возведении в которую элементы матрицы А^m_ содержат только положительные элементы.

В этом случае все вершины являются достижимыми из любой вершины путем, состоящим из не более чем m ребер (дуг) .

Граф G и соответствующая ему матрица смежности А называются примитивными, а m – индексом примитивности.

На рис.21 в граф G₃ не является примитивным, поскольку из его вершин 7 и 8 нет ребер , связывающих их с другими вершинами.

Для определения количества путей различной длины применяют возведение в степень матрицы смежности по правилам обычной алгебры .

Так, при возведении в квадрат матрицы А₁, соответствующей графу G₁ на рис.21а получим :

			0	1	1	1		0	1	1	1
			1	0	1	0		1	0	1	0
А²₁	=А₁	х А₁=	1	1	0	1	х	1	1	0	1
			1	0	1	0		1	0	1	0
	3	1	2	1
	1	2	1	2
=	2	1	3	1
	1	2	1	2

На главной диагонали стоят степени вершин .

Из вершины v₁в v₂есть один путь из двух ребер е₂ е₄ ; в вершину v₃ – два пути е₁ е₄ и е₃ е₅; в вершину v₄- е₂ е₅ .

Эти пути можно определить только визуально из графа, по матрице же можно определить только их количество.

Для перечисления путей применяют так называемые структурные матрицы и одну из равновидностей булевой алгебры.

Структурная матрица в определяется таким образом:
b_ij, если вершины v_i и v_j соединены ребрам и i < j

В = 1, если i = j

b_ij, если вершины v_i и v_j соединены ребром, но i>j

0 в остальных случаях

алгебра такова: 1 U 1 = 1 ; 1.0 = 0.1=0 ; 1 U 0 = 0 U 1=1

ā .а=0 ; а U а = а ;а Uав = а ; 1 U а =1

для графа G₁ рис 31а структурная матрица примет вид :

	1	а	в	С			1	aUb	bUadUcē	cUbe
	ā	1	d	0			ā Ud	1	dUāb	ācUe
В=	b		1	ē	;	B²=	вUaUce	Ua	1	eUbc
		0	ē	1			Uē	acUе	ēUc	1

Для удобства заполнения матрицы В² записываем i-ю строку, под ней j-й столбец и производим умножение строки на столбец по изложенным правилам.
1 а в с

В²₁₁= 1 ā

= 1*1U а* ā U в*

Uс *

= 1
1 а в с

В²₁₂= а 1

0= 1*aU а 1U в

U с 0 = aUв

1 а в с

В²₁₃= в d 1 ē = 1*вU а dU в Uс ē = вUаdU с ē
1 а в с

В²₁₄= с 0 е 1 = сU а 0UвеU с = сUве
Для того, чтобы перечислить одно, двух и трехзвенные пути, необходимо умножить матрицу В²хВ₁ т.е. В³= В²хВ.

Получим, например, первую стоку матрицы В³

В³₁₁=	1	аUb	bUadVc ē	cUbe
В³₁₁=	1	ā

= 1U ā b

U a

d UbceUcb ē = 1

В³₁₂=	1	аUb	bUadUc ē	cUbe
В³₁₂=	a	1		0

=a U a b

U b

c ē = a U b

U c ē

В³₁₃=	1	аUb	bUadUc ē	cUbe
В³₁₃=	b	d	1	ē

= b U ad U b U ad U c ē U c ē = b U ad U c ē

В³₁₄=	1	аUb	bUadUc ē	cUbe
В³₁₄=	c	0	e	1

= c UbeUade

В³₂₃=	ā Ud	1	b U ā b	c Ube
В³₂₃=	b	d	1

= ā b U d U ā

В³₂₄=	ā Ud	1	b U ā b	c Ube
В³₂₄=	c	0	e	1

= ā U c

d U de U ā be

В³₃₄=	U ā	U a	1	e Uc
В³₃₄=	c	0	e	1

c Uc ā

U e U

c
матрица В³ имеет вид:

1	a U b Uс е d	b UadU c ē	c UbeUade
ā U d	1	d U aU ā c ē	ā c U de U ā b c Ud
b UadU e	UabUa e	1	e Uc Uc a
U ē U ā ē	а c U d e Uа c Ub ē	e UUcad	1

Дальнейшее возведение в степень матрицы смежности не дает новых путей (только циклы), а алгоритм определения базисных циклов был рассмотрен ранее.

В каждой из клеток (n-1) степени структурной матрицы представлены все пути, ведущие из вершины v_i в вершину v_j. Каждую из клеток в связи с этим можно представить отдельной матрицей путей М_st строкам которой соответствуют пути, а столбцам –дуги, входящие в эти пути.

Например, для клетки 13 матрица путей примет вид:

		е₁	е₂	е₃	е₄	е₅
		a	b	c	d	e
	₁	0	1	0	0	0
М_st=	₂	1	0	0	1	0
	₃	0	0	1	0	1

^k₁₃ = ¹₁₃U²₁₃U³₁₃ = b U ad U c ē .

Перечисление путей М_st из произвольной вершины s в произвольную вершину t может быть получено из структурной матрицы В раскрытием определителя подматрицы В_ts, получаемого из структурной матрицы В вычергиванием s-го столбца и t –й строки:
М_st = detв_ts = | в_ts |

1 a b c a b c

в= a 1 d o ;в₁₃= 1 d o

b d 1 e o e 1

c o e 1

a b c

^k₁₃=|в₁₃| = 1 d O =а d OU b c UO = ad U b Ucе

o e 1 e 1 e 1
Для вершин v₁ и v₃таких независимых путей 3 – это b(e₂) Uad(e₁e₄) Uce(e₃e₅), для вершин v₂и v₃таких пути два :d(e₄) U a b (e₁e₂). Это является следствием того, что степень вершины d(V₄) = 2 , поэтому и число независимых путей в нее и из нее не может превышать этого числа.

И вообще число независимых путей из одной вершины в другую не может превышать минимальную степень одной из них.

В наших примерах :

d(v₁) = 3; d(v₂) = 2; d(v₃) = 3; поэтому между v₁ и v₃ может быть не более трех независимых путей, а между v₂ и v₃ не более двух .

В множестве путей М₂₃ пути ab и асе содержат общее ребро а, поэтому они не могут быть независимыми.

Множество путей между двумя произвольными вершинами связано с понятием “сечение”, которое является более общим случаем понятия “разрез”.

Напомним, что разрез – это минимальное число ребер, удаление которых разбивает граф на два связанных подграфа.

Сечением называется минимальное число ребер или вершин, удаление которых делает две вершины графа v_s и v_t несвязными.

Для того, чтобы сделать две вершины v_s и v_tнесвязными, нужно либо нарушить все пути М_st, связывающие эти вершины, либо хотя бы одно из сечений _st ε S_st , где S_st – множество сечений между вершинами v_s и v_t.

Между множеством путей М_st и множеством сечений S_st , а также множеством базисных разрезов существуют однозначные взаимосвязи.

Множество сечений S_st можно получить из дизъюнктивно-нормальной формы записи множества путей М_st , заменив знаки конъюнкции на знаки дизъюнкции и наоборот, используя булеву алгебру. Поскольку в булевой алгебре 1 U 1 = 1, то а.а = а; а U а = а; 1.а = а;

1 U а = 1; а(а U в) = а; а Uав = а; а. ā = 0; а U ā =1.

Например,

М₁₃ = b U ad Uce → S₁₃ = b.(a U d).(c U e).

Здесь U и (.) –знаки дизъюнкции и конъюнкции. Скобки удобнее раскрывать последовательно.

b(a U d) = (b a U b d)
( b a U b d )( cU e ) = a b c U b c d U a b e U b d e = S₁₃
Аналогично из перечисления сечений S_st можно получить выражение для перечисления множества путей М_st, произведя замену знаков дизъюнкций и конъюнкций. S₁₃ =a b c U b c d U a b e U b d e → М₁₃ = ( a U b U c).(b U c U d).(a U b U c ).(b U d U c).(a U b U c).(b U c U d)= abUadUacU b UcbUcdU c = (adU b U c) посколку a Uab = a такие пары скобок дает: (a U b U e)(b U d U e) = abUadUacU b UbdUbcUacUbcU e = adU b U e окончательно получим:

(adU b U c)(adU b U e) = ad UabdUabeUabdU b U be U cad Uce = b U ad Uce = М₁₃ .Запишем полученное множество сечений

в форме матрицы :

a e₁	b e₂	с e₃	d e₄	е e₅
1	1	1	0	0
0	1	1	1	0
1	1	0	0	1
0	1	0	1	1

Запишем также матрицу базисных разрезов относительно остовного дерева{e₁ , e₂ , e₃}, полученную ранее

	e₁	e₂	e₃	e₄	e₅
s₁	1	0	0	1	0
s₂	0	1	0	1	1
s₃	0	0	1	0	1

Из соотношения матриц сечений и базисных разрезов видно, что:

S¹₁₃ = S₁

S₂

S₃= S₄

S²₁₃ = S₂

S₃= S₅

S³₁₃ = S₁

S₂= S₆

S⁴₁₃ = S₂= S₂
Таким образом, каждое сечение является линейнной комбинацией базисных разрезов. Запишем полученные разрезы в одну матрицу.

	e₁	e₂	e₃	e₄	e₅
s₁	1	0	0	0	1
s₂	0	1	0	1	1
s₃	0	0	1	0	1
s₄	1	1	1	0	0
s₅	0	1	1	1	0
s₆	1	1	0	0	1

Как видно из графа G₁ на рис.21а, матрица охватывает все возможные разрезы этого графа.

Множество сечений S_st является подмножеством всех возможных сечений.

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

На основе логическной формы записи множества путей рассмотрен способ получения сечений и установлена взаимосвязь между множеством сечений и базисным множеством разрезов.

Как видно из графа G₁ на рис.1.21а, матрица охватывает все возможные разрезы этого графа.

Множество сечений S_st является подмножеством всех возможных сечений.

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

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

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

Весь предыдущий материал по теории графов является минимальной необходимой базой для исследования сетей связи, анализа заданных сетей и синтеза сетей с заданными свойствами.

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

При этом некоторые вершины и ребра могут быть особенными.

Так, вершина, удаление которой увеличивает число компонент графа называется точкой сочленения.

Ребро с аналогичным свойством называется мостом.

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

Блок графа- это его максимальный неразделимый подграф.

Полносвязный блок называют кликой.

1 2 3 4 5 6 7 8 9 ... 19

Методологические основы моделирования

Матрицы смежности и перечисления путей