Поиск остовного дерева графа-кактуса с минимальным индексом Винера
Поиск остовного дерева графа-кактуса с минимальным индексом Винера
Аннотация:
Рассматривается задача построения остовного дерева в графе типа «кактус», минимизирующего значение индекса Винера — топологического индекса графа, который определяется суммой расстояний между всеми парами вершин. Граф-кактус представляет собой особый класс связных графов, в которых любые два простых цикла имеют не более одной общей вершины. Показывается, что в общем виде задача поиска остовного дерева с минимальным индексом Винера NP-полна, но для графов типа «кактус» данная задача решается за полиномиальное время. Приведён соответствующий алгоритм.
Ил. 1, библиогр. 7.
Литература:
- Abu-Affash A. K., Carmi P., Luwisch O., Mitchell J. S. B. Geometric spanning trees minimizing the Wiener index // Algorithms and data structures. Proc. 18th Int. Symp. (Montreal, QC, Canada, July 31 – Aug. 2, 2023). Cham: Springer, 2023. P. 1–14. (Lect. Notes Comput. Sci.; V. 14079).
- Pandey D., Patra K. L. Wiener index of graphs with fixed number of pendant or cut-vertices // Czechoslov. Math. J. 2022. V. 72, No. 2. P. 411–431.
- Klein D. J., Randić M. Resistance distance // J. Math. Chem. 1993. V. 12. P. 81–95.
- Wiener H. Structural determination of paraffin boiling points // J. Am. Chem. Soc. 1947. V. 69, No. 1. P. 17–20.
- Gutman I., Trinajstic N. Graph theory and molecular orbitals. Total $\phi$-electron energy of alternant hydrocarbons // Chem. Phys. Lett. 1972. V. 17, No. 4. P. 535–538.
- Bonchev D., Rouvray D. H. Complexity in chemistry, biology, and ecology. New York: Springer, 2005. 348 p.
- Johnson D. S., Lenstra J. K., Rinnooy Kan A. H. G. The complexity of the network design problem // Networks. 1978. V. 8, No. 4. P. 279–285.
Исследование выполнено за счёт бюджета Волгоградского гос. университета. Дополнительных грантов на проведение или руководство этим исследованием получено не было.
Клячин Владимир Александрович
- Волгоградский гос. университет,
Университетский пр., 100, 400062 Волгоград, Россия
E-mail: klyachin.va@volsu.ru
Хижнякова Екатерина Владимировна
- Волгоградский гос. университет,
Университетский пр., 100, 400062 Волгоград, Россия
E-mail: yakovleva.e.v@volsu.ru
Статья поступила 28 мая 2025 г.
После доработки — 11 июня 2025 г.
Принята к публикации 22 сентября 2025 г.
Abstract:
We consider the problem of constructing a spanning tree in a cactus graph that minimizes the value of the Wiener index, which is a topological graph index determined by the sum of distances between all pairs of vertices. The cactus graph is a special class of connected graphs in which any two simple cycles have at most one vertex in common. It is shown that the problem of finding a spanning tree with the minimum Wiener index is NP-complete, while for cactus-type graphs this problem can be solved in polynomial time. The corresponding algorithm is provided.
Illustr. 1, bibliogr. 7.
References:
- A. K. Abu-Affash, P. Carmi, O. Luwisch, and J. S. B. Mitchell, Geometric spanning trees minimizing the Wiener index, in Algorithms and Data Structures, Proc. 18th Int. Symp. (Montreal, QC, Canada, July 31 – Aug. 2, 2023) (Springer, Cham, 2023), pp. 1–14 (Lect. Notes Comput. Sci., V. 14079).
- D. Pandey and K. L. Patra, Wiener index of graphs with fixed number of pendant or cut-vertices, Czechoslov. Math. J. 72 (2), 411–431 (2022).
- D. J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12, 81–95 (1993).
- H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1), 17–20 (1947).
- I. Gutman and N. Trinajstic, Graph theory and molecular orbitals. Total $\phi$-electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (4), 535–538 (1972).
- D. Bonchev and D. H. Rouvray, Complexity in Chemistry, Biology, and Ecology (Springer, New York, 2005).
- D. S. Johnson, J. K. Lenstra, A. H. G. Rinnooy Kan, The complexity of the network design problem, Networks 8 (4), 279–285 (1978).