Задача о существовании дерева с характеристическим вектором узловых вершин

Main Article Content

Иван Николаевич Попов

Аннотация

В работе рассматривается задача о существовании дерева с определенными числовыми характеристиками. Если задано дерево, то можно определить количества узловых вершин дерева и листьев, а также определить их степени. Тем самым для дерева можно определить набор пар, составные которых есть числа, соответствующие количествам узловых вершин и их степеней. Можно сформулировать обратную задачу: задаются пары натуральных чисел, вторые компоненты которых больше 1, и следует определить, найдется ли хотя бы одно дерево, что количества его узловых вершин и их степеней совпадают с данными парами. Решение этой задачи представлено в данной работе.

Article Details

Как цитировать
Попов, И. Н. . (2021). Задача о существовании дерева с характеристическим вектором узловых вершин. Электронные библиотеки, 24(3), 474-484. https://doi.org/10.26907/1562-5419-2021-24-3-474-484

Библиографические ссылки

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.