=Paper=
{{Paper
|id=Vol-1787/423-427-paper-73
|storemode=property
|title=Методы эйлеровой аппроксимации графов в задаче мониторинга коммуникаций
(The eulerian graphs approximation methods for the problem of communications monitoring)
|pdfUrl=https://ceur-ws.org/Vol-1787/423-427-paper-73.pdf
|volume=Vol-1787
|authors=Alexander Rappoport
}}
==Методы эйлеровой аппроксимации графов в задаче мониторинга коммуникаций
(The eulerian graphs approximation methods for the problem of communications monitoring)==
https://ceur-ws.org/Vol-1787/423-427-paper-73.pdf
Методы эйлеровой аппроксимации графов в задаче
мониторинга коммуникаций
А. М. Раппопорт
Институт проблем передачи информации им. А.А. Харкевича
Российской академии наук
127051, г. Москва, Большой Каретный пер. д.19, стр.2
E-mail: ram43@mail.ru
Работа посвящена решению задачи организации эффективного мониторинга коммуникационных
систем на основе минимизации повторного обхода соединений. Одна из возможностей для его реализа-
ции состоит в построении ближайшей структуры, в которой такие повторы исключены, а именно эйлеро-
ва графа. Проведена классификация вершин исходного графа относительно наличия ребер между под-
множествами вершин с четными и нечетными степенями. Рассмотрены различные способы построения
аппроксимирующего графа, в первую очередь минимизирующие изменения в матрице смежности. Пред-
ложен эффективный метод преобразования исходного графа в эйлеров (полуэйлеров) с использованием
операций добавления и удаления ребер. Сформулированы условия возможности внутренней аппрокси-
мации, когда в результате последовательной процедуры удаления ребер получается эйлеров (полуэйре-
ров) граф.
Ключевые слова: оптимизация мониторинга коммуникаций, преобразование графа, реберные опе-
рации, эйлеров граф.
Финансовая поддержка: Грант Российского Фонда Фундаментальных Исследований № 16-07-00238А.
© 2016 Раппопорт Александр Моисеевич
423
Введение
При проведении мониторинга коммуникационных систем естественно пытаться исклю-
чить повторное прохождений соединений. Как известно, такая возможность является уникаль-
ной, т.к. означает эйлеровость соответствующего графа, что равносильно четности степеней
всех его вершин. Поэтому в общем случае оказывается целесообразным создание метода обхо-
да, в котором дублирование коммуникаций удается снизить. Один из таких подходов представ-
лен алгоритмом решения задачи о китайском почтальоне [Фляйшнер, 2002; Fleischner, 1991;
Кристофидес, 1978], минимизирующим такие повторы. Случай, когда учитывается только на-
личие соединений (без весов), рассмотрен в работе [Bellman, Cooke, 1969]. Другой подход со-
стоит в построении ближайшего аппроксимирующего эйлерова графа, чему и посвящена на-
стоящая статья. В ней излагаются некоторые способы решения этой задачи, использующие
операции добавления и удаления ребер в исходном графе. Предлагаются два эффективных ме-
тода, отличающихся последовательностью применяемых операций.
Постановка задачи и известные методы преобразования графов в
эйлеров
Пусть G (V , E ) – конечный связный граф, V - множество вершин, E – множество ребер (
V n, E m ). Множество V представимо в виде V V1 V2 , V1 n1 , V2 n2 , где V1 (V2 ) -
подмножество вершин с нечетными (четными) степенями. Обозначим G1 G1 (V1 , E1 ) ,
G2 G2 (V2 , E2 ) - подграфы на соответствующих подмножествах вершин. В общем случае,
как известно, n1 - четное число, а в эйлеровом графе n1 0 . Ищется эйлеров (полуэйлеров)
граф G G (V , E ) , минимизирующий хеммингово расстояние от исходного графа, т.е.
(G, G ) EE min .
Простейший, но не эффективный способ получения эйлерова графа из исходного, состоит
во введении новой вершины, смежной со всеми вершинами из V1 , что требует использования
n1 новых ребер. (Далее будем считать V V .)
Также, если допускаются кратные ребра, то при добавлении n1 / 2 попарно несмежных ре-
бер получим эйлеров граф.
В работе [Раппопорт, 2011] выделен ряд случаев, исключающих введение новой вершины
и позволяющих использовать меньшее число дополнительных ребер. В частности, в классах
двудольных графов с четными долями или неполных двудольных графов с нечетными долями
при добавлении минимального количества ребер, равного n1 / 2 , получается эйлеров граф.
В статье [Раппопорт, 2012] решается задача построения внешнего аппроксимирующего
графа, отличающегося от исходного новыми ребрами. Для этого предложена последовательная
процедура единичного увеличения степеней «нечетных вершин», которая за n1 / 2 операций
добавления ребер (без кратностей) преобразует исходный граф в эйлеров, если в результате ос-
тается пустой граф. Эта процедура основа на так называемом многодольном представлении ко-
нечного графа, хотя для получения аналогичного результата можно было бы обойтись и более
простыми средствами (см. раздел 3). Получены условия, которым должен удовлетворять под-
граф на вершинах с нечетными степенями, гарантирующие минимальность числа используе-
мых операций в независимости от выбора такого представления.
Следует отметить, что введение новых ребер не всегда означает в практической ситуации
построение новых коммуникаций. Например, когда стоит задача мониторинга подсистемы
424
коммуникаций, включенной в некоторую объемлющую структуру и добавление новых соеди-
нений происходит за счет имеющихся в ней.
Два эффективных метода построения эйлерова графа
Как и ранее, представим исходный граф G (V , E ) G (V1 ,V2 , E ) в виде двух подграфов
G1 (V1 , E1 ) и G2 (V2 , E2 ) , E E1 E2 E3 , где E 3 - подмножество ребер, соединяющих вер-
шины из V1 и V 2 . Вершины из V1 можно разбить на две группы:
V12 {x V1 /( x, y ) E1 , y V1}, V11 {x V1 / y V1 , ( x, y ) E1} , первые смежны только с
«четными вершинами», вторые соединены ребром с некоторой «нечетной вершиной».
Построение эйлерова графа с начальной операцией добавления ребер
Пусть в подграфе с «нечетными вершинами» G1 отсутствуют несмежные, т.е. G1 K n1 -
полный граф и в нем имеется простой цикл длины n1 . Если кратные ребра допускаются, то
n1 / 2 новых ребер делает степени всех его вершин четными. Если кратные ребра запрещены,
то добавление новых невозможно и эйлеров граф будет получен при удалении n1 / 2 попарно
несмежных ребер в том же простом цикле. В случае, когда G1 K 2 содержит единственное
ребро, его можно удалить только, если оно не является мостом в исходном графе G . В против-
ном случае граф G полуэйлеров, т.е. содержит эйлерову цепь.
Пусть теперь вершины x, y V1 несмежные. Добавление ребра ( x, y ) делает степени x, y
четными, а число «нечетных» вершин в новом графе уменьшается на две. Продолжая эту про-
цедуру, в результате придем к случаю, рассмотренному выше; либо, если E1 Ø, за n1 / 2 полу-
чим эйлеров граф. Эти рассуждения позволяют сформулировать
Утверждение 1. Пусть начальной операцией преобразования графа G G (V , E ) является
добавление ребер без кратности, тогда
а) если в подграфе G1 с «нечетными» вершинами нет моста графа G , то за n1 / 2 шагов
добавления и удаления ребер получается эйлеров граф:
б) если в подграфе G1 есть мост графа G , то за n1 / 2 шагов добавления и удаления ребер
получается полуэйлеров граф.
Построение эйлерова графа с начальной операцией удаления ребер
Более предпочтительной представляется ситуация, когда исходной оказывается операция
удаления некоторых соединений, не тре6ующая в первую очередь добавления новых. Такая
возможность возникает, когда достаточно ограничиться мониторингом некоторой заданной
подсистемы коммуникаций.
Пусть подграф G1 (V1 , E1 ) не является деревом, каждое ребро которого - мост в исходном
графе G . Последовательно удаляем все ребра из E1 . На каждом шаге степени двух «нечетных
вершин» становятся четными. При этом возникают две возможности. Первая - все степени
вершин станут четными и эйлеров граф будет получен без использования новых ребер. Вторая
– подграф на оставшихся «нечетных вершинах» не имеет ребер. Он содержит четное число
вершин и преобразуется в граф с четными степенями добавлением, как и ранее в п.3.1., попарно
несмежных ребер. В результате за n1 / 2 шагов будет построен эйлеров граф. Если в подграфе
425
G1 имеется единственное ребро, являющееся мостом графа G , то в полученном в результате
предложенной процедуры графе имеется эйлерова цепь. Если же подграф G1 - дерево, содер-
жащее более одного моста графа G , то приоритетной операцией перестройки будет добавле-
ние ребер.
Утверждение 2. Пусть начальной операцией преобразования графа G G (V , E ) является
удаление ребер возможно с последующим добавлением новых (без кратностей), тогда
а) если в подграфе G1 с «нечетными вершинами» нет моста графа G , то за n1 / 2 шагов
удаления и добавления ребер получается эйлеров граф; при этом, если в результате удаления
ребер не осталось «нечетных вершин», то новых ребер не требуется;
б) если в подграфе G1 имеется единственное ребро, являющееся мостом в G , то за n1 / 2
шагов удаления и добавления ребер получается полуэйлеров граф.
Таким образом, операции удаления и добавления n1 / 2 ребер из подграфа с «нечетными»
вершинами всегда позволяет преобразовать исходный граф в эйлеров или полуэйлеров. Если
имеется необходимость учета весов соединений (например, расстояний между узлами сети), то
в описанной процедуре сначала последовательно удаляются ребра с минимальными весами, а
затем последовательно добавляются ребра с максимальными весами. В результате будет по-
строена ближайшая подсистема коммуникаций, при мониторинге которой повторные прохож-
дения соединений исключаются.
Список литературы
Belman R., Cooke K. The Kenisberg bridges problem generalized // J. of Math. And Appl. — 1969. —
P. 25.
Фляйшнер Г. Эйлеровы графы и смежные вопросы. — М.: «Мир». 2002. — 335 с.
Fleiscnter H. Eurelian graphs and related topics. Part 1, vol. 1. Amsterdam: Elsevier science publishers B. V., 1991
(Russ. ed.: Fleischner H. Eulerovy grafy i smezhnye voprosy // M., «Mir»: 2002).
Fleischner H. Eurelian graphs and related topics. Part 1, vol. 2. Amsterdam: Elsevier science publish-
ers B. V., 1991. — 337 p.
Кристофидес Н. Теория графов (алгоритмический подход). — М.: «Мир». 1978. — 432 с.
Christofides N. Graph theory, an algorithmic approach // Academic Press, New York, London, San Francisco, 1975
(Russ. ed.: Christofides N. Teoria grafov, algoritmicheskiy podhod // M., «Mir»: 1978).
Раппопорт А.М. Оптимизация мониторинга системы коммуникаций на основе эйлеровой ап-
проксимации // Системный анализ и информационные технологии, САИТ-2011: Труды
IV Международной конференции. Т. 2. — Абзаково, Россия: 2011. — С. 173175.
Rappoport A.M. [The monitoring optimization of communications system by means of eurelian approxsimation].
Trudy IV Mezhdunarodnoy konferencii “Sistemnyj analiz i informacionnye tekhnologii” [Proc. IV Int. Conf. System
analyses and information technology]. — Vol. 2. — Abzakovo, Russia: 2011. — P. 173175 (in Russian).
Раппопорт А.М. Эффективный мониторинг коммуникаций на основе внешней аппроксимации
графа // Распределенные вычисления и грид технологии в науке и образовании: Труды
V Международной конференции. — Дубна: ОИЯИ, 2012. — С. 377382.
Rappoport A.M. [The eurelian graphs approximation methods for the problem of communications monitoring]. Trudy
V Mezhdunarodnoy konferencii “Raspredelennye vychesleniya i grid technologii v nauke i obrazovanii” [Proc. V Int.
Conf. Distributed computing and grid technology in science and education]. — Dubna: JINR, 2012. — P. 377382 (in
Russian).
426
The eulerian graphs approximation methods for the
problem of communications monitoring
A. M. Rappoport
A. A. Kharkevich Institute for Information Transmission Problems of Russian Academy of Sciences,
19, b. 2, Bolshoj Karetnij by-st., Moscow, 127051, Russia
E-mail: ram43@mail.ru
The paper provides a solution efficient communication system monitoring problem because of doubling
connections minimization. One of the approaches to this realization is approximation of corresponding graph by
eurelian graph, that excludes repeated vertex advancing.
The work provides classification of the input graph vertexes in regard to edges between subsets between
vertexes subsets with even and odd degrees. The study also considers various approximating graph construction
ways, first of all those, that minimize changes in adjacent matrix. The paper suggests the efficient method for
connected graph transmission to eulerian (semieurelian) graph using edges operation of deletion and adding. The
work shows the conditions of existence of interior approximation without additional elements.
Keywords: graph transmission, edges operations, eulerian graph, monitoring o f communications optimiza-
tion.
The work was supported by Grant of RFFI № 16-07-00238A.
© 2016 Alexander M. Rappoport
427