Индекс Винера (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.
