Докажите, что число правого неизоморфных деревьев на n вершинах не превосходит 2^2n-2.(Графы называются изоморфными, если при некоторой перенумерации вершин их множества ребер совпадают.)

задан 25 Май '17 21:53

Что значит "число правого неизоморфных деревьев"? Это звучит бессмысленно.

(25 Май '17 22:02) falcao

Попарно неизоморфных- я незаметил это т9 исправил

(25 Май '17 22:09) Spl35
10|600 символов нужно символов осталось
1

Здесь можно воспользоваться сравнением с числом корневых деревьев, число которых известно. Корневое дерево определяется индукцией по числу вершин. Если вершина одна, то она является корнем дерева. Если вершин более одной, то рассматриваем конечную последовательность корневых деревьев с меньшим числом вершин, одну новую вершину объявляем корнем, и соединяем её рёбрами слева направо с корнями деревьев последовательности. При этом порядок подвешивания важен. Ясно, что число таких объектов не меньше числа деревьев с точностью до изоморфизма, поскольку каждое дерево можно задать как корневое, и чаще всего многими способами.

Число корневых деревьев с m рёбрами (соответственно, n=m+1 вершиной) равно m-му числу Каталана c_m=(2m)!/(m!(m+1)!), что, в свою очередь, не больше 4^m/(m+1). Факт достаточно известный, и на него можно найти ссылки даже из популярных статей. Это и даёт оценку сверху 4^{n-1}, где n -- число вершин.

ссылка

отвечен 25 Май '17 23:39

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,481

задан
25 Май '17 21:53

показан
471 раз

обновлен
25 Май '17 23:39

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

по почте:

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

по RSS:

Ответы

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

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