"Записки научных семинаров ПОМИ"
Том 381, стр. 31-46
Построение остовного дерева графа с большим количеством листьев
Н. В. Гравин
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН,
Фонтанка 27,
191023 Санкт-Петербург, Россия.
Division of Mathematical Sciences, School
of Physical and Mathematical Sciences,
Nanyang Technological
University, Singapore
gravin@pdmi.ras.ru
- Аннотация: Известно, что в графе на $n$ вершинах с минимальной степенью $4$
существует остовное дерево, содержащее не менее $\frac{2}{5} \cdot
n$ листьев \cite{4}, что является асимптотически точной оценкой
для таких графов. В нашей работе приводится полиномиальный
алгоритм, находящий в графе с $k$ вершинами степени хотя бы четыре и
$k'$ вершинами степени три, остовное дерево с количеством висячих
вершин, по крайней мере $\lceil\frac{2}{5} \cdot k + \frac{2}{15}
\cdot k'\rceil$. Библ. -- 13 назв.
- Ключевые слова: Остовное дерево, количество листьев, висячие вершины
[Spanning tree, leaves, terminal vertices]
Полный текст(.pdf)