Задача о существовании дерева с характеристическим вектором узловых вершин
https://doi.org/10.26907/1562-5419-2021-24-3-474-484
Аннотация
В работе рассматривается задача о существовании дерева с определенными числовыми характеристиками. Если задано дерево, то можно определить количества узловых вершин дерева и листьев, а также определить их степени. Тем самым для дерева можно определить набор пар, составные которых есть числа, соответствующие количествам узловых вершин и их степеней. Можно сформулировать обратную задачу: задаются пары натуральных чисел, вторые компоненты которых больше 1, и следует определить, найдется ли хотя бы одно дерево, что количества его узловых вершин и их степеней совпадают с данными парами. Решение этой задачи представлено в данной работе.
Список литературы
1. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М.: Лаборатория базовых знаний, 2001. 288 с.
2. Калужнин Л.А., Сущанский В.И. Преобразования и перестановки. М.: Наука. Главная редакция физико-математической литературы, 1985. 160 с.
3. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: Изд-во МАИ, 1992. 264 с.
4. Попов И.Н, Попова А.В. Разложение подстановок в циклы: реализация приложений с помощью Python // Сборник трудов Международной научной конференции «Актуальные проблемы прикладной математики, информатики и механики», Воронеж, Россия, 11-13 ноября 2019 г. Воронеж: Издательство «Научно-исследовательские публикации», 2020. С. 484-491.
5. Lutz M. Learning Python, 4th Edition. O'Reilly Media, Inc. 2011. 1280 p.
Рецензия
Для цитирования:
Попов И.Н. Задача о существовании дерева с характеристическим вектором узловых вершин. Электронные библиотеки. 2021;24(3):474-484. https://doi.org/10.26907/1562-5419-2021-24-3-474-484
For citation:
Popov I.N. The Problem of the Existence of a Tree with a Characteristic Vector of Node Vertices. Russian Digital Libraries Journal. 2021;24(3):474-484. (In Russ.) https://doi.org/10.26907/1562-5419-2021-24-3-474-484
Просмотров:
12
Послать статью по эл. почте 