Рассматривается задача е-поиска на графах, основное внимание уделяется изучению скачков функции Головача для деревьев. Исследования в этом направлении были предприняты в работах Ц] и [2]. B первой статье приводится достаточное условие единичности скачка функции Головача для деревьев и доказывается важная лемма >. B работе [2] построены примеры деревьев, в которых указанное достаточное условие нарушается, и функция Головача для этих деревьев имеет скачок высоты 2. Приведённые примеры не только подтвердили существенность условий теоремы o единичных скачках, но и оказались минимальными по числу рёбер деревьями c > (имеющей неединичные скачки) функцией Головача. Авторы настоящей статьи некоторое время полагали, что, помимо перечисленного, на этих примерах достигается наибольший скачок функции Головача, возможный для деревьев. В настоящей статье это предположение опровергается, и утверждается, что скачок функции Головача для деревьев может быть сколь угодно большим.
展开▼
