Методологические основы моделирования
 Скачать 2.94 Mb.
|
2.Матрица разрезов и ее связь с матрицей цикловВ матрице разрезов S столбцы соответствуют ребрам, строки разрезам . Если ребро входит в разрез , то элемент матрицы равен 1, если нет, то 0. Для рассматриваемого графа разрезы сведены матрицу.
Разрезы S1 , S2 , S3 являются базисными , остальные их- линейными комбинациями : S4 = S1 S2 S3 S5 = S1 S2 S6 = S2 S3 Строки матрицы S называются векторами разрезов. Ранг матрицы разрезов равен n-1 , в нашем случае =n-1= 4-1=3 . Представим матрицу базисных разрезающих множеств относительно остовного дерева, им соответствующего. Остовное дерево, как и для базисных циклов, состоит из ребер е1, е2 , е3. e1 e2 e3 e4 e5 s11 0 0 1 0 Sf =s2 0 1 0 1 1 или Sf = ( I | Sfc) s3 0 0 1 0 1 где I- единичная матрица, включающая ветви дерева, относительно которого определяются базовые разрезающие множества, а Sfc – матрица, включающая хорды, которые входят в разрез, они же являются основой базисных циклов, полученных по отношению к этому же остовному дереву. Рассмотрим, как из матрицы разрезов получить матрицу циклов. Расположим номера ребер также, как и в матрице базисных циклов, тогда получим :
S11 I Представим S в виде двух блочных матриц т.е. S= S11| I . Из соотношения ортогональности, которое, существует между матрицей циклов и транспонированной матрицей разрезов, имеем (I | C12)( S′11 | I ) = 0 для нашего случая : 110 10110 011 000 ( I | C12) ( S′11 | I ) = 01011 100 = 000 = 0 . 010 001 Следовательно,IS′11 + C12I =0 , откудаS′11= C12 , т.к.-1Ξ 1 мод 2. 110 S′11= 011 = C12 10 присоединив слева матрицу : I = 10 , получим матрицу базисных циклов 10110 Сf =I|C12 = 01011 , которую ранее мы получили другим путем. Это означает, что зная матрицу базисных циклов, из нее можно получить матрицу базисных разрезов и наоборот, из матрицы базисных разрезов можно получить матрицу базисных циклов. Все действия по построению матрицы базисных циклов и матрицы базисных разрезов относительно остовного дерева вытекают из равенства I S′11 + C12 I =0 и сводятся к следующему. -выбирают остовное дерево Т, например е1е2е3 (11100). -добавляя к остовному дереву по одной хорде кодерева (е4,е5), получают базисные циклы, число которых равно числу хорд: е1е2е4 (11010) и е2е3е5 (01101). -составляют матрицу базисных циклов так, чтобы хорды (е4 и е5) образовалии единичную матрицу: е4е5 е1 е2 е3 1 0 1 1 0 Сf = ( I / C12)= 0 1 0 1 1 =I|Cft|=(C11C12) Матрицу I=C11 отбрасывают, матрицу С12 транспонируют и присоединяют к ней справа единичную матрицу, соответствующую остовному дереву (е1е2е3), получая матрицу базисных разрезов, число которых равно числу ребер в остовном дереве (n-1) S = [ S11 |I], где S11 = C12 е4е5е1е2е3 1 0 1 0 0 S = 1 1 0 1 0 0 1 0 0 1 Таким образом, вся работа по определению базисных циклов и базисных разрезов выполняется почти механически без вычисления обратных матриц. Рассмотренные матрицы являются удобной и практически исчерпывающей формой представления структурных свойств графов. Определение базисных матриц для циклов и разрезов основано на понятиях остовного дерева, ветвей дерева и хорд. Задавая или вычисляя матрицы разрезов и циклов, мы всегда фиксируем по отношению к какому остовному дереву они определялись. Число независимых остовных деревьев определяется достаточно просто. Каждое остовное дерево содержит n-1 ветви. Ребер в графе m, поэтому |Т|= m/(n-1); максимальное число ребер для полносвязного графа m = n(n-1)/2, отсюда |Т|мах= n(n-1)/2(n-1)=n/2. Вместе с тем, количество циклов и разрезов, их реберный состав остаются неизмененными с точностью до переименования ребер. Это подтверждается тем, что ранг матрицы и цикломатическое число определяются числом вершин и ребер графа и не зависят от выбора остовного дерева. Представляет интерес определить количество остовных деревьев графа. Для определения общего числа остовных деревьев воспользуемся матрицей степеней вершн графа К=|| kij || размерности n x n, которая определяется следующим образом: -ρ , если i ≠ j и вершины viи vj связывают ρ Кij = паралельных ребер; d(vi), если i=j для рассматриваемого графа G(4,5) матрица ||kij || имеет вид: 3 -1 -1 -1 Kij = -1 2 -1 0 -1 -1 3 -1 -1 0 -1 2 Доказано, что все алгебраические дополнения матрицы степеней связного неориентированного графа имеют одинаковое значение, равное числу остовных деревьев графа. Рассмотрим алгебраическое дополнение к элементу К41: -1 -1 -1 2 -1 -1 -1 ТΣ = - 2 -1 0 = - + =5+3= 8 -1 3 -1 -1 3 2 -1 аналогичный результат получим, если определим алгебраическое дополнение к элементу К23 3 -1 -1 -1 -1 3 -1 3 -1 ТΣ = - -1 -1 -1 = +0* -2* = 8 -1 0 2 -1 -1 -1 -1 -1 -1 Заметим, что для вычисления определителя в первом случае он разлагается по элементам третьего столбца, во втором по элементам третьей строки, но в обоих случаях используется обычная алгебра. Эти остовы были определены ранее и сведены в таблицу 1. Лекция 9 ВЗАИМОСВЯЗЬ МАТРИЦ ГРАФОВ |