Самотрансформация деревьев с ограниченной степенью вершин с целью минимизации или максимизации индекса Винера
https://doi.org/10.15514/ISPRAS-2019-31(4)-13
Аннотация
Рассматривается распределённая сеть, граф связи которой является неориентированным деревом. Предполагается, что сеть может сама менять свою топологию. Для этого предлагается предельно локальная атомарная трансформация – добавление ребра, соединяющего разные концы двух смежных ребер, и одновременное удаление одного из этих ребер. Такая трансформация выполняется по «команде» от вершины дерева, а именно, общей вершины двух смежных ребер. Показывается, что из любого дерева можно получить любое другое дерево с помощью только атомарных трансформаций. Если рассматриваются деревья с ограничением d (d ³ 3) на степени вершин, то трансформация не нарушает этого ограничения. В качестве примера цели такой трансформации рассматриваются задачи максимизации и минимизации индекса Винера дерева с ограниченной степенью вершин без изменения множества его вершин. Предлагаются соответствующие распределённые алгоритмы и доказываются линейные оценки их сложности.
При поддержке: Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 17-07-00682-а.
Об авторе
Игорь Борисович Бурдонов
Институт системного программирования им. В.П. Иванникова РАН
Россия
Доктор физико-математических наук, ведущий научный сотрудник
Россия
Доктор физико-математических наук, ведущий научный сотрудник
Список литературы
1. Wiener H. Structural determination of paraffin boiling points. Journal of the American Chemical Society, vol. 69, no. 1, 1947, pp. 17–20.
2. Miranca Fischerman, Arne Hoffmann, Dieter Rautenbach, László Székely, LutzVolkmann. Wiener index versus maximum degree in trees. Discrete Applied Mathematics, volume 122, issues 1–3, 2002, pp. 127–137.
3. L. A. Székely and Hua Wang, On Subtrees of Trees. Advances in Applied Mathematics, vol. 34, issue 1, 2005, pp. 138–155.
4. A.А. Кочкаров, Л.И. Сенникова, Р.А. Кочкаров. Некоторые особенности применения динамических графов для конструирования алгоритмов взаимодействия подвижных абонентов. Известия ЮФУ. Технические науки», № 1, 2015, стр. 207–214 / А.А. Kochkarov, L.I. Sennikova, R.А. Kochkarov. Some features of dynamic graphs applications for construction of mobile agents interaction algorithms. Izvestiya SFedU. Engineering sciences, № 1, 2015, pp. 207–214 (in Russian).
5. A.A. Kochkarov, R.A. Kochkarov, G.G. Malinetskii. Issues of dynamic graph theory. Computational Mathematics and Mathematical Physics, 2015, vol. 55, no. 9, pp. 1590–1596.
6. А.В. Проскочило, А.В. Воробьев, М.С. Зряхов, А.С. Кравчук. Анализ состояния и перспективы развития самоорганизующихся сетей. Научные ведомости Белгородского государственного университета, Экономика, Информатика, no. 36/1, вып. 19 (216), 2015, стр. 177-186 / A.V. Proskochylo, A.V. Vorobyov, M.S. Zriakhov, A.S. Kravchuk. Analysis of state and development perspectivesof self-organizing networks. Belgorod State University Scientific Bulletin. Economics, Information technologies, no. 19 (216), issue 36/1, 2015, pp. 177-186 (in Russian).
7. Zhi Chen, Shuai Li, and Wenjing Yue. SOFM Neural Network Based Hierarchical Topology Control for Wireless Sensor Networks. Journal of Sensors, vol. 2014, Article ID 121278, 6 p.
8. Chen Dongning, Zhang Ruixing, Yao Chengyu, and Zhao Zheyu. Dynamic topology multi force particle swarm optimization algorithm and its application. Chinese Journal of Mechanical Engineering, vol. 29, issue 1, 2016, pp. 124–135.
9. Simin Mo, Jian-Chao Zeng, Ying Tan. Particle Swarm Optimization Based on Self-organizing Topology Driven by Fitness. In Proc. of the International Conference on Computational Aspects of Social Networks, 2010, pp. 23–26.
10. Al-Sakib Khan Pathan (ed.) Security of self-organizing networks: MANET, WSN, WMN, VANET. CRC press, 2010, 638 p.
11. Boukerche A. (ed.) Algorithms and protocols for wireless, mobile Ad Hoc networks. John Wiley & Sons, 2008, 496 p.
12. Wen, Chih-Yu and Hung-Kai Tang. Autonomous distributed self-organization for mobile wireless sensor networks. Sensors, vol. 9, issue 11, 2009, pp. 8961-8995.
13. Jaime Llorca, Stuart D. Milner, Christopher Davis. Molecular System Dynamics for Self-Organization in Heterogeneous Wireless Networks. EURASIP Journal on Wireless Communications and Networking, 2010, Article number: 548016.
14. Rangaswami Balakrishnan and S. Francis Raj. The Wiener number of powers of the Mycielskian. Discussiones Mathematicae Graph Theory, vol. 30, no. 3, 2010, p. 489–498.
15. Chen Wai-kai. Net Theory and its Applications: Flows in Networks. World Scientific Publishing, 2003, 672 p.
16. Hongzhuan Wang. On the Extremal Wiener Polarity Index of Hückel Graphs. // Computational and Mathematical Methods in Medicine, vol. 2016, article ID 3873597. http://dx.doi.org/10.1155/2016/3873597.
17. Xiaoxin Xu, Yubin Gao, Yanbin Sang, and Yueliang Liang. On the Wiener Indices of Trees Ordering by Diameter-Growing Transformation Relative to the Pendent Edges. Mathematical Problems in Engineering, vol. 2019, article ID 8769428.
18. The On-Line Encyclopedia of Integer Sequences (OEIS). http://oeis.org/
19. Михаил Дехтярь. Основы дискретной математики. Лекция 10: Деревья. ИНТУИТ (национальный открытый университет). https://www.intuit.ru/studies/courses/1084/192/lecture/5017 / Mihail Dekhtyar'. The basics of discrete mathematics. Lecture 10: The trees. INTUIT (National Open University). Available at: https://www.intuit.ru/studies/courses/1084/192/lecture/5017 (in Russian).
Рецензия
Для цитирования:
Бурдонов И.Б. Самотрансформация деревьев с ограниченной степенью вершин с целью минимизации или максимизации индекса Винера. Труды Института системного программирования РАН. 2019;31(4):189-210. https://doi.org/10.15514/ISPRAS-2019-31(4)-13
For citation:
Burdonov I.B. Self-transformation of trees with a bounded degree of vertices to minimize or maximize the Wiener index. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2019;31(4):189-210. (In Russ.) https://doi.org/10.15514/ISPRAS-2019-31(4)-13
Послать статью по эл. почте 