Построение и структура моделирующих графов сложных систем
На базе общей теоретико-множественной модели системы обоснована концепция моделирующего и обобщенного моделирующего графов сложных систем как основы построения баз данных и знаний интеллектуальных информационных систем. Рассмотрены способы задания структуры графов множеством инцидентности и смежност...
Saved in:
| Published in: | Системні дослідження та інформаційні технології |
|---|---|
| Date: | 2002 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2002
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/50228 |
| 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: | Построение и структура моделирующих графов сложных систем / А.А. Волков // Систем. дослідж. та інформ. технології. — 2002. — № 2. — С. 118-132. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859863963695579136 |
|---|---|
| author | Волков, А.А. |
| author_facet | Волков, А.А. |
| citation_txt | Построение и структура моделирующих графов сложных систем / А.А. Волков // Систем. дослідж. та інформ. технології. — 2002. — № 2. — С. 118-132. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | На базе общей теоретико-множественной модели системы обоснована концепция моделирующего и обобщенного моделирующего графов сложных систем как основы построения баз данных и знаний интеллектуальных информационных систем. Рассмотрены способы задания структуры графов множеством инцидентности и смежности и оценивается их эффективность.
На базі загальної теоретико-множинної моделі системи обгрунтована концепція моделюючого і узагальненого моделюючого графів складних систем як основи побудови баз даних та знань інтелектуальних інформаційних систем. Розглянуті засоби задання структури графів множинами інцидентності та суміжності і оцінюється їх ефективність.
A concept of modeling and geleralized modeling graph of complex systems is proved on the basis of common model of system as a base for building data bases and the knowledge base of intellectual information system. Setting of graphs structure by incedenity and contiguity sets is reviewed and their effectiveness is estimated.
|
| first_indexed | 2025-12-07T15:47:22Z |
| format | Article |
| fulltext |
© А.А. Волков
118 ISSN 1681–6048 System Research & Information Technologies, 2002, 2
TIДC
МАТЕМАТИЧНІ МЕТОДИ, МОДЕЛІ,
ПРОБЛЕМИ І ТЕХНОЛОГІЇ ДОСЛІДЖЕННЯ
СКЛАДНИХ СИСТЕМ
УДК УДК 007:681.3.06:519.17.007.57(045)+
ПОСТРОЕНИЕ И СТРУКТУРА МОДЕЛИРУЮЩИХ
ГРАФОВ СЛОЖНЫХ СИСТЕМ
А.А. ВОЛКОВ
На базе общей теоретико-множественной модели системы обоснована
концепция моделирующего и обобщенного моделирующего графов сложных
систем как основы построения баз данных и знаний интеллектуальных
информационных систем. Рассмотрены способы задания структуры графов
множеством инцидентности и смежности и оценивается их эффективность.
ВВЕДЕНИЕ
Существует много сложных систем, которые можно отнести к сетевым. Для
математического описания и исследования процессов, происходящих в этих
системах, применяются методы теории графов. Впервые эти методы были
применены для анализа электрических цепей, а в дальнейшем — электронных
и других систем, геометрическая конфигурация эквивалентных схем
которых представляется графами.
Проблеме математического описания и анализа электромеханических
систем с физически разнородными элементами (электрическими, тепловыми,
механическими, гидравлическими и др.) посвящена монография [1].
Математическая модель физической системы здесь представляется
совокупностью полюсных уравнений отдельных ее компонент и
математическим описанием порядка их соединения, определяемого
некоторым графом. Одним из необходимых условий такого подхода
является обобщенная трактовка физических переменных, входящих в
уравнения компонент системы. Она основывается на свойствах, общих для
способов измерения этих переменных. В зависимости от указанных
способов различаются последовательные (through) и параллельные (across)
фундаментальные переменные. Функциональная связь между ними для
отдельных физических компонент в общем случае определяется
некоторыми операторами, выражающими собой полюсные уравнения
компонент. Указанным фундаментальным переменным соответствуют: токи
и напряжения — в электрических и электронных компонентах, потоки
жидкости или газа и изменения напора — в гидравлических, газовых,
вентиляционных компонентах сетей, силы (крутящие моменты) и линейные
(угловые) перемещения — в механических компонентах, тепловые потоки и
перепады температур — в тепловых компонентах систем и т.д. Второе
Построение и структура моделирующих графов сложных систем.
Системні дослідження та інформаційні технології, 2002, 2 119
необходимое условие такого подхода состоит в том, чтобы фундамен-
тальные последовательные и параллельные переменные удовлетворяли двум
основным постулатам для вершин и циклов моделирующего графа,
определяющего структуру соединения компонентов системы. Если
ориентированным звеньям (дугам) vi моделирующего графа системы
поставлены в соответствие некоторые значения последовательных qi и
параллельных hi фундаментальных переменных, то указанные постулаты
выражаются следующим образом.
Постулат 1. Алгебраическая сумма последовательных переменных qi,
соответствующих дугам, инцидентным произвольной вершине xi графа,
равна нулю.
Постулат 2. Алгебраическая сумма параллельных переменных hi,
соответствующих дугам любого произвольно ориентированного цикла
графа, равна нулю.
Для различных типов физических систем указанные постулаты могут
рассматриваться как отображение и обобщение соответствующих им
физических законов. Для электрических цепей, например, эти постулаты
соответствуют первому и второму законам Кирхгофа. Они были
сформулированы еще в середине прошлого столетия. Для некоторых других
физических систем такое обобщение получено значительно позже.
Например, только в 1955 г. было показано, что формулировка основных
законов механики может быть обобщена и представлена в виде приведенных
выше постулатов. Первый постулат для механических систем содержится в
обычной формулировке основных законов механики. Второй постулат здесь
конкретизируется в следующем виде: полная сумма перемещений по
замкнутому контуру стремится к нулю. В тех случая, когда уравнения
компонент физических систем представляют собой двухполюстники, то
геометрическая конфигурация систем представляется в виде сети или графа.
Фактически любую физическую систему можно представить в виде
некоторой сети и смоделировать ее графом. Особый интерес в этом
отношении представляет работа [2], в которой предпринята попытка
обосновать возможность применения к информационным сетям первого и
второго информационных законов Кирхгофа. Использование понятия
обобщенной топологической модели, введенного в [3], может стать основой
построения обобщенных моделирующих графов сложных систем, включающих
элементы различной физической природы.
1. ОПРЕДЕЛЕНИЯ МОДЕЛИРУЮЩЕГО ГРАФА
Дадим следующее определение моделирующего графа (мультиграфа) сети [3].
Граф (мультиграф) G назовем моделирующим некоторую сеть С, если
удовлетворяются следующие условия:
1. Граф (мультиграф) G изоморфен сети С.
2. Каждой дуге vi графа G поставлены в соответствие последова-
тельные qi и параллельные hi фундаментальные переменные сети С и
операторы Di , отображающие их взаимосвязь в виде
А.А. Волков
ISSN 1681–6048 System Research & Information Technologies, 2002, 2 120
iii qDh = ; mi ,1= ,
где Di — в общем случае совокупность математических действий, которые
нужно произвести, чтобы по переменной qi найти переменную hi.
3. На графе G определены операции сложения последовательных qi и
параллельных ih фундаментальных переменных, выражающих собой
первый и второй постулаты для вершин (узлов) и замкнутых контуров графа
сети в виде уравнений 0=Aq , 0=Bh , где А — матрица линейно
независимых обобщенных узлов; В — матрица линейно независимых
контуров; q и h — векторы последовательных и параллельных фундамен-
тальных переменных соответсвенно.
При некотором дереве графа матрицы А и В определяют два взаимно
ортогональных подпространства: подпространство независимых обобщенных
узлов (вершин) и подпространство независимых контуров. Вследствие этого
справедливо соотношение: 0=⋅ TBA , где Т — символ транспонирования
матрицы. Последнее соотношение позволяет по матрице А найти матрицу В
или наоборот.
2. ТЕОРЕТИКО-МНОЖЕСТВЕННОЕ ПРЕДСТАВЛЕНИЕ ГРАФА
В основу представления графа естественно положить теоретико-множественную
модель системы. Такая модель предполагает задание семейства множеств
{ }IiMM i ∈= , , где М — множество (объект) системы; I — множество
индексов; Мi — компоненты системы.
Тогда системой называется [4] отношение непустых (абстрактных)
множеств
{ }IiMS i ∈×⊂ , , (1)
где × — символ декартова произведения.
Важным классом отношений (1) являются двухместные или бинарные
отношения. Отношение (1) в этом случае приобретает вид
21 MMS ×⊂ . (2)
Именно отношение (2) может быть положено в основу определения графа.
Граф G всегда можно представить двумя взаимосвязанными
множествами абстрактных объектов. Одно из них — множество Х
изолированных вершин, другое — множество V звеньев (если звено графа
неориентировано — оно называется ребром, если ориентировано — дугой).
Множества Х и V будем называть графообразующими. Под определением
графообразующих множеств будем понимать перечисление (перенумерацию)
всех его элементов. Определяя графообразующие множества (или одно из
них) и отношения (1) на их декартовом произведении, мы можем дать
теоретико-множественное определение графа.
Практическое значение имеют два способа определения графа:
Построение и структура моделирующих графов сложных систем.
Системні дослідження та інформаційні технології, 2002, 2 121
1) в отношении (2) определяются два графообразующих множества
XM =1 ; VM =2 ;
2) в отношении (2) определяется одно графообразующее множество
XMM == 21 .
В соответствии с этим можно дать два определения графа.
Определение 1. Графом G называется отношение на декартовом
произведении непустого множества Х вершин и непустого множества V
звеньев, т.е.
VXG ×⊂ . (3)
Декартово произведение в отношении (3) представляет собой
множество всех упорядоченных пар элементов вида ),( vx при условии, что
VvXx ∈∈ ; , т.е.
( ){ } .,,, VvXxvxVX ∈∈=× (4)
Если положить, что ZX ⊂ и ZV ⊂ , где Z — множество целых чисел,
то декартово произведение (4) можно наглядно представить точками ),( ijx ν ,
VvXx ij ∈∈ ; в узлах координатной сетки, образующей множество
( ){ } .,1;,1,, minjvx ij == (5)
При конечных графообразующих множествах мощность множества (4) или
(5) численно равна произведению мощностей графообразующих множеств, т.е.
,nmVXVX ⋅=⋅=× (6)
где n — количество вершин графа; m — количество звеньев графа.
Выясним, какова мощность множества (3). В графе G без петель каждое
звено Vvi ∈ инцидентно двум различным вершинам ;Xxk ∈ ,Xxl ∈ lk ≠ .
Тогда звену vi могут быть поставлены в соответствие две различные пары
),( kjx ν и ),( ljx ν элементов бинарного отношения (3), определяющего
граф G.
Отсюда следует, что мощность множества (3) определяется удвоенной
мощностью множества V звеньев графа G, т.е.
,22 mVG xv == (7)
где xvG — мощность отношения (3) декартового произведения множеств
Х и V.
Определение 2. Графом G называется бинарное отношение на
декартовом произведении непустого множества Х вершин на это же
множество, т.е.
А.А. Волков
ISSN 1681–6048 System Research & Information Technologies, 2002, 2 122
.XXG ×⊂ (8)
Декартово произведение в отношении (8) представляет собой
множество всех упорядоченных пар элементов вида ),( kj xx nkj ,1, = при
условии, что Xxx kj ∈, , т.е.
( ){ } nknjxxXX kj ,1,,1,, ===× . (9)
Мощность множества (9) численно равна квадрату мощности
множества Х, т.е.
.22 nXXX ==× (10)
Отношение (8) представляет собой подмножество декартового
произведения (9). Выясним, какова его мощность. Предположим, что
неориентированный граф G (обозначим его Gн) не имеет петель и кратных
звеньев. Тогда каждому его ребру mivi ,1, = могут быть поставлены в
соответствие две пары смежных вершин: ),( lk xx и ),( jl xx . Отсюда
следует, что мощность множества (2), определяющего граф Gн , будет
.22 mVGн == (11)
Если граф ориентирован (обозначим его G0), то каждой его дуге
mivi ,1, = ставится в соответствие только одна пара смежных вершин
),( lk xx , где хk — начало дуги; хl — конец дуги. Мощность множества (8)
для такого графа будет в два раза меньше, чем для графа нG , т.е.
.mVGо == (12)
Сравнивая соотношения (11) и (12), приходим к выводу, что введение
такой информации, как ориентация дуг на графе, позволяет в два раза
уменьшить мощность множества (8), определяющего граф G.
3. СПОСОБЫ ЗАДАНИЯ ГРАФОВ МНОЖЕСТВАМИ ИНЦИДЕНТНОСТИ
Графы могут быть заданы множествами или матрицами. Матричный способ
исторически возник первым. Так, еще в 1877 г. Кирхгоф установил
закономерность течения постоянного электрического тока, где структура
разветвленных цепей задавалась матрицами инцидентности (инциденций)
вершин и звеньев.
Рассмотрим способы задания графов, которые основываются на
отношении (3). Пусть в конечном графе G без петель и параллельных
звеньев определены его графообразующие множества: множество вершин
}{ jxX = , ,nj 1= и множество звеньев }{ ivV = , .,1 mi = Отношение
соответствия элементов этих множеств определяются матрицей инцидентности
Построение и структура моделирующих графов сложных систем.
Системні дослідження та інформаційні технології, 2002, 2 123
|||| jia , имеющей n строк и m столбцов. Строки соответствуют вершинам
графа, а столбцы — звеньям (ребрам, дугам).
Если граф не ориентирован, то элементы матрицы |||| jia определяются
следующим образом: 1=jia , если ребро iv инцидентно вершине jx , 0=ija
в противном случае. Если граф ориентирован, то элементы инцидентности
матрицы |||| jia находятся так: 1−=jia если вершина jx является началом
дуги iv , 1=jia , если вершина jx является концом дуги iv ; 0=jia , если
дуга iv неинцидентна вершине jx .
Заметим, что как для неориентированного, так и для ориентированного
графов, в каждом столбце матрицы инцидентности |||| jia содержится
только два отличных от нуля элемента и, следовательно, матрица содержит
большое количество нулей. При исследовании моделирующих графов
больших размерностей с использованием ЭВМ возникает проблема
больших слабозаполненных матриц инцидентности. Она обусловлена,
прежде всего, значительной трудоемкостью ввода информации и
неэффективностью использования памяти ЭВМ, значительными трудностями
топологического анализа графа и решения других задач исследования
систем.
Возникает необходимость поиска более эффективных способов задания
графов. Одним из них оказался способ задания графов множествами
инцидентности (инциденций) или множествами сечений. Этот способ в
первоначальном варианте был обоснован автором в 1966 г. [5] и нашел
применение в различных областях, в частности при топологическом анализе
шахтных вентиляционных сетей [6].
Способ задания графов множествами инцидентности или множествами
сечений [7] естественным образом вытекает из определения графа G
отношением (3).
Сечение отношения (3), обозначенное )( jxG , есть множество Vvi ∈
таких звеньев, что Gx ij ∈),( ν . Иначе скажем так : каждой вершине Xx j ∈
графа G можно поставить в соответствие сечения )( jxG отношения (3),
представляющее собой множество }{ iv jIi∈ инцидентных jx звеньев
такое, что { } GIix jij ⊂∈|),( ν .
Сечения }{)( ijj vYxG == , jIi∈ назовем множеством инцидентностей,
где I j — подмножество индексов, которыми помечены звенья графа,
инцидентные вершине jx , ,II j ⊂ },...,1{ mI =
Множество сечений отношения (3), обозначаемое ]}{[)( jij vxXGY •== ,
nj ,1= , иначе называется семейством множеств инциденций. Оно полностью
определяет граф. Рассмотрим конкретный пример задания графа семейством
множеств инциденций (множеством сечений).
А.А. Волков
ISSN 1681–6048 System Research & Information Technologies, 2002, 2 124
Пусть дан неориентированный граф (неограф) G (рис. 1), образо-
ванный множеством },,,{ 4321 xxxxX = вершин и множеством
},,,,,{ 654321 vvvvvvV = ребер.
Декартово произведение (4) для этого графа представляется в виде:
., i;,; jv,xVX ij 6141}{ ===× (13)
Отношение (3) является подмножеством множества (13), т.е.
),v,(x),v,(x),v,(x),v,(x),v,(x),v,{(x 423212612111=G
)}v,(x),v,(x),v,(x),v,(x),v,(x),v,(x 645444533323 . (14)
На рис. 2 это отношение задано табличным способом [7].
Здесь вертикали соответствуют звеньям Vvi ∈ , а горизонтали —
вершинам Xx j ∈ , затемненными кружками в узлах координатной сетки
отмечены инциденции вершин и ребер, а сечения G(x1), G(x2), G(x3), G(x4)
отмечают на каждой горизонтали jx множество инцидентных ребер.
Множество сечений G(X) отношения (14) полностью определяет граф G и
представляет собой семейство Y множеств инциденций:
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
==
}6,5,4{
}5,3,2{
}4,3,1{
}6,2,1{
}{
}{
}{
}{
)(
)(
)(
)(
)(
654
532
431
621
4
3
2
1
,v,vv
,v,vv
,v,vv
,v,vv
xG
xG
xG
xG
XGY . (15)
С определением графа G при помощи графообразующих множеств X и
V непосредственно связан способ задания графа матрицами инцидентности
и множествами инциденций.
Для рассматриваемого неориентированного графа матрица инциденций,
строки которой соответствуют вершинам jx , 4,1=j , а столбцы — ребрам
iv , 6,1=j , имеет вид
v6
x3
v2
x1 x4
v5
v4
x2
v3
v1
Рис. 1
v1 v2 v3 v4 v5 v6
x1
x2
x3
x4
G(x1) = {v1,v2,v6}
G(x2) = {v1,v3,v4}
G(x3) = {v2,v3,v5}
G(x4) = {v4,v5,v6}
Рис. 2
Построение и структура моделирующих графов сложных систем.
Системні дослідження та інформаційні технології, 2002, 2 125
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
==
111000
010110
001101
100011
j iaA . (16)
Множество инциденций (15) может быть получено в результате
умножения матрицы (16) A на вектор-столбец V упорядоченных ребер графа
и последующего исключения из результирующей матрицы *A нулевых
элементов, т.е.
YAVA →=⋅ * . (17)
Для данного примера имеем
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
→
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
⋅
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
}{
}{
}{
}{
000
000
000
000
111000
010110
001101
100011
654
532
431
621
654
532
431
621
6
5
4
3
2
1
,v,vv
,v,vv
,v,vv
,v,vv
vvv
vvv
vvv
vvv
v
v
v
v
v
v
.
Произвольная строка матрицы (16) является избыточной и ее можно
исключить без потери информации о топологической структуре графа.
Заметим, что количество элементов матрицы (16) равно мощности
декартового произведения (13), для данного графа 24=nm . Количество же
элементов семейства множеств инциденций (15) равно мощности
подмножества декартового произведения (14), для данного графа 122 =m .
Сравнивая между собой способы задания графов матрицей и множествами
инциденций, можно сделать вывод, что последний более эффективен. Для
ориентированного графа, показанного на рис 3, отношения (3) графически
интерпретируются таблицей на рис. 4.
Здесь затемненными кружками обозначены узлы координатной сетки, в
которых вершины jx являются началом дуги iv , а незатемненными
кружками обозначены узлы, в которых jx являются концами дуги iv .
v1 v2 v3 v4 v5 v6
x1
x2
x3
x4
G(x1) = {v1,v2,-v6}
G(x2) = {-v1,v3,v4}
G(x3) = {-v2,-v3,v5}
G(x4) = {-v4,-v5,v6}
Рис. 4
v1
v2
v3
v5
v4
v6
x2
x3
x4
Рис. 3
x1
А.А. Волков
ISSN 1681–6048 System Research & Information Technologies, 2002, 2 126
Семейство Y множеств инциденций ориентированного графа (или
множество сечений )(XG ) может быть представлено в виде
⎥⎦
⎤
⎢⎣
⎡ ∈⋅×= jiij IivvxY }sign{ , nj ,1= , (18)
где
⎪⎩
⎪
⎨
⎧
−
=
.концомявляетсяесли,1
,началомявляетсяесли,1
sign
ij
ij
i vx
vx
v
Если в выражении (18) опустить jx и в дальнейшем оставить только
номера дуг, то для рассматриваемого орграфа семейство множеств
инциденций будет :
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
−−
−−
−
−
=
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
−−
−−
−
−
=
6}5,4,{
5}3,2,{
4}3,1,{
6}2,{1,
},,{
},,{
},,{
},,{
654
532
431
621
vvv
vvv
vvv
vvv
Y .
Как и для неографа, семейство множеств инциденций орграфа может
быть получено с использованием соотношения (17).
4. СПОСОБЫ ЗАДАНИЯ ГРАФОВ МНОЖЕСТВАМИ СМЕЖНОСТИ ВЕРШИН
Задание графов множествами смежности вершин базируется на отношении
(8) и выражается матрицами смежности и множествами смежности.
Матрица смежности вершин представляет собой прямоугольную таблицу,
строкам и столбцам которой поставлены в соответствие вершины графа.
Элемент на пересечении j-й строки и i-го столбца этой матрицы равен числу
ребер, инцидентных одновременно j-й и i-й вершинам для
неориентированного мультиграфа (или равен единице, если граф не
содержит кратных ребер). Если мультиграф ( или граф без кратных дуг)
ориентирован, то элемент на пересечении j-й строки и i-го столбца этой
матрицы равен числу дуг, направленных от вершин j к вершине i ( или
единице для графа без кратных дуг).
Для неографа, показанного на рис. 5, матрица смежности имеет вид :
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
0111
1011
1101
1110
нB .
Для орграфа, показанного на рис 7, эта матрица будет
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
0001
1000
1100
0110
оB .
Построение и структура моделирующих графов сложных систем.
Системні дослідження та інформаційні технології, 2002, 2 127
Заметим, что количество элементов каждой из этих матриц смежности
n2 = 16.
Множество R смежности вершин, определяющее неориентированный
связный граф нG без петель, можно построить, исходя из следующих
рассуждений. Для каждой вершины njx j ,1, = существует множество
{ }kj xx =Γ смежных вершин, т.е. таких, которые порождают смежное вершине
xj множество упорядоченных пар }),,{( jKKj xxxx Γ∈ .
Следовательно, для всего множества вершин njx j ,1, = образуется
семейство R множеств смежности njxxxxR jKKj ,1},),,{( =Γ∈= .
Мощность множества R можно определить из следующих
рассуждений. Для неориентированного графа нG без петель существует
пара нKJ Rxx ∈),( , причем каждая пара ),( kj xx и ),( jk xx определяет одно
и тоже звено nivi ,1, = графа нG . Отсюда следует, что мощность
множества нR равна удвоенному количеству звеньев графа mRн 2|| = .
Для ориентированного графа оG без кратных дуг для каждой пары
оkj Rxx ∈),( не существует обратной пары, оjk Rxx ∉),( . Мощность мно-
жества mRо = . Отсюда следует, что семейством множеств смежности
более выгодно задавать ориентированные графы.
Рассмотрим теперь конкретные примеры задания графов семействами
множеств смежности (множествами смежности). Для неориентированного
графа, показанного на рис 5, отношение (2) представляется следующим
множеством упорядоченных пар смежных вершин
),,(),,(),,(),(),,(),{( 4232124,1312,1 xxxxxxxxxxxxRн =
)}.,(),,(),,(),(),,(),( 3424144,3231,3 xxxxxxxxxxxx (19)
Мощность этого множества 122|| == mRн .
На рис. 6 множество (19) задается таблицей, где элементам этого
множества соответствуют затемненные кружки в узлах координатной сетки.
x1
x2
x3
x4
x1 x2 x3 x4
G(x1) = {x2,x3,x4}
G(x2) = {x1,x3,x4}
G(x3) = {x1,x2,x4}
G(x4) = {x1,x2,x3}
Рис. 6
x3
x1 x4
x2
Рис. 5
А.А. Волков
ISSN 1681–6048 System Research & Information Technologies, 2002, 2 128
Соотношение (19) можно представить в виде эквивалентного ему
семейства множеств смежности
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
×
×
×
×
=
}321{
}421{
}431{
}432{
}{
}{
}{
}{
3214
4213
4312
4321
,,
,,
,,
,,
x,x,xx
x,x,xx
x,x,xx
x,x,xx
YR .
Для ориентированного графа, представленного на рис 7, отношение (8)
запишем в виде следующего множества упорядоченных пар смежности
вершин:
.)},(),,(),,(),(),,(),{( 1443423,2312,1 xxxxxxxxxxxxRо = (20)
Мощность этого множества 6|| == mRо . На рис 8 множество (20)
задается таблицей, где элементам этого множества соответствуют кружки в
узлах координатной сетки.
Отношение (20) можно представить в виде эквивалентного ему
семейства множеств смежности
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
×
×
×
×
=
}1{
}4{
}43{
}32{
}{
}{
}{
}{
14
43
432
321
,
,
xx
xx
,xxx
,xxx
YR .
Оценивая по критерию минимума требуемого объема информации для
задания графов при помощи семейства множеств смежности и матрицы
смежности, мы приходим к выводу о предпочтительности их задания
семейством множеств смежности.
Таким образом, теоретико-множественное задание моделирующих
графов при помощи множеств инцидентности или множеств смежности
предпочтительнее задания графов матричными способами.
Рис. 8
x1
x2
x3
x4
x1 x2 x3 x4
G(x1) = {x2,x3}
G(x2) = {x3,x4}
G(x3) = {x4}
G(x4) = {x1}
x3
x1 x4
x2
Рис. 7
Построение и структура моделирующих графов сложных систем.
Системні дослідження та інформаційні технології, 2002, 2 129
5. ОБОБЩЕННАЯ ТОПОЛОГИЧЕСКАЯ МОДЕЛЬ СИСТЕМЫ
Теоретико-множественная модель абстрактной системы или модель общей
теории систем и концепция моделирующих графов позволяют получить
такую обобщенную модель сложной сетевой системы, которая обладает
возможностью построения на ее основе совокупности целенаправленных
моделей, обладающих достаточной степенью детализации. Такую модель
можно назвать обобщенным моделирующим графом системы.
Построение этой модели основывается на конкретизации абстрактных
множеств или объектов системы niM i ,1, = теоретико-множественной
модели, представленной соотношением (1). При такой конкретизации
декартово произведение
{ }IiM i ∈× , (21)
в правой части отношения (1) может быть декомпозировано и представлено
некоторым семейством декартовых произведений множеств Мi путем
разбиения множества I.
Пусть, например, множество I разбивается на N непустых попарно не
пересекающихся подмножеств JjII j ∈⊂ , таких, что
а) ∅=kj II ∩ для всякой пары различных индексов ( );kj ≠
б) ∪
N
j
j II
1
.
=
=
Тогда можно определить следующее биективное (взаимооднозначное)
отображение, называемое каноническим:
{ } { }{ }IIIiAIiM jjii ∈∈×⇒∈× ,,, . (22)
Таким образом, декартово произведение (21) множеств IiM i ∈, можно
декомпозировать и заменить другим декартовым произведением, где в
качестве сомножителей выступают декартовы произведения { ,iM× ,jIi∈
}II j ⊂ меньшей степени. Смысл отображения (21) состоит в том, что
исходные объекты системы IiM i ∈, объединяются по некоторым
семантическим признакам и их декартовы произведения могут
рассматриваться как новые обобщенные системные объекты Qj, ,Jj∈
NJ = уже не одноэлементных, а многоэлементных множеств, т.е.
проекции исходного произведения (21). Тогда теоретико-множественная
модель системы (1) будет представляться отношением
{ }JjQS j ∈×⊂ ,' , (23)
где { } .,,, NJIIIjMQ jjjj =⊂∈×⇔
Сформулируем основные предпосылки для конкретизации объектов
IiM i ∈, в выражениях (1) и (21) при построении обобщенной топологической
А.А. Волков
ISSN 1681–6048 System Research & Information Technologies, 2002, 2 130
модели системы. Системные объекты Qj должны удовлетворять следующим
требованиям:
• объекты IiM i ∈, могут отображать как данные, так и знания о
структуре и элементах системы;
• объекты IiM i ∈, могут быть изначально как полностью опреде-
ленными, так и совсем не определенными, а определяться в процессе
моделирования;
• объекты IiM i ∈, могут отображать модели, алгоритмы и
программные модули для определения других объектов (множеств) и
управления процессом моделирования в интерактивном режиме;
• полный набор объектов IiM i ∈, является конечным, но не
фиксированным и может быть при необходимости расширен. Этим
достигается гибкость модели, возможность ее совершенствования и
развития.
С учетом сформулированных требований выделим следующие семейства
исходных множеств },{ IiM i ∈ .
1. Множества, определяющие топологическую структуру моделируемой
сетевой системы (графообразующие множества).
2. Множество последовательных и параллельных фундаментальных
переменных и операторов связи между ними, которые ставятся в
соответствие каждому звену моделирующего графа.
3. Множества, определяющие линейно независимые векторы
последовательных и параллельных фундаментальных переменных,
удовлетворяющих первому и второму постулатам.
4. Множества алгоритмов и программных модулей для топологического
анализа моделирующего графа, идентификации операторов его звеньев,
расчета распределения последовательных переменных в звеньях (потоков
сети) при различных исходных данных.
5. Множества алгоритмов и программных модулей для управления
процессом распределения последовательных переменных (потоков) в
звеньях моделирующего графа при различных исходных данных.
6. Множества параметров и экспериментальных статистических данных,
характеризующих техническое состояние сетевой системы и ее элементов.
7. Множества алгоритмов и программных модулей для оценки и
анализа технического состояния моделируемой сетевой системы.
Выделение семейства исходных множеств или объектов системы
позволяет представить ее в виде следующей обобщенной топологической
модели (обобщенного моделирующего графа):
,...21 nQQQS ×××⊂
где { } njIIIiAQ jjii ,1,,, =⊂∈×= .
Обобщенная топологическая модель может быть основой построения
базы данных и знаний интеллектуальных информационных систем и
технологий.
Построение и структура моделирующих графов сложных систем.
Системні дослідження та інформаційні технології, 2002, 2 131
ВЫВОДЫ
На основании анализа и обобщения работ в области моделирования
сложных сетевых систем обоснована концепция моделирования систем
графами.
Основываясь на общем теоретико-множественном представлении
обоснованы способы определения топологической структуры графов как
бинарных отношений на декартовом произведении непустых графооб-
разующих множеств — вершин и звеньев. Обоснованы способы задания
топологической структуры графов множествами инциденций вершин и
звеньев и множествами смежности вершин. Определена связь различных
способов задания графов множествами и матрицами, а также их
эфективность.
Моделирующий граф системы представляется в виде совокупности
полюсных уравнений отдельных ее компонент и математического описания
порядка их соединения, определяемого графом. Необходимым условием
такого подхода является обобщенная трактовка физических переменных,
входящих в уравнения компонент, которые подразделяются в зависимости
от способа их измерения на последовательные и параллельные фундаментальные
переменные, и подчинении этих переменных внутрисистемным законам
сохранения — двум основным постулатам для узлов и циклов
моделирующего графа. Рассмотрена обобщенная топологическая модель и
обобщенный моделирующий граф системы.
Построение этой модели основывается на конкретизации и
агрегировании (или обобщении) абстрактных множеств или объектов
теоретико-множественной модели системы. Смысл агрегирования состоит в
том, что исходные системные объекты объединяются по некоторым
семантическим признакам и их декартовы произведения могут рассматриваться
как новые обобщенные системные объекты уже не одноэлементных, а
многоэлементных множеств. Степень декартового произведения обобщенной
теоретико-множественной модели при этом снижается.
Сформулированы основные предпосылки для конкретизации и
обобщения исходных абстрактных объектов системы при построении
обобщенной топологической модели системы. Обобщенная топологическая
модель или обобщенный моделирующий граф системы может служить
основой построения базы данных и базы знаний информационных систем и
интеллектуальных информационных технологий.
ЛИТЕРАТУРА
1. Кениг Г., Блекуэлл В. Теория электромеханических систем. — М.-Л.:Энергия,
1965. — 424 с.
2. Денисов А.А. Основы теории информационных сетей. — Л.:Изд-во Ленинград.
политехн. ин-та,1977. — 48 c.
3. Волков А.А. Моделирование систем графами // Вісн. КМУЦА. 1998. — № 1. —
С. 268–279.
4. Месарович М., Такахара Я. Общая теория систем: математические основы. —
М.:Мир, 1978. — 311 с.
А.А. Волков
ISSN 1681–6048 System Research & Information Technologies, 2002, 2 132
5. Волков А.А. Многозначное отображение множества дуг графа как метод
изоморфного отображения топологии сети // Научно-техн. конф.,
посвященная дню радио. Секция техн. кибернетики. — Харьков:
ХИГМАВТ, 1966. — С. 8–12.
6. Волков А.А., Евдокимов А.Т. Волколупова Р.Т. Топологический анализ шахтных
вентиляционных сетей // Изв. высш. уч. заведений. Горный журнал
МВССО СССР. — 1967. — № 1. — С. 66–75.
7. Фор Р., Кофман А., Дени-Папен М. Современная математика — М.: Мир, 1966.
— 271 с.
Поступила 7.06.2002
|
| id | nasplib_isofts_kiev_ua-123456789-50228 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-12-07T15:47:22Z |
| publishDate | 2002 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Волков, А.А. 2013-10-07T19:39:48Z 2013-10-07T19:39:48Z 2002 Построение и структура моделирующих графов сложных систем / А.А. Волков // Систем. дослідж. та інформ. технології. — 2002. — № 2. — С. 118-132. — Бібліогр.: 7 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50228 007:681.3.06:519.17.007.57(045)+ На базе общей теоретико-множественной модели системы обоснована концепция моделирующего и обобщенного моделирующего графов сложных систем как основы построения баз данных и знаний интеллектуальных информационных систем. Рассмотрены способы задания структуры графов множеством инцидентности и смежности и оценивается их эффективность. На базі загальної теоретико-множинної моделі системи обгрунтована концепція моделюючого і узагальненого моделюючого графів складних систем як основи побудови баз даних та знань інтелектуальних інформаційних систем. Розглянуті засоби задання структури графів множинами інцидентності та суміжності і оцінюється їх ефективність. A concept of modeling and geleralized modeling graph of complex systems is proved on the basis of common model of system as a base for building data bases and the knowledge base of intellectual information system. Setting of graphs structure by incedenity and contiguity sets is reviewed and their effectiveness is estimated. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Математичні методи, моделі, проблеми і технології дослідження складних систем Построение и структура моделирующих графов сложных систем Побудова та структура моделюючих графів складних систем Construction of complex system modeling graphs and their structure Article published earlier |
| spellingShingle | Построение и структура моделирующих графов сложных систем Волков, А.А. Математичні методи, моделі, проблеми і технології дослідження складних систем |
| title | Построение и структура моделирующих графов сложных систем |
| title_alt | Побудова та структура моделюючих графів складних систем Construction of complex system modeling graphs and their structure |
| title_full | Построение и структура моделирующих графов сложных систем |
| title_fullStr | Построение и структура моделирующих графов сложных систем |
| title_full_unstemmed | Построение и структура моделирующих графов сложных систем |
| title_short | Построение и структура моделирующих графов сложных систем |
| title_sort | построение и структура моделирующих графов сложных систем |
| topic | Математичні методи, моделі, проблеми і технології дослідження складних систем |
| topic_facet | Математичні методи, моделі, проблеми і технології дослідження складних систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50228 |
| work_keys_str_mv | AT volkovaa postroenieistrukturamodeliruûŝihgrafovsložnyhsistem AT volkovaa pobudovatastrukturamodelûûčihgrafívskladnihsistem AT volkovaa constructionofcomplexsystemmodelinggraphsandtheirstructure |