Уточнение свойств центроида дерева


https://doi.org/10.18255/1818-1015-2017-4-410-414

Полный текст:


Аннотация

Работа посвящена уточнению свойств центроида дерева. Внимание авторов привлекла популярная задача (бинарного) разбиения графа, для которой неизвестен непереборный алгоритм. Выяснено, что для «экономного» разбиения дерева имеет смысл рассматривать разбиения в окрестности центроидных вершин, определение которых представлено. В ходе работы предложены доказательства, связанные с ограничением их веса. Также доказано, что если в дереве имеются две центроидные вершины, то они смежны. В следствии отмечается, что в дереве не могут иметь место три таких вершины. Составлены соответствующие предложения. Согласно первому, любая вершина дерева с определенным ограничением на ее вес является центроидной. По одному из пунктов второго предложения, если в дереве имеются две центроидные вершины, то порядок дерева является чётным числом. Третье предложение гласит, что если в дереве имеется центроидная вершина ограниченного веса, то имеется и другая центроидная вершина того же веса и смежная с первой. Для доказательства предложений рассматривается ветвь наибольшего веса при центроидной вершине и в этой ветви берется другая смежная с центроидной вершина. В работе используется теорема Жордана, при изложении материала представлено три изображения. 


Об авторах

Юрий Анатольевич Белов
Ярославский государственный университет им. П.Г. Демидова
Россия
канд. физ.-мат. наук, доцент


Сергей Иванович Вовчок
Ярославский государственный университет им. П.Г. Демидова
Россия
аспирант


Список литературы

1. Евстигнеев В. А., Касьянов В. Н., Теория графов. Алгоритмы обработки деревьев, Наука, Новосибирск, 1994

2. Ловас Л., Пламмер М., Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии, Мир, М., 1998


Дополнительные файлы

Для цитирования: Белов Ю.А., Вовчок С.И. Уточнение свойств центроида дерева. Моделирование и анализ информационных систем. 2017;24(4):410-414. https://doi.org/10.18255/1818-1015-2017-4-410-414

For citation: Belov Y.A., Vovchok S.I. Tree Centroid Properties Clarification. Modeling and Analysis of Information Systems. 2017;24(4):410-414. (In Russ.) https://doi.org/10.18255/1818-1015-2017-4-410-414

Просмотров: 216

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)