УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ
на главную написать письмо карта сайта

ѕоиск в базе данных публикаций по теории управлени€ организационными системами



јвтор:  √убко ћ.¬.
Ќазвание:  ¬ерхн€€ оценка индекса ¬инера дл€ дерева с заданными степен€ми и весами вершин
—татус:  опубликовано
»здательство (дл€ книг и брошюр):  ћ‘“»
√од:  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)

ѕросмотров: 791, загрузок: 218, за мес€ц: 8.

Ќазад

»ѕ” –јЌ © 2007. ¬се права защищены