"Записки научных семинаров ПОМИ"

Том 475, стр. 5-21

С.-Петербургский государственный университет, ул. Ульяновская, д.3, Старый Петергоф, 198504 Санкт-Петербург, Россия

abvabv@bk.ru, v.buslov@spbu.ru

Аннотация: Развит инструментарий, позволяющий из одних ориентированных лесов строить другие ориентированные леса. С его помощью доказаны неравенства, связывающие веса минимальных ориентированных лесов при разных количествах деревьев в них. Также доказана теорема о родственных лесах, показывающая, как с помощью замены дуг в одном дереве получить минимальный ориентированный лес с числом корней, большим или меньшим на единицу. Библ. -- 10 назв.
Ключевые слова: минимальный лес, ориентированное дерево, неравенства выпуклости [minimal forest, directed tree, convexity inequalities]