Топологический анализ графов сетевых систем

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

Full description

Saved in:

Bibliographic Details
Date:	2005
Main Author:	Волков, А.А.
Format:	Article
Language:	Russian
Published:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2005
Subjects:	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/13865
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Топологический анализ графов сетевых систем / А.А. Волков // Систем. дослідж. та інформ. технології. — 2005. — № 3. — С.99 -113. — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859949664179060736
author	Волков, А.А.
author_facet	Волков, А.А.
citation_txt	Топологический анализ графов сетевых систем / А.А. Волков // Систем. дослідж. та інформ. технології. — 2005. — № 3. — С.99 -113. — Бібліогр.: 5 назв. — рос.
collection	DSpace DC
description	Сильно связный граф сети представляется в виде конечномерного векторного пространства, порожденного его звеньями с определенными на нем базисами взаимно ортогональных подпространств независимых обобщенных узлов и независимых циклов. Используется аппарат линейной алгебры для обоснования методов получения матричных операторов линейных преобразований независимых обобщенных узлов, а также независимых циклов и определения их взаимозависимости. The strongly coherent columns of a network is represented as a finite-dimensional vector space, caused by its parts with bases, determined on him, mutually orthogonal subspace of independent generalized units and independent cycles. For a substantiation linear transformations matrix operators of the independent generalized units and cycles and definition of their mutually dependence is used. Сильно зв’язний граф мережі подається у вигляді кінцевовимірного векторного простору, породженого його ланками з визначеними на ньому базисами взаємно ортогональних підпросторів незалежних узагальнених вузлів та незалежних циклів. Використовується апарат лінійної алгебри для обґрунтування методів отримання матричних операторів лінійних перетворень незалежних узагальнених вузлів і незалежних циклів та визначення їх взаємозалежності.
first_indexed	2025-12-07T16:16:10Z
format	Article
fulltext	 А.А. Волков, 2005 Системні дослідження та інформаційні технології, 2005, № 3 99 TIДC НОВІ МЕТОДИ В СИСТЕМНОМУ АНАЛІЗІ, ІНФОРМАТИЦІ ТА ТЕОРІЇ ПРИЙНЯТТЯ РІШЕНЬ УДК 519.176 ТОПОЛОГИЧЕСКИЙ АНАЛИЗ ГРАФОВ СЕТЕВЫХ СИСТЕМ А.А. ВОЛКОВ Сильно связный граф сети представляется в виде конечномерного векторного пространства, порожденного его звеньями с определенными на нем базисами взаимно ортогональных подпространств независимых обобщенных узлов и не- зависимых циклов. Используется аппарат линейной алгебры для обоснования методов получения матричных операторов линейных преобразований незави- симых обобщенных узлов, а также независимых циклов и определения их взаимозависимости ВВЕДЕНИЕ Топологический анализ сетевых систем относится к проблематике теории графов. В терминах графов формулируются и решаются задачи по самым различным дисциплинам: электротехнике и электронике, социологии и эко- номике, топологии и алгебре, автоматике и кибернетике, теории информа- ции и исследованию операций. Все эти задачи содержат общее математиче- ское ядро, относящееся к специфической проблематике теории графов. К какой бы области знаний не относилась задача, она почти всегда может быть представлена как чисто в содержательном, так и в формализованном виде. Формализация обычно приводит к лучшему пониманию задач, так как при этом вскрываются их наиболее существенные особенности — структур- ные свойства, которые, как правило, отображаются графами. Во многих случаях решение рассматриваемых задач связано с анализом тех или иных топологических характеристик графов. Поэтому роль теории графов посто- янно возрастает, чему способствуют запросы практики и развитие приклад- ных наук [1]. В основу определения графа естественно положить теоретико- множественное его представление [2, 3]. Граф G всегда можно представить двумя взаимосвязанными множествами абстрактных объектов. Одно из них — множество X изолированных вершин, другое — множество V ребер (если ребро графа неориентировано — оно называется звеном, если ориенти- ровано — дугой). Множества X и V будем называть графообразующими. Графом G назовем отношение на декартовом произведении непустого множества X вершин и непустого множества V ребер VXG ×⊂ . (1) А.А. Волков ISSN 1681–6048 System Research & Information Technologies, 2005, № 3 100 Декартово произведение (1) представляет собой множество всех упоря- доченных пар ( )vx, при условии, что Xx∈ ; Vv∈ , ( ){ }vxVX ,=× , Xx∈ , Vv∈ . Вершины графа могут быть поставлены в соответствие любым объек- там, а ребра — связи между ними. Геометрическая конфигурация графа не имеет значения. Интерес представляет только то, какие вершины являются граничными точками Vvi ∈ ребер. Ребро инцидентно вершине Xx j ∈ , если jx — граничная точка iv . Два различных ребра sv и qv ( qs vv ≠ ) называются смежными, если они имеют какую-нибудь общую граничную точку kx (инцидентны одной и той же вершине). Две различные вершины kx и lx ( )lk xx ≠ смежны, если они являются граничными точками какого-нибудь одного и того же ребра sv . Число ребер, инцидентных вершине kx , называется степенью вершины kx . Цепью на графе называется такая последовательность ( )mqsi vvvv ,,, смеж- ных ребер, в которой одна из граничных вершин предыдущего ребра явля- ется граничной вершиной последующего. Циклом называется замкнутая цепь на графе. Граф связен, если любые две его различные вершины jx и nx ( )nj xx ≠ можно соединить цепью. Граф сильно связен (сильно связан- ный), если любые две его различные вершины jx и nx ( )nj xx ≠ можно включить в некоторый цикл на графе. Ребро, обе граничные точки которого совпадают, называется петлей. Ребро iv , соединяющее две различные вер- шины kx и ix , может быть ориентированным (с заданным направлением) или неориентированным. Граф, содержащий только ориентированные ребра (дуги), называется ориентированным (орграфом). Граф, содержащий только неориентированные ребра (звенья), называется неориентированным (неографом). При исследовании топологической структуры графов существенное значение имеет понятие дерева графа. Связный подграф H графа HG ⊂ , содержащий все вершины графа, но не имеющий ни одного цикла, называ- ется остовным деревом графа G . Антидеревом (кодеревом) называется под- граф S , содержащий все вершины и дополняющий остовное дерево H до графа G . Очевидно, что объединение подграфов H и S образует граф G , т.е. GSH =∪ . Дуги дерева H называют ветвями, а дуги кодерева — хор- дами или связями. Подграф S может быть несвязным. Один и тот же граф может иметь некоторое конечное множество остовных деревьев. Любая сеть C однозначно отображается изоморфным ей сильно связ- ным графом G . Каждой вершине Xx j ∈ графа G может быть поставлено в соответствие некоторое подмножество дуг VY j ∈ , инцидентных вершине jx , причем каждая дуга определяется ее порядковым номером iv и знаком ivsign , где    − + = .вершинекнаправленоесли, ,вершиныотнаправленоесли, sign ji ji i xv xv v Топологический анализ графов сетевых систем Системні дослідження та інформаційні технології, 2005, № 3 101 Таким образом, по определению множество jY инцидентности дуг вы- ражается соотношением { } jiij JivvY ∈⋅= ,sign , где jJ — множество индексов, которыми помечены дуги, инцидентные вершине jx . Каждой вершине jx графа ставится в соответствие множество jY инцидентности дуг, а всему множеству X вершин графа — семейство { }121 ,...,, += nYYYY множеств инцидентности дуг. Следовательно, граф может быть определен парой ( )YVG ,= , где V — непустое множество дуг; Y — семейство множеств инцидентно- стей дуг. Каждая дуга iv графа G без петель должна входить в два какие-нибудь множества семейства Y , причем для ориентированного графа с различными знаками, а для неориентированного — с одинаковыми. Назовем два подмно- жества kY и lY , в которые входит одна и та же дуга iv , смежными. Основы- ваясь на изложенном выше, сформулируем следующее утверждение. Утверждение 1. Если задано n множеств jY инцидентностей дуг сильно связного графа G без петель, имеющего ( )1+n вершин, то граф полностью определен. Следствие. Суммарное количество J элементов множеств njY j ,1, = инцидентностей дуг связного графа G , необходимое для задания графа, рав- няется удвоенному числу m элементов множества V дуг графа за вычетом числа jI элементов произвольного множества 1+nY инцидентности дуг графа. ЛИНЕЙНЫЕ ОПЕРАТОРЫ В m -МЕРНОМ ВЕКТОРНОМ ПРОСТРАНСТВЕ ЗВЕНЬЕВ ГРАФА Матрицы составляют основной аналитический аппарат для изучения линей- ных операторов в m-мерном пространстве звеньев графа. Рассмотрим способы задания графов, которые основываются на отно- шении (1). Пусть в конечном графе G без петель и параллельных ребер оп- ределены его графообразующие множества: множество вершин { }jxX = , 1,1 += nj и множество ребер { } mivV i ,1, == . Отношения соответствия элементов этих множеств определяются матрицей инцидентности jia , minj ,1;1,1 =+= . Строки соответствуют вершинам графа, а столбцы — ребрам (звеньям, дугам). Матрица инцидентности может служить базой для изучения основных структурных характеристик сильно связного графа сети. Для этого граф G А.А. Волков ISSN 1681–6048 System Research & Information Technologies, 2005, № 3 102 будем рассматривать как конечномерное векторное пространство, порож- денное его дугами, в котором выделяется подпространство множеств инци- дентности дуг. Графу G можно сопоставить некоторое линейное преобразование, где каждому множеству NjY j ∈, поставлен в соответствие вектор jy , а семей- ству Y множеств инцидентности дуг — вектор y . Это линейное преобразование определяется системой        +++= +++= +++= ++++ mmnnnn mm mm vavavay vavavay vavavay ,122,211,11 22221212 12121111 ... ......... ... ... . (2) Коэффициенты jia преобразования (2) принадлежат подмножеству Φ , состоящему из чисел 1,1,0 −+ некоторого числового поля Φ⊃F . Рассмотрим два векторных пространства над подмножеством Φ число- вого поля F : m -мерное V и ( )1+n -мерное Y . Выберем в пространстве V некоторый базис mee ,1 и в пространстве Y некоторый базис 11,..., +ngg , в качестве которых можно взять столбцы единичной матрицы m -го и ( )1+n -го порядков соответственно. Преобразование (2) относит каждому вектору ∑ = = m i ii evv 1 из V неко- торый вектор ∑ + = = 1 1 n j jj gyy из Y , т.е. преобразование (2) определяет неко- торый линейный оператор xΨ , относящий вектору v из V вектор y из Y . vy xΨ= . (3) Линейный оператор xΨ , отображающий пространство V дуг графа в подпространство Y семейства множеств инцидентностей дуг (или в пространство вершин X ) графа, назовем оператором инциденций графа. Этому оператору при некотором базисе соответствует прямоугольная матрица 0 xA с размерами ( ) mn ×+1 1,1;,1,0 +=== njmiaA jix , (4) представляющая собой матрицу инциденций графа. Эта матрица является вполне унимодулярной. Каждый столбец ее имеет два ненулевых элемента: 1+ и 1− . Справедливо следующее Утверждение 2. Если граф G , содержащий ( )1+n вершину, связен, то ранг матрицы 0 xA равен n . Следствие 1. Ранг каждой матрицы ( )j xA , 1,...,2,1 += nj , полученной из матрицы инциденций 0 xA вычеркиванием j -й строки, равен n . Топологический анализ графов сетевых систем Системні дослідження та інформаційні технології, 2005, № 3 103 В самом деле, строки этой матрицы порядка mn× являются линейно независимыми, количество строк равно рангу матрицы ( )j xA . Каждая из этих матриц содержит jImJ −= 2 ненулевых элементов и полностью определя- ет топологию графа сети. Положим 1+= nj , соответствующую матрицу ( )1+n xA обозначим xA , тогда nmnn m m x aaa aaa aaa A ... .... ... ... 21 22221 11211 = . (5) Строки матрицы xA являются линейно независимыми, количество строк n равно рангу матрицы xA . Следствие 2. Число линейно независимых столбцов матрицы xA силь- но связного графа G , имеющего ( )1+n вершин, равняется n . Это непосредственно следует из того, что максимальное число линейно независимых строк матрицы равно максимальному числу ее линейно неза- висимых столбцов. Столбцам матрицы xA соответствуют координаты дуг iv графа G в пространстве X его вершин или в пространстве Y узловых подмножеств его дуг. Утверждение 3. Ранг r линейного оператора xψ , отображающего про- странство V дуг связного графа G , имеющего ( )1+n вершин, в подпро- странство Y его узлов, равен n . Для выделения базиса оператора xψ и удобства оперирования с матри- цей xA целесообразно вершины (или элементарные узлы) и дуги графа про- нумеровать таким образом, чтобы линейно независимые столбцы матрицы инциденций 0 xA (или матрицы xA ), соответствующие дугам дерева H гра- фа G , составляли бы подматрицу 1xA матрицы xA . Согласно теореме, доказанной в работе [1], подграф H представляет собой дерево тогда и только тогда, когда определитель квадратной матрицы n jia 1 , полученной из матрицы инциденций 0 xA порядка ( ) nn ×+1 вычерки- ванием одной строки, равен 1 или 1− . Во всех остальных случаях этот оп- ределитель равен нулю. Используем это утверждение и метод его доказательства для обоснова- ния более общего утверждения об упорядочивающей нумерации сильно связного графа, позволяющей выделить базис независимых столбцов матри- цы xA порядка mn× , соответствующей ветвям дерева H графа. Определение. Матрицу xA назовем упорядоченной матрицей, если она содержит неособенную подматрицу 1xA треугольного вида, ранг r кото- рой соответствует рангу матрицы xA . А.А. Волков ISSN 1681–6048 System Research & Information Technologies, 2005, № 3 104 Нумерацию вершин и дуг графа G , приводящую к образованию упо- рядоченной матрицы xA из матрицы инциденций 0 xA вычеркиванием ( )1+n -й строки, назовем упорядочивающей нумерацией графа. Утверждение 4. Вершины jx , Nj∈ , 1+= nN и дуги iv , Mi∈ , mM = сильно связного графа G всегда можно пронумеровать таким обра- зом, чтобы матрица xA порядка mn× содержала бы квадратную подматри- цу 1xA порядка n треугольного вида, столбцы которой соответствовали бы ветвям одного из деревьев графа. В результате такой нумерации вершин и дуг графа G матрица xA мо- жет быть представлена в виде двух подматриц ( )21, xxx AAA = , первая из которых jix aA =1 , ninj ,1;,1 == представляет собой квадратную неосо- бенную подматрицу n -го порядка треугольного вида (нижняя или верхняя). 1... ..... 0...1 0...01 0...001 321 3231 21 1 ± ± ± ± = nnn x aaa aa a A . (6) Определитель любой треугольной матрицы равен произведению эле- ментов главной диагонали. Поскольку на главной диагонали подматрицы 1xA находятся единичные элементы, то ( ) 1Det 1 ±=xA . Следовательно, столбцы этой подматрицы соответствуют ветвям одного из деревьев графа G , что и требовалось доказать. Подматрица jix aA =2 , mninj ,1;,1 +== образуется столбцами мат- рицы xA , являющимися линейными комбинациями столбцов подматрицы 1xA и соответствуют дугам антидерева (кодерева) графа G . ЛИНЕЙНЫЕ ОПЕРАТОРЫ ПОДПРОСТРАНСТВА НЕЗАВИСИМЫХ ОБОБЩЕННЫХ УЗЛОВ СИЛЬНО СВЯЗНОГО ГРАФА Обобщенным узловым подмножеством дуг (или обобщенным узлом) назы- вается замкнутое очертание, которое может содержать несколько элемен- тарных узлов (узловых подмножеств дуг) графа [4]. Одно узловое подмно- жество или один узел графа можно рассматривать как частный случай обобщенного узлового подмножества дуг. Каждому узловому подмножеству jY графа G соответствует вектор jy пространства Y . Каждому обобщенному узловому подмножеству kY0 можно также сопоставить вектор ky0 пространства R , если  jk YY =0 . Существует множество различных обобщенных узлов графа, однако интерес представляют лишь независимые обобщенные узлы. Топологический анализ графов сетевых систем Системні дослідження та інформаційні технології, 2005, № 3 105 Независимым обобщенным узлом графа при произвольно выбранном базисе (дереве) назовем такое обобщенное подмножество дуг, которое со- держит только одну ветвь (дугу) дерева графа. Векторы ky0 образуют базис пространства R . Обозначим n kjtT 1 = квадратную матрицу перехода от базиса { }ky к базису { }ky0 ; ξ — линей- ный оператор, отображающий пространство Y на себя так, что базис { }ky переходит в { }ky0 : kk yy 0=ξ . (7) Вводя координатные столбцы ( )′= nyyyy 002010 ,...,, и ,,( 21 yyy = ), ′ny , (7) записываем в матричной форме yTy =0 . (8) Матрицу n kjtT 1 = можно получить из матрицы инциденций узловых подмножеств дуг графа и независимых обобщенных узлов.     ∉ ∈ = .если,0 ,если,1 0 0 kj kj kj yy yy t (9) На рис. 1 показан граф с выделенным деревом (базисом независимых обобщенных узлов). Независимые обобщенные узлы графа (отсечения) обо- значены пунктирными линиями, а матрица T имеет вид 11111 01000 00111 00011 00001 =T . (10) Рис. 1. Граф с выделенным деревом II II III III I I IV IV V V 1 I 1 2 2 3 6 5 4 5 6 9 3 8 4 7 А.А. Волков ISSN 1681–6048 System Research & Information Technologies, 2005, № 3 106 Упорядоченная матрица xA для этого графа при выбранном базисе, со- ответствующая оператору xψ Рассмотрим, каким образом, располагая операторами xψ , ξ и соответ- ствующими им матрицами xA , T , можно определить оператор ψ - преобразования m -мерного пространства V дуг графа в n -мерное подпро- странство R и соответствующую ему матрицу A . Справедливо следующее Утверждение 5. Оператор ψ , преобразующий пространство V дуг графа в подпространство R его независимых обобщенных узлов, опреде- ляется операторным равенством xξψψ = , где xψ — оператор, преобра- зующий пространство V в Y ; ξ — оператор, преобразующий под- пространство Y в себя так, что базис { }ky переводится в базис { }ky0 независимых обобщенных узлов графа R . Справедливость утверждения непосредственно следует из [5]. Следствие. Матрица A независимых обобщенных узлов графа, соот- ветствующая оператору ψ , определяется матричным равенством xATA = . (12) Заметим, что операция умножения матриц T и xA всегда выполнима, так как число столбцов матрицы T равно числу строк матрицы xA и рангу этих матриц nr = . Коэффициенты jia матрицы A независимых обобщенных узлов графа принадлежат подмножеству Ф числового поля F и определяются следую- щим соотношением:      ∈− ∈ ∉ = − − .дугиконец,если,1 ,дугиначало,если,1 ,если,0 0 0 0 i k ij k i i н ij н i ji ji vvYv vvYv Yv a (13) Эту матрицу можно назвать матрицей инциденций дуг и независимых обобщенных узлов. В качестве примера воспользуемся равенством (12) и определим мат- рицу A для графа, показанного на рис. 1. Подставив в (12) матрицы (10) и (11), получаем . 000011100 001101000 100000110 000100011 110000001 −− − −− − − =xA 1xA 2xA (11) Топологический анализ графов сетевых систем Системні дослідження та інформаційні технології, 2005, № 3 107 Эта матрица состоит из единичной подматрицы nEA 11 = и подматрицы 2A , т.е. ( )21, AAA = . Матрицу A можно назвать упорядоченной матрицей независимых обобщенных узлов. Утверждение 6. Матрицу A , соответствующую оператору ψ линей- ного преобразования пространства V дуг графа в подпространство R его независимых обобщенных узлов, всегда можно получить элементарным преобразованием матрицы инциденций 0 xA или эквивалентных ей матриц ( )j xA , соответствующих оператору xψ . Для примера рассмотрим способ получения матрицы A элементарным преобразованием матрицы xA , определяемой выражением (11). Нетрудно видеть, что строки искомой матрицы (14) получаются из матрицы (11) прос- тым сложением строк. Произвольный вектор V из пространства V связан с вектором 0y пространства R соотношением Vy ψ=0 . (15) Матричное выражение этого соотношения имеет вид Avy =0 . (16) ЛИНЕЙНЫЕ ОПЕРАТОРЫ ПОДПРОСТРАНСТВА НЕЗАВИСИМЫХ ЦИКЛОВ СИЛЬНО СВЯЗНОГО ГРАФА Топология сильно связного графа определяется также в пространстве ( )* ,θV , образованном множеством V дуг и множеством θ циклов графа. Каждому циклу kθ при заданной его ориентации взаимно-однозначно соответствует вектор kθ из пространства V , а всей совокупности векто- ров — линейное преобразование        +++= +++= +++= msmsss mm mm vbvbvb vbvbvb vbvbvb ... ......... ... ... 2211 22221212 12121111 θ θ θ . (17) 011010000 001101000 010100100 110100010 110000001 − − − − − =A . 1A 2A (14) А.А. Волков ISSN 1681–6048 System Research & Information Technologies, 2005, № 3 108 Коэффициенты kib преобразования (17) принадлежат числовому полю Φ , состоящему из чисел 1,1,0 −+ некоторого числового поля Φ⊃F в следующей зависимости:      ∈− ∈ ∉ = ..совпадаютнеиориентациииесли,1 совпадают,иориентациииесли,1 ,если,0 kiki kiki ki ki vv vv v b θθ θθ θ (18) Подпространство θ векторного пространства V , являющееся линей- ной оболочкой системы векторов kθ , sk ,1= , назовем подпространством циклов графа G . В сильно связном графе существуют как независимые, так и зависимые циклы. Нас интересует система независимых циклов (базис подпространства θ независимых циклов графа). В графе G существует, вообще говоря, ( )HΛ вариантов выбора бази- сов независимых циклов графа, где ( )HΛ — число деревьев графа. Число независимых циклов графа при выбранном базисе определяется цикломати- ческим числом, равным количеству дуг антидерева сильно связного графа, т.е. nms −= . (19) Преобразование (17) определяет некоторый линейный оператор ϕ′ , от- носящий вектору v из V вектор ′θ из θ , т.е. vϕθ ′=′ . (20) Оператору ϕ′ соответствует матрица θB (матрица циклов), составлен- ная из координат векторов kθ в (17). Элементарными преобразованиями матрицы θB , как это было показа- но выше применительно к матрице xA , можно матрицу θB произвольных циклов привести к виду ( )21, BBB = , (21) где sEB 12 = — единичная матрица порядка s . Матрицу B назовем упоря- доченной матрицей инциденций независимых циклов графа. Матрица B при базисе sθθ ,...,1 , состоящем из независимых циклов, соответствует ли- нейному оператору ϕ , отображающему пространство V дуг графа в подп- ространство θ . vϕθ = . (22) По аналогии с выражением (12) связь между матрицей B независимых циклов графа и матрицей θB произвольных циклов определяетя выражением θNBB = , (23) где N — матрица преобразования произвольных циклов k ′θ в независимые циклы kθ . Топологический анализ графов сетевых систем Системні дослідження та інформаційні технології, 2005, № 3 109 Для определения матрицы ( )21 , BBB = существует простой геометри- ческий метод, основанный на выборе базиса независимых циклов (антиде- рева) графа. Из методологических соображений сформулируем следующее важное утверждение, которое фактически широко используется на прак- тике. Утверждение 7. Циклы kθ и дуги iv сильно связного графа G всегда можно пронумеровать таким образом, чтобы матрица B инциденций дуг iv и циклов kθ графа представляла собой упорядоченную матрицу ( )21, BBB = независимых циклов графа, т.е. содержала бы единичную подматрицу ( )sEB 12 = порядка nms −= . Доказательство. Пусть дан сильно связный граф G , имеющий m дуг iv и ( )1+n вершин jx . Пронумеруем все вершины jx и первые n дуг графа методом, использу- емым в утверждении 4. При этом образуется дерево графа, содержащее все n его пронумерованных дуг. Оставшиеся nms −= непронумерованных дуг бу- дут соответствовать ветвям антидерева графа, т.е. базису его независимых циклов. Зададимся направлениями независимых циклов графа, т.е. циклов, содержащих только одну дугу антидерева графа, соответствующих направ- лениям входящих в них дуг антидерева графа. Нумерацию циклов kθ ( )sk ,1= и дуг iv ( )ni ,1= антидерева графа будем производить таким обра- зом, чтобы их индексы определялись зависимостью nik −= для mni ≤+≥ 1 . Составим далее матрицу, столбцы которой соответствуют ду- гам графа, а строки — циклам с элементами kib , определяемыми зависимо- стью (18). Получим таким образом искомую упорядоченную матрицу B независимых циклов графа, что и доказывает утверждение. На рис. 2 показан граф, нумерация и ориентация дуг которого такие же, как и у графа на рис.1. Нумерация циклов графа произведена в соответствии с условиями, рас- смотренными в утверждении 7. Матрица B инциденций дуг и независимых циклов этого графа имеет вид Рис. 2. Граф с выделенными независимыми обобщенными узлами IV II III I 3 8 5 1 9 2 4 7 6 А.А. Волков ISSN 1681–6048 System Research & Information Technologies, 2005, № 3 110 Выражение (22) в матричном виде определяется уравнением Bv=θ . (24) СВЯЗЬ МЕЖДУ ЛИНЕЙНЫМИ ОПЕРАТОРАМИ НЕЗАВИСИМЫХ ОБОБЩЕННЫХ УЗЛОВ И НЕЗАВИСИМЫХ ЦИКЛОВ СИЛЬНО СВЯЗНОГО ГРАФА При топологическом анализе графов сетевых систем возникает необходи- мость определения операторов независимых циклов графа по операторам независимых обобщенных узлов или наоборот. Конкретно это выражается в необходимости определения матрицы B независимых циклов графа по мат- рице A независимых обобщенных узлов. Существует аналитический метод определения матрицы циклов графа по матрице его инциденций. Этот метод базируется на одной из основных теорем топологии сетей, впервые сформу- лированной еще Анри Пуанкаре в 1899 г., а затем в различных ее интерпре- тациях и другими авторами. Доказательство этой теоремы приводится во многих источниках и, в частности, в работе [1]. Пользуясь нашими обозначениями, суть этой теоремы можно выразить зависимостью 00 =θxA , т.е. произведение матрицы инциденций 0 xA на век- тор-цикл θ равняется нулю. Область применения данной теоремы, следовательно, ограничена толь- ко матрицей инциденций дуг и элементарных узлов графа и не распростра- няется в данной ее трактовке на матрицу независимых обобщенных узлов. В более общей постановке множество V дуг графа порождает m - мерное пространство V , в котором определены два подпространства: n - мерное подпространство Y узловых подмножеств дуг (узлов) и s -мерное подпространство θ циклов графа. Докажем, что эти подпространства взаимно ортогональны. Утверждение 8. Подпространство Y узлов сильно связного графа G и подпространство θ его циклов являются взаимно ортогональными. Доказательство. По определению два подпространства называются взаимно ортогональными, если каждый вектор одного ортогонален к любо- му вектору другого. Произвольный вектор обобщенного узла jy0 графа определяется вы- ражением . 100000011 010010111 001011000 000101110 −− −− −− =B 1B 2B Топологический анализ графов сетевых систем Системні дослідження та інформаційні технології, 2005, № 3 111 ∑ = = m i ijij vay 1 0 , nj ,1= , (25) где jia — коэффициенты матрицы A независимых обобщенных узлов, определяемые соотношением (13). Произвольный вектор-цикл kθ графа G определяется зависимостью ∑ = = m l lklk vb 1 θ , sk ,1= , (26) где klb — коэффициенты матрицы B для циклов графа, определяемые соотношением (18). Здесь mivi ,...,1= будем рассматривать как ортонормированный базис евклидова пространства, для которого справедливо соотношение ( )    == ≠ == .,1,,при1 ,при0 nlili li vv illi δ (27) Такое допущение основано на известном положении: в любом конеч- номерном подпространстве или пространстве существует ортонормиро- ванный базис, который может быть получен из любой системы линейно не- зависимых векторов этого подпространства путем ортогонализации и нормализации. Для доказательства утверждения необходимо и достаточно показать, что произвольный вектор jy0 , Nj∈ графа G ортогонален произвольному вектору kθ , Sk ∈ этого же графа ( )SkNjy kj ∈∈⊥ ,,0 θ , т.е. скалярное произведение этих векторов равно нулю. Скалярное произведение векторов jy0 и kθ при ортонормированном базисе m -мерного евклидова пространства определяется выражением ( ) ( )∑ ∑ = = == m il m il kljilikljikj bavvbay 1, 1, 0 θ , sknj ,1;,1 == , (28) что непосредственно следует из выражений (25) и (26) с учетом (27). Выяс- ним, какие значения приобретают коэффициенты jia и klb , входящие в вы- ражение (28). Можно убедиться, что для всех возможных случаев скалярное произ- ведение векторов jy0 и kθ равняется нулю, т.е. ( ) ∑ = ==== m i kijikj sknjbay 1 0 ,1;,1,0θ , (29) что и доказывает утверждение. Учитывая, что элементарный узел графа — частный случай его обоб- щенного узла, это полностью справедливо и для векторов-узлов, т.е. удовле- творяется также и соотношение А.А. Волков ISSN 1681–6048 System Research & Information Technologies, 2005, № 3 112 ( ) 0=njy θ . (30) Заметим также, что подпространство θ является ортогональным до- полнением к Y (или наоборот). Суммарная размерность этих подпро- странств равна размерности всего пространства V . Если n — размерность R , а s — размерность θ , то размерность все- го пространства V равна snm += . Ортонормированными базисами под- пространств R и θ являются соответственно дуги дерева и антидерева (кодерева) графа. Следствие. Если jiaA = , minj ,1;,1 == — упорядоченная матрица независимых обобщенных узлов, а skibB = , misk ,1;,1 == — независи- мых циклов, то справедливо соотношение 0=′=′ ABBA , (31) где B′ и A′ — транспонированные матрицы соответственно B и A . Соотношение (31) непосредственно следует из выражения (29). Имея в виду, что 21, AAA = , 21, BBB = , 0, 2 1 21 = ′ ′ B B AA , 0, 2 1 21 = ′ ′ A A BB , откуда ( ) 1 1221 −′′−= AABB , ( ) 1 2112 −′′−= BBAA . Поскольку nEA 11 = , sEB 12 = и EE =′ −1)( , то ns EAEB 211 ′−= , sn EBEA 112 ′−= . Зная, что ijaA =′2 , njmni ,1;,1 =+= ; ikbB =′1 , skni ,1;,1 == , име- ем 21 AB ′−= , 12 BA ′−= . (32) Эти выражения позволяют получить подматрицу 1B независимых цик- лов графа по подматрице 2A независимых обобщенных его узлов и наобо- рот. Выражения (32) показывают, что достаточно знать только один из опе- раторов Ψ или ϕ , представленных в виде соответствующих им матриц A или B , чтобы определить как вектор 0y независимых узловых подмно- жеств дуг графа, так и вектор θ независимых циклов графа. Матричные уравнения vAy = , vB=θ можно записать в виде III vAvAy 21 += , III vBvB 21 +=θ , (33) Топологический анализ графов сетевых систем Системні дослідження та інформаційні технології, 2005, № 3 113 где Iv — матрица-столбец, соответствующая дугам дерева графа; IIv — матрица-столбец, соответствующая дугам антидерева графа. С учетом (32) и имея в виду, что nEA 11 = ; sEB 12 = , уравнения (33) можно записать так: III vAvy 2+= , III vvA +′= 2θ (34) или III vBvy 1′−= , III vvB += 1θ . (35) Эти системы уравнений позволяют выразить столбцевые матрицы y и θ только через одну из подматриц: 2A или 1B . ВЫВОДЫ 1. Путем обобщения работ в области исследования сетевых систем обоснованы алгебраические методы топологического анализа графов сетей. Сильно связный граф сети представляется в виде конечномерного векторно- го пространства V , порожденного его звеньями (дугами) с определенными на нем подпространствами Y узлов (вершин), R независимых обобщен- ных узлов и θ независимых циклов, базисами которых являются соответ- ственно деревья и кодеревья графа. 2. Рассматриваются линейные операторы, отображающие пространство V в подпространствах Y , R и θ . Исследуются взаимосвязи между эти- ми операторами. Матричные представления операторов позволяют исполь- зовать аппарат линейной алгебры для обоснования алгоритмов получения матрицы A независимых обобщенных узлов и матрицы B независимых циклов графа сети. 3. Векторные пространства R и θ являются взаимно ортогональны- ми, что позволяет установить взаимосвязь между матрицами A и B . 4. Результаты топологического анализа графа алгебраическими мето- дами дают возможность автоматизировать процесс определения матриц A и B , используемых при моделировании, исследовании и расчете сетевых сис- тем. ЛИТЕРАТУРА 1. Берж К. Теория графов и ее применение. — М.: Изд-во иностр. лит., 1962. — 320 с. 2. Волков А.А. Моделирование систем графами // Вісн. КМУЦА. — 1998. — № 1. — С. 268–279. 3. Волков А.А. Построение и структура моделирующих графов сложных систем // Системні дослідження та інформаційні технології. — 2000. — № 2. — С. 118–132. 4. Максимович Н.Т. Линейные электрические цепи и их преобразования. — М.: Госэнергоиздат, 1961. — 264 с. 5. Гантмахер Ф.Р. Теория матриц. — М.: Наука, 1967. — 575 с. Поступила 24.06.2004 НОВІ МЕТОДИ В СИСТЕМНОМУ АНАЛІЗІ, ІНФОРМАТИЦІ ТА ТЕОРІЇ ПРИЙНЯТТЯ РІШЕНЬ Топологический анализ графов сетевых систем А.А. Волков ВВЕДЕНИЕ Линейные операторы в -мерном векторном пространстве звеньев графа Линейные операторы подпространства независимых обобщенных узлов сильно связного графа Линейные операторы подпространства независимых циклов сильно связного графа Связь между линейными операторами независимых обобщенных узлов и независимых циклов сильно связного графа ВЫВОДЫ Рис. 1. Граф с выделенным деревом Рис. 2. Граф с выделенными независимыми обобщенными узлами
id	nasplib_isofts_kiev_ua-123456789-13865
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1681–6048
language	Russian
last_indexed	2025-12-07T16:16:10Z
publishDate	2005
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
record_format	dspace
spelling	Волков, А.А. 2010-12-06T10:28:56Z 2010-12-06T10:28:56Z 2005 Топологический анализ графов сетевых систем / А.А. Волков // Систем. дослідж. та інформ. технології. — 2005. — № 3. — С.99 -113. — Бібліогр.: 5 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/13865 519.176 Сильно связный граф сети представляется в виде конечномерного векторного пространства, порожденного его звеньями с определенными на нем базисами взаимно ортогональных подпространств независимых обобщенных узлов и независимых циклов. Используется аппарат линейной алгебры для обоснования методов получения матричных операторов линейных преобразований независимых обобщенных узлов, а также независимых циклов и определения их взаимозависимости. The strongly coherent columns of a network is represented as a finite-dimensional vector space, caused by its parts with bases, determined on him, mutually orthogonal subspace of independent generalized units and independent cycles. For a substantiation linear transformations matrix operators of the independent generalized units and cycles and definition of their mutually dependence is used. Сильно зв’язний граф мережі подається у вигляді кінцевовимірного векторного простору, породженого його ланками з визначеними на ньому базисами взаємно ортогональних підпросторів незалежних узагальнених вузлів та незалежних циклів. Використовується апарат лінійної алгебри для обґрунтування методів отримання матричних операторів лінійних перетворень незалежних узагальнених вузлів і незалежних циклів та визначення їх взаємозалежності. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Топологический анализ графов сетевых систем The topological analysis of graphs of network systems Топологічний аналіз графов мережевих систем Article published earlier
spellingShingle	Топологический анализ графов сетевых систем Волков, А.А. Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
title	Топологический анализ графов сетевых систем
title_alt	The topological analysis of graphs of network systems Топологічний аналіз графов мережевих систем
title_full	Топологический анализ графов сетевых систем
title_fullStr	Топологический анализ графов сетевых систем
title_full_unstemmed	Топологический анализ графов сетевых систем
title_short	Топологический анализ графов сетевых систем
title_sort	топологический анализ графов сетевых систем
topic	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
topic_facet	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
url	https://nasplib.isofts.kiev.ua/handle/123456789/13865
work_keys_str_mv	AT volkovaa topologičeskiianalizgrafovsetevyhsistem AT volkovaa thetopologicalanalysisofgraphsofnetworksystems AT volkovaa topologíčniianalízgrafovmereževihsistem

Топологический анализ графов сетевых систем

Institution

Similar Items