Метод зменшення числа триреберних циклів для лінійних нерівностей зі структурою графа
At the decision of linear inequalities with the column structure by process of elimination of unknown persons there are the difficulties connected to presence of cycles in the column. The method of reduction of cycles is offered in the article. The algorithm of three-costal cycles finding is describ...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Online Zugang: | https://journal.iasa.kpi.ua/article/view/171357 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1866302415382249472 |
|---|---|
| author | Klimenko, V. M. Ostapenko, V. V. Ostapenko, O. S. Finin, G. S. |
| author_facet | Klimenko, V. M. Ostapenko, V. V. Ostapenko, O. S. Finin, G. S. |
| author_sort | Klimenko, V. M. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-06-24T16:34:27Z |
| description | At the decision of linear inequalities with the column structure by process of elimination of unknown persons there are the difficulties connected to presence of cycles in the column. The method of reduction of cycles is offered in the article. The algorithm of three-costal cycles finding is described. |
| first_indexed | 2025-07-17T10:25:17Z |
| format | Article |
| fulltext |
© В.М. Клименко, В.В. Остапенко, О.С. Остапенко, Г.С. Финин, 2005
Системні дослідження та інформаційні технології, 2005, № 1 113
TIДC
МАТЕМАТИЧНІ МЕТОДИ, МОДЕЛІ,
ПРОБЛЕМИ І ТЕХНОЛОГІЇ ДОСЛІДЖЕННЯ
СКЛАДНИХ СИСТЕМ
УДК 518.9
МЕТОД УМЕНЬШЕНИЯ ЧИСЛА ТРЕХРЕБЕРНЫХ ЦИКЛОВ
ДЛЯ ЛИНЕЙНЫХ НЕРАВЕНСТВ СО СТРУКТУРОЙ ГРАФА
В.М. КЛИМЕНКО, В.В. ОСТАПЕНКО, О.С. ОСТАПЕНКО, Г.С. ФИНИН
Решение линейных неравенств со структурой графа методом исключения не-
известных усложняется при наличии циклов в графе. Предлагается метод
уменьшения числа трехреберных циклов. Описан алгоритм их нахождения.
ВВЕДЕНИЕ
В статье предлагается метод замены исходной системы неравенств новой,
структура которой описывается графом, отличающимся от исходного тем,
что все трехреберные циклы в нем заменены подграфами, имеющими вид
трехлучевой звезды.
Теория потоков в сетях с обобщенным законом Кирхгофа моделирует
такие важные прикладные процессы, как управление транспортом различ-
ных ресурсов, например, воды в каналах оросительных систем, газа и нефти
в магистральных трубопроводах [1–4].
Разрабатываемые в последнее время основные подходы к решению
этих задач базируются на методах исключения неизвестных из системы ли-
нейных неравенств [4–9]. Однако численным методам решения уделялось
недостаточно внимания, и на сегодняшний день до конца разрешены только
отдельные конкретные задачи [4, 6–9].
Рассмотренная в данной статье математическая проблема возникла при
решении практических задач управления транспортными сетями, имеющи-
ми структуру графа [4, 6–9].
В работах [4, 5, 9] показано, что если неизвестный поток протекает по
концевому или промежуточному ребру, то при его исключении получаем
новую систему неравенств с меньшим числом неравенств, чем исходная, но
также со структурой графа. Причем новый граф получается из исходного
стягиванием соответствующего ребра. Таким образом, актуальной является
задача отыскания концевых и промежуточных ребер [4, 10].
В работе [4] показано, что если граф имеет только один цикл, то, по-
следовательно исключая потоки, протекающие по концевым, а затем по
промежуточным ребрам, можно полностью решить задачу отыскания реше-
ния исходной системы неравенств. Если граф содержит большое число цик-
В.М. Клименко, В.В. Остапенко, О.С. Остапенко, Г.С. Финин
ISSN 1681–6048 System Research & Information Technologies, 2005, № 1 114
лов, то приходится использовать достаточно громоздкий общий метод ис-
ключения неизвестных из системы неравенств [5].
Наличие в исходном графе G различных циклов — наибольшая труд-
ность в численном решении задач, связанных с управлением и распределе-
нием ресурсов в сетях.
МЕТОД ЗАМЕНЫ ГРАФА. ОСНОВНЫЕ ТЕОРЕМЫ
Цель статьи — реализация метода, позволяющего заменить исходный граф
G графом G′ c меньшим количеством циклов. Рассмотрим случай цикла C
из трех ребер («треугольник») и докажем, что исходный «треугольник» C
можно заменить графом H , имеющим вид трехлучевой звезды. При этом из
системы неравенств, соответствующей графу G′ , вытекает система нера-
венств, соответствующая графу G .
Пусть },{ EVG = — неориентированный граф, где V — множество
вершин; E — множество ребер. Обозначим }),(:{)( EbaVbaN ∉∈= окре-
стность вершины Va∈ .
Рассмотрим систему линейных неравенств, которая имеет структуру
графа
nk jji VVV ,, , (1)
EjiBx ijij ∈∈ ),(, , (2)
jiij xx = .
Здесь iA и ijB — отрезки. Кроме того, считаем, что выполняется усло-
вие jiij xx = . Таким образом, ijx является величиной потока, а ija опреде-
ляет его направление.
Пусть существует подграф
описанного графа, имеющий вид
треугольника (рис. 1), вершины ко-
торого обозначим cba ,, ; ребра,
соответственно, bcxx = , acxy = ,
abxz = .
Дадим локальное описание сис-
темы (1), (2) в окрестности треуголь-
ника cba ,, .
Предположим, что
aAzyp ∈−+ )(1 , (3)
bAxzp ∈−+ )(2 , (4)
cAyxp ∈−+ )(3 , (5)
Рис. 1. Исходный подграф
b
y z
x
a
с
Метод уменьшения числа трехреберных циклов для линейных неравенств …
Системні дослідження та інформаційні технології, 2005, № 1 115
где
∑
∈
=
},{\)(
1
cbaNj
ajaj xp α ,
∑
∈
=
},{\)(
2
cabNj
bjbj xp α ,
∑
∈
=
},{\)(
3
bacNj
cjcj xp α .
В исследуемом случае в выражениях (3),(4),(5) для коэффициентов α
справедливо следующее:
1,1 =−= cbbc αα ,
1,1 −== caac αα ,
1,1 =−= baab αα ,
]1,0[,, ∈zyx , (6)
т.е. ]1,0[=== abacbc BBB .
Обозначив zyu −= , xzv −= , yxw −= и произведя замену, из выра-
жений (3)–(6) получаем систему неравенств относительно u,v,w
aAup ∈+1 , (7)
bAvp ∈+2 , (8)
cAwp ∈+3 , (9)
0=++ wvu , (10)
]1,1[,, −∈wvu . (11)
Новая система неравенств, в которой неравенства (3)–(5) заменены
(7)–(10), а (6) неравенством (11) имеет структуру нового графа G′ , в кото-
ром треугольник },,{ cba заменен звездой },,,{ dcba (рис. 2).
В новом графе G′ неравенству (10)
соответствует вершина d . В новую сис-
тему неравенств входят параметры ijx ,
где { }),(),,(),,(\),( cacbbaEji ∈ , и пара-
метры wvu ,, .
Из приведенного построения следует
Теорема 1. Пусть исходная система
неравенств (1), (2) имеет решение ijx ,
Eji ∈),( . Тогда для новой системы
{ }),(),,(),,(\),(, cacbbaEjixij ∈ ,
yxwxzvzyu −=−=−= ,, .
Рис. 2. Замена исходного подграфа
a
c b
В.М. Клименко, В.В. Остапенко, О.С. Остапенко, Г.С. Финин
ISSN 1681–6048 System Research & Information Technologies, 2005, № 1 116
Основной является
Теорема 2. Пусть { }),(),,(),,(\),(, cacbbaEjixij ∈ и wvu ,, — решения
новой системы неравенств, тогда существуют такие zyx ,, , что ijx ,
Eji ∈),( являются решением исходной системы (1), (2).
Доказательство. Из равенства (10) следует, что хотя бы одна из неиз-
вестных wvu ,, должна быть неотрицательной. Рассмотрим все возможные
случаи.
1. Пусть для определенности 0≥u . Тогда из принятых обозначений
следует, что ]1;0[, ∈zy . В этом случае 0≤+ wv . Если 0≤v , то получаем
]1;0[;0 ∈= zz ,
]1;0[,; ∈= uyuy ,
]1;0[,; ∈−−= xvvx .
Если 0≥v , то 0≤w . В этом случае
]1;0[;0 ∈= xx ,
]1;0[,; ∈= vzvz ,
]1;0[,; ∈−−= ywwy .
2. Допустим, 0≥v . Очевидно, что ]1;0[, ∈xz и 0≤+ vu . Если 0≤u , то
получаем
]1;0[;0 ∈= yy ,
]1;0[,; ∈= wxwx ,
]1;0[,; ∈−−= zuuz .
Если 0≥u , то 0≤w . Тогда
]1;0[;0 ∈= xx ,
]1;0[,; ∈= vzvz ,
]1;0[,; ∈−−= ywwy .
3. Допустим, 0≥w . Очевидно, что ]1;0[, ∈xz и 0≤+ vu . Если 0≤u ,
то получаем
]1;0[;0 ∈= yy ,
]1;0[,; ∈= wxwx ,
]1;0[,; ∈−−= zuuz .
Метод уменьшения числа трехреберных циклов для линейных неравенств …
Системні дослідження та інформаційні технології, 2005, № 1 117
Если 0≥u , то 0≤v . Тогда
]1;0[;0 ∈= zz ,
]1;0[,; ∈= uyuy ,
]1;0[,; ∈−−= xvvx .
Замечание 1. Для циклов, имеющих четыре и больше ребер, теорема 2
несправедлива.
АЛГОРИТМ ПОИСКА ЦИКЛА, СОСТОЯЩЕГО ИЗ ТРЕХ РЕБЕР
Допустим, связный граф G задан матрицей отношений (инцидентности) B .
Матрица B задана таким образом, что если вершины графа i и j соедине-
ны ребром iju , то элемент матрицы ijb ( jib )равен единице, и если вершины
не соединены ребром, то соответствующий элемент матрицы B равен нулю.
Выведем критерий наличия в графической структуре цикла, содержа-
щего три вершины («треугольник»).
Пусть связный граф G имеет v вершин и u ребер. Очевидно, если
vu ≥ , то граф содержит циклы. Применительно к матрице отношений это
заключение выглядит следующим образом: если сумма единичных элемен-
тов матрицы отношений больше или равна сумме строк и столбцов этой
матрицы, то связный граф G , описанный этой матрицей, имеет циклы.
Пусть в i -й строке матрицы отношений B есть элементы
1ijb и
2ijb ,
равные 1. Тогда для существования треугольного цикла достаточно, чтобы
матрица B содержала единичный элемент
21 jjb . В этом случае вершины i ,
21 , jj графа G будут заключены в треугольный цикл («треугольник»).
В работах [4, 10] приведены алгоритмы поиска концевых и промежу-
точных ребер графа. Опишем алгоритм поиска треугольных циклов в связ-
ном графе G по матрице отношений B .
Шаг 1. Проверка критерия наличия цикла vb
ijb ij 21 ≥∑ =
. Если крите-
рий выполнен, то шаг 2. Иначе: выход.
Шаг 2. Находим и вычеркиваем из матрицы все строки и столбцы, со-
держащие только один единичный элемент. Переходим к шагу 3.
Шаг 3. Если в матрице есть строки, содержащие ровно два единичных
элемента, то переходим к шагу 4. Иначе: шаг 5.
Шаг 4. Находим в полученной матрице первую строку, содержащую
ровно два единичных элемента
1ijb и
2ijb . Вычеркиваем i -й столбец и стро-
ку, проверяем элемент
21 jjb . Если 1
21
=jjb , то найден цикл 21 ,, jji . Пере-
ходим к шагу 1. Иначе: шаг 3.
Шаг 5. Для первой пары
kijb ,
nijb единичных элементов первой строки
матрицы, содержащей более двух единичных элементов, проверяем наличие
единичного элемента
nn jjb . Если 1=
nn jjb , то найден цикл nk jji ,, . Пере-
В.М. Клименко, В.В. Остапенко, О.С. Остапенко, Г.С. Финин
ISSN 1681–6048 System Research & Information Technologies, 2005, № 1 118
ходим к следующей паре единичных элементов. После завершения проце-
дуры для всех возможных пар единичных элементов строки вычеркиваем
эту строку и столбец с таким же индексом. Переходим к шагу 1.
Замечание 2. Данный алгоритм позволяет отыскать все треугольные
циклы.
ВЫВОДЫ
1. Обоснован способ решения системы линейных неравенств со струк-
турой графа путем замены исходной системы новой, которая также имеет
структуру графа. Новый граф отличается от исходного тем, что в нем цик-
лы, состоящие из трех ребер, заменяются подграфом в виде трехлучевой
звезды.
2. Приведен алгоритм нахождения трехреберных циклов.
Развитием данной статьи будет служить разработка методов замены
многореберных циклов на многолучевые звезды.
ЛИТЕРАТУРА
1. Остапенко В.В., Финин Г.С. Моделирование движения воды обобщенным за-
коном Кирхгофа // Проблемы управления и автоматики. — 1999. — № 4. —
С. 86–90.
2. Данильченко В.Е., Остапенко В.В., Яковлева А.П. Математические вопросы
моделирования и управления в задачах водораспределения / Ин-т ки-
бернетики им. В.М. Глушкова АН УССР. — Препр. — Киев, 1989. —
18 с.
3. Ostapenko V.V., Jakovleva A.P. Mathematical qustions of modeling and control wa-
ter distribution problem // Control and Cybernetics. — 1991. — 20, № 4. —
Р. 99–111.
4. Остапенко В.В., Скопецький В.В., Фінін Г.С. Розподіл ресурсів у просторі та
часі. — Київ: Наук. думка, 2003. — 323 с.
5. Черников С.Н. Линейные неравенства. — М.: Наука, 1968. — 488 с.
6. Остапенко В.В., Финин Г.С. Метод исключения неизвестных для систем
линейных неравенств со структурой графа // Кибернетика и системный ана-
лиз. — 1999. — № 5. — С. 66–74.
7. Остапенко В.В., Финин Г.С. Системы линейных неравенств со структурой бес-
конечного графа // Проблемы управления и автоматики. — 2000. — № 3. —
С. 86–90.
8. Остапенко В.В., Финин Г.С. Методы управления потоками в сетях с обобщен-
ным принципом сохранения // Математические машины и системы. —
2000. — № 2, 3. — С. 59–63.
9. Остапенко В.В., Финин Г.С. Методы исключения неизвестных из систем
линейных неравенств и их приложения // Український математичний жур-
нал. — 2001. — № 1. —С. 50–56.
10. Остапенко В.В., Финин Г.С., Ганошина И.Н. Стягивание дуг при решении сис-
темы линейных неравенств со структурой графа // Кибернетика и систем-
ный анализ. — 2000. — № 2. — С. 167–170.
Поступила 17.09.2003
|
| id | journaliasakpiua-article-171357 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:25:17Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/0e/8246a3498544f307c46be3a2ba06380e.pdf |
| spelling | journaliasakpiua-article-1713572019-06-24T16:34:27Z Method of reduction of number of three-costal cycles for linear inequalities with the column structure Метод уменьшения числа трехреберных циклов для линейных неравенств со структурой графа Метод зменшення числа триреберних циклів для лінійних нерівностей зі структурою графа Klimenko, V. M. Ostapenko, V. V. Ostapenko, O. S. Finin, G. S. At the decision of linear inequalities with the column structure by process of elimination of unknown persons there are the difficulties connected to presence of cycles in the column. The method of reduction of cycles is offered in the article. The algorithm of three-costal cycles finding is described. Решение линейных неравенств со структурой графа методом исключения неизвестных усложняется при наличии циклов в графе. Предлагается метод уменьшения числа трехреберных циклов. Описан алгоритм их нахождения. Розв’язання лінійних нерівностей зі структурою графа методом вилучення невідомих ускладнюється при наявності циклів у графі. Пропонується метод зменшення числа триреберних циклів. Наведено алгоритм їх знаходження. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-06-24 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/171357 System research and information technologies; No. 1 (2005); 113-118 Системные исследования и информационные технологии; № 1 (2005); 113-118 Системні дослідження та інформаційні технології; № 1 (2005); 113-118 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/171357/171012 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Klimenko, V. M. Ostapenko, V. V. Ostapenko, O. S. Finin, G. S. Метод зменшення числа триреберних циклів для лінійних нерівностей зі структурою графа |
| title | Метод зменшення числа триреберних циклів для лінійних нерівностей зі структурою графа |
| title_alt | Method of reduction of number of three-costal cycles for linear inequalities with the column structure Метод уменьшения числа трехреберных циклов для линейных неравенств со структурой графа |
| title_full | Метод зменшення числа триреберних циклів для лінійних нерівностей зі структурою графа |
| title_fullStr | Метод зменшення числа триреберних циклів для лінійних нерівностей зі структурою графа |
| title_full_unstemmed | Метод зменшення числа триреберних циклів для лінійних нерівностей зі структурою графа |
| title_short | Метод зменшення числа триреберних циклів для лінійних нерівностей зі структурою графа |
| title_sort | метод зменшення числа триреберних циклів для лінійних нерівностей зі структурою графа |
| url | https://journal.iasa.kpi.ua/article/view/171357 |
| work_keys_str_mv | AT klimenkovm methodofreductionofnumberofthreecostalcyclesforlinearinequalitieswiththecolumnstructure AT ostapenkovv methodofreductionofnumberofthreecostalcyclesforlinearinequalitieswiththecolumnstructure AT ostapenkoos methodofreductionofnumberofthreecostalcyclesforlinearinequalitieswiththecolumnstructure AT finings methodofreductionofnumberofthreecostalcyclesforlinearinequalitieswiththecolumnstructure AT klimenkovm metodumenʹšeniâčislatrehrebernyhciklovdlâlinejnyhneravenstvsostrukturojgrafa AT ostapenkovv metodumenʹšeniâčislatrehrebernyhciklovdlâlinejnyhneravenstvsostrukturojgrafa AT ostapenkoos metodumenʹšeniâčislatrehrebernyhciklovdlâlinejnyhneravenstvsostrukturojgrafa AT finings metodumenʹšeniâčislatrehrebernyhciklovdlâlinejnyhneravenstvsostrukturojgrafa AT klimenkovm metodzmenšennâčislatrirebernihciklívdlâlíníjnihnerívnostejzístrukturoûgrafa AT ostapenkovv metodzmenšennâčislatrirebernihciklívdlâlíníjnihnerívnostejzístrukturoûgrafa AT ostapenkoos metodzmenšennâčislatrirebernihciklívdlâlíníjnihnerívnostejzístrukturoûgrafa AT finings metodzmenšennâčislatrirebernihciklívdlâlíníjnihnerívnostejzístrukturoûgrafa |