|
Уточнение свойств центроида дерева
Ю. А. Белов, С. И. Вовчок Ярославский государственный университет им. П.Г. Демидова, ул. Советская, 14, г. Ярославль, 150003 Россия,
Аннотация:
Работа посвящена уточнению свойств центроида дерева. Внимание авторов привлекла популярная задача (бинарного) разбиения графа, для которой неизвестен непереборный алгоритм. Выяснено, что для «экономного» разбиения дерева имеет смысл рассматривать разбиения в окрестности центроидных вершин, определение которых представлено. В ходе работы предложены доказательства, связанные с ограничением их веса. Также доказано, что если в дереве имеются две центроидные вершины, то они смежны. В следствии отмечается, что в дереве не могут иметь место три таких вершины. Составлены соответствующие предложения. Согласно первому, любая вершина дерева с определенным ограничением на ее вес является центроидной. По одному из пунктов второго предложения, если в дереве имеются две центроидные вершины, то порядок дерева является чётным числом. Третье предложение гласит, что если в дереве имеется центроидная вершина ограниченного веса, то имеется и другая центроидная вершина того же веса и смежная с первой. Для доказательства предложений рассматривается ветвь наибольшего веса при центроидной вершине и в этой ветви берется другая смежная с центроидной вершина. В работе используется теорема Жордана, при изложении материала представлено три изображения.
Ключевые слова:
центроид, центроид дерева.
Поступила в редакцию: 25.07.2017
Образец цитирования:
Ю. А. Белов, С. И. Вовчок, “Уточнение свойств центроида дерева”, Модел. и анализ информ. систем, 24:4 (2017), 410–414
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais573 https://www.mathnet.ru/rus/mais/v24/i4/p410
|
|