Автор:  Губко М.В.
Название:  Верхняя оценка индекса Винера для дерева с заданными степенями и весами вершин
Статус:  опубликовано
Издательство (для книг и брошюр):  МФТИ
Год:  2016
Тип публикации:  тезисы
Название журнала или конференции:  Труды 59-й конференции МФТИ
Полная библиографическая ссылка:  Губко М.В. Верхняя оценка индекса Винера для дерева с заданными степенями и весами вершин / Труды 59-й научной конференции МФТИ с международным участием (Долгопрудный, 2016). Долгопрудный: МФТИ-, 2016.
Аннотация:  Индекс Винера (WI) – суммарное (реберное) расстояние между парами вершин графа [1] – является, пожалуй, самым известным графовым инвариантом. Он находит применение в математической химии и при анализе социальных сетей [2]. WI дает числовую меру «компактности» графа: среди деревьев с заданным числом вершин наименьшее значение WI имеет звезда, а наибольшее – цепь. Самое компактное дерево с заданной последовательностью степеней вершин – это «жадное» сбалансированное дерево, в котором длины путей от листьев до центральной вершины отличаются не более чем на единицу, а степени вершин убывают при удалении от центра [3, 4]. WI естественным образом обобщается на графы со взвешенными вершинами [5]. Для деревьев с заданными последовательностями степеней и весов вершин самым компактным (доставляющим минимум индекса) является обобщенное дерево Хаффмана. Оно эффективно строится последовательным соединением подграфов минимального веса [6]. Задача максимизации WI на множестве деревьев с заданной последовательностью степеней вершин оказывается более сложной. Известно, что оптимальное дерево – это некоторая гусеница (дерево, превращающееся в цепь при удалении листьев), в которой степени вершин монотонно убывают от концов центральной цепи к ее середине [3] и в [7] предложен эффективный алгоритм оптимального размещения вершин на этой цепи. В то же время, задача максимизации WI для взвешенных вершин NP-полна (к ней сводится задача о камнях). В докладе показывается, что, как и в задаче о камнях, сложность максимизации WI – в асимметрии весов вершин. Если число вершин каждой степени и веса четно), то индекс максимизируется гусеницей T, в которой вершины большего веса симметрично располагаются ближе к краям цепи. Можно записать аналитическое выражение для оптимального значения индекса. В общем случае асимметричных вершин оно дает верхнюю оценку значения индекса. Литература Wiener H. Structural determination of paraffin boiling points // J. Am. Chem. Soc. – 1947. –N 69. – P. 17–20. Dobrynin A. A., Entringer R., Gutman I. Wiener index of trees: theory and applications // Acta Appl. Math. – 2001. – N 66. – P. 211–249. Wang H. The extremal values of the Wiener index of a tree with given degree sequence // Discr. Appl. Math. – 2008. – N 156. – P. 2647–2654. Zhang X.-D., Xiang Q. Y., Xu L. Q., Pan R. Y. The Wiener index of trees with given degree sequences // MATCH Commun. Math. Comput. Chem. – 2008. – N 60. – P. 623–644. Klavžar S., Gutman I. Wiener number of vertex–weighted graphs and a chemical application // Discr. Appl. Math. – 1997. – N 80. – P. 73–81. Goubko M. Minimizing Wiener index for vertex-weighted trees with given weight and degree sequences // MATCH Commun. Math. Comput. Chem. – 2015. – N 73. – P. 3–27. Çela E., Schmuck, N. S., Wimer, S., Woeginger, G. J. The Wiener maximum quadratic assignment problem // Discrete Optimization. – 2011. – V. 8. – N. 3. – P. 411–416.

Полный текст: Скачать (pdf)

Просмотров: 2772, загрузок: 1705, за месяц: 6.

Назад