Дано ориентированное дерево, содержащее N ярусов. (Определение: k-й ярус дерева - множество узлов дерева, находящихся на уровне k от корня дерева.)

Какое максимальное возможное число путей длины n от корня дерева?

задан 9 Дек '17 22:05

@AlinaH: получается, что ярус и уровень -- это одно и то же. Зачем тогда два разных понятия? Я бы сказал проще: вершины k-го уровня находятся в дереве на расстоянии k от корня.

Видимо, здесь подразумевается, что N -- число непустых ярусов (уровней).

Количество путей не выражается через число ярусов. Рассмотрим простейший пример: пусть N=1. Это значит, что от корня отходят рёбра. Их количество нам не дано. Их может быть 10, 100, бесконечно много. Столько же будет и путей от корня, если брать простые пути.

(9 Дек '17 22:36) falcao

Спасибо! А если ввести дополнительное условие-обозначение: на k-м уровне число вершин не превосходит a_k ?

(9 Дек '17 23:30) AlinaH

@AlinaH: если есть только ограничение сверху, то и получить можно только ограничение. Но тут ничего интересного не получится -- ведь число путей (простых) из корня на уровень k равно числу вершин уровня k.

Что это вообще за задача, как она возникла?

(10 Дек '17 0:15) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,062
×135

задан
9 Дек '17 22:05

показан
118 раз

обновлен
10 Дек '17 0:15

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru