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

Article Sidebar

PDF
Опубликован: 09.05.2020
УДК 004.021 004.42
DOI: https://doi.org/10.26907/1562-5419-2020-23-3-315-335
Выпуск
Том 23 № 3 (2020): Тематический выпуск «Научный сервис в сети Интернет». Часть 1

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://doi.org/10.26907/1562-5419-2020-23-3-315-335
Биография автора

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

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

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

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.



Представляя статьи для публикации в журнале «Электронные библиотеки», авторы автоматически дают согласие предоставить ограниченную лицензию на использование материалов Казанскому (Приволжскому) федеральному университету (КФУ) (разумеется, лишь в том случае, если статья будет принята к публикации). Это означает, что КФУ имеет право опубликовать статью в ближайшем выпуске журнала (на веб-сайте или в печатной форме), а также переиздавать эту статью на архивных компакт-дисках журнала или включить в ту или иную информационную систему или базу данных, производимую КФУ.

Все авторские материалы размещены в журнале «Электронные библиотеки» с ведома авторов. В случае, если у кого-либо из авторов есть возражения против публикации его материалов на данном сайте, материал может быть снят при условии уведомления редакции журнала в письменной форме.

Документы, изданные в журнале «Электронные библиотеки», защищены законодательством об авторских правах, и все авторские права сохраняются за авторами. Авторы самостоятельно следят за соблюдением своих прав на воспроизводство или перевод их работ, опубликованных в журнале. Если материал, опубликованный в журнале «Электронные библиотеки», с разрешения автора переиздается другим издателем или переводится на другой язык, то ссылка на оригинальную публикацию обязательна.

Передавая статьи для опубликования в журнале «Электронные библиотеки», авторы должны принимать в расчет, что публикации в интернете, с одной стороны, предоставляют уникальные возможности доступа к их материалам, но, с другой, являются новой формой обмена информацией в глобальном информационном обществе, где авторы и издатели пока не всегда обеспечены защитой от неправомочного копирования или иного использования материалов, защищенных авторским правом.

При использовании материалов из журнала обязательна ссылка на URL: http://elbib.kpfu.ru. Любые изменения, дополнения или редактирования авторского текста недопустимы. Копирование отдельных фрагментов статей из журнала разрешается только для научных исследований и персонального использования, но не для коммерческого использования, перепродажи или передачи другому лицу.

Запросы на право переиздания или использования любых материалов, опубликованных в журнале «Электронные библиотеки», следует направлять главному редактору Елизарову А.М. по адресу: [email protected]

Издатели журнала «Электронные библиотеки» не несут ответственности за точки зрения, излагаемые в публикуемых авторских статьях.

Предлагаем авторам статей загрузить с этой страницы, подписать и выслать в адрес издателя журнала по электронной почте скан Авторского договора о передаче неисключительных прав на использование произведения.