Модель самотрансформации графов, основанная на операции изменения конца ребра

Main Article Content

Игорь Борисович Бурдонов

Аннотация

Рассмотрена распределенная сеть, топология которой описана неориентированным графом. Сеть может сама изменять свою топологию, используя специальные «команды», подаваемые ее узлами. В работе предложена предельно локальная атомарная трансформация acb изменения конца c ребра ac, «движущегося» вдоль ребра cb от вершины c к вершине b. В результате этой операции ребро ac удаляется, а ребро ab добавляется. Такая трансформация выполняется по «команде» от общей вершины c двух смежных ребер ac и cb. Показано, что из любого дерева можно получить любое другое дерево с тем же множеством вершин, использовав только атомарные трансформации. Если степени вершин дерева ограничены числом d (d3), то трансформация не нарушает этого ограничения. В качестве примера цели такой трансформации рассмотрены задачи максимизации и минимизации индекса Винера дерева с ограниченной степенью вершин без изменения множества его вершин. Индекс Винера – это сумма попарных расстояний между вершинами графа. Максимальный индекс Винера имеет линейное дерево (дерево с двумя листовыми вершинами). Для корневого дерева с минимальным индексом Винера определены его вид и способ вычисления числа вершин в ветвях соседей корня. Предложены два распределенных алгоритма: трансформации дерева в линейное дерево и трансформации линейного дерева в дерево с минимальным индексом Винера. Доказано, что оба алгоритма имеют сложность не выше 2n–2, где n – число вершин дерева. Также рассмотрена трансформация произвольных неориентированных графов, в которых могут быть циклы, кратные ребра и петли, без ограничения на степени вершин. Показано, что любой связный граф с n вершинами может быть преобразован в любой другой связный граф с k вершинами и тем же числом ребер за время не более 2(n+k)–2.

Article Details

Как цитировать
Бурдонов, И. Б. (2020). Модель самотрансформации графов, основанная на операции изменения конца ребра. Электронные библиотеки, 23(3), 315-335. извлечено от https://elbib.ru/article/view/602
Биография автора

Игорь Борисович Бурдонов

Ведущий научный сотрудник Института системного программирования им. В.П. Иванникова РАН. Сфера научных интересов – моделирование и верификация программных систем, теория графов, теория автоматов

Библиографические ссылки

Wiener H. Structural determination of paraffin boiling points // J. Am. Chem. Soc. 1947. No 69 (1). P. 17–20.

Кочкаров A.A., Сенникова Л.И., Кочкаров Р.А. Некоторые особенности применения динамических графов для конструирования алгоритмов взаимо-действия подвижных абонентов // Известия ЮФУ. Технические науки, раздел V, cистемы и пункты управления. 2015. №1. С. 207–214.

А.В. Проскочило, А.В. Воробьев, М.С. Зряхов, А.С. Кравчук. Анализ состояния и перспективы развития самоорганизующихся сетей // Научные ведомости, серия экономика, информатика, выпуск 36/1. 2015. № 19 (216). С. 177–186.

Pathan A.S.K. (ed.). Security of self-organizing networks: MANET, WSN, WMN, VANET. CRC press, 2010. 638 p.

Boukerche A. (ed.). Algorithms and protocols for wireless, mobile Ad Hoc networks // John Wiley & Sons, 2008. 496 p.

Chen Z., Li S., Yue W. SOFM Neural Network Based Hierarchical Topology Control for Wireless Sensor Networks // Hindawi Publishing Corporation. J. of Sensors. 2014. article ID 121278. 6 p. http://dx.doi.org/10.1155/2014/121278

Mo S., Zeng J.-C., Tan Y. Particle Swarm Optimization Based on Self-organizing Topology Driven by Fitness // International Conference on Computational Aspects of Social Networks, CASoN 2010, Taiyuan, China, 10.1109/CASoN. 2010. No 13. P. 23–26.

Wen C.-Y., Tang H.-K. Autonomous distributed self-organization for mobile wireless sensor networks // Sensors (Basel, Switzerland). 2009. V. 9, 11. P. 8961–8995.

Llorca J., Milner S.D., Davis C. Molecular System Dynamics for Self-Organization in Heterogeneous Wireless Networks // EURASIP J. on Wireless Communications and Networking. 2010. 10.1155/2010/548016. 13 p.

Wai-kai C. Net Theory And Its Applications: Flows In Networks. Imperial College Press (26 May 2003). 672 p.

Wang H. On the Extremal Wiener Polarity Index of Hückel Graphs // Computational and Mathematical Methods in Medicine. 2016. article ID 3873597. 6 p. http://dx.doi.org/10.1155/2016/3873597

Xu X., Gao Y., Sang Y., Liang Y. On the Wiener Indices of Trees Ordering by Diameter-Growing Transformation Relative to the Pendent Edges // Mathematical Problems in Engineering. 2019. article ID 8769428. 11 p. https://doi.org/ 10.1155/2019/8769428

The On-Line Encyclopedia of Integer Sequences (OEIS). http://oeis.org/

Fischerman M., Hoffmann A., Rautenbach D., Székely L., Volkmann L. Wiener index versus maximum degree in trees // Discrete Applied Mathematics. 2002. V. 122. Is. 1–3. P. 127–137.

Бурдонов И. Самотрансформация деревьев с ограниченной степенью вершин с целью минимизации или максимизации индекса Винера// Труды ИСП РАН. 2019. Т. 31. Вып. 4. С. 189–210.