Разрешима ли следующая задача

[Dima_VGEML]

На множестве деревьев (неориентированных графов без циклов) введена операция. Мы можем склеить два дерева по вершине (по любой, не обязательно по корню). Понятно, что после склейки мы получим снова дерево.

Массовая задача: Дано конечное множество деревьев. Можно ли из них получить любое дерево кроме конечного количества?

Существует ли алгоритм для решения этой задачи?

p.s. Нетривиальный пример, когда можно получить любое дерево, кроме конечного количества.
Рассмотрим множество всех деревьев с количеством вершин от N до 2N. Легко показать, что из них мы можем собрать любое дерево длины больше N, то есть все, кроме конечного количества.

[venco]

При слиянии количество рёбер равно сумме количеств рёбер исходных деревьев. Т.е. если начальное множество содержит деревья с чётным количеством рёбер, то мы не сможем получить дерево с нечётным количеством рёбер.

-- Пт окт 26, 2012 09:16:00 --

(Оффтоп)

А что такое корень неориентированного графа без циклов?

[sergey1]

Видимо висячая вершина

[arseniiv]

Dima_VGEML в сообщении #636110 писал(а):

деревьев (неориентированных графов без циклов)

Dima_VGEML в сообщении #636110 писал(а):

по вершине (по любой, не обязательно по корню)

У таких деревьев и нет корня. Из одного такого дерева можно получить некоторое множество корневых деревьев, выбирая корнем разные его вершины.

[Dima_VGEML]

arseniiv в сообщении #636150 писал(а):

Dima_VGEML в сообщении #636110 писал(а):

деревьев (неориентированных графов без циклов)

Dima_VGEML в сообщении #636110 писал(а):

по вершине (по любой, не обязательно по корню)

У таких деревьев и нет корня. Из одного такого дерева можно получить некоторое множество корневых деревьев, выбирая корнем разные его вершины.

Рад, что вы владеете терминологией. Я специально написал условий с избытком, чтобы не возникло сомнений при чтении условия задачи. По сути задачи есть что добавить?

[Ales]

Dima_VGEML в сообщении #636222 писал(а):

arseniiv в сообщении #636150 писал(а):

Dima_VGEML в сообщении #636110 писал(а):

деревьев (неориентированных графов без циклов)

Dima_VGEML в сообщении #636110 писал(а):

по вершине (по любой, не обязательно по корню)

У таких деревьев и нет корня. Из одного такого дерева можно получить некоторое множество корневых деревьев, выбирая корнем разные его вершины.

Рад, что вы владеете терминологией. Я специально написал условий с избытком, чтобы не возникло сомнений при чтении условия задачи. По сути задачи есть что добавить?

Если есть только конечное множество деревьев, то как получить любое дерево?
Одно и то же дерево использовать несколько раз?

[Dima_VGEML]

Ales в сообщении #636231 писал(а):

Если есть только конечное множество деревьев, то как получить любое дерево?
Одно и то же дерево использовать несколько раз?

Да, деревья можно использовать любое число раз. Например, любое дерево можно построить из дерева, состоящего из одного ребра.

[worm2]

Кажется, ответ на Ваш вопрос отрицательный. Слишком уж обширно множество частных случаев.
По крайней мере, я бы попробовал это доказать (если бы владел техникой)
Дерево эквивалентно некоторому S-выражению с единственным атомом, поэтому задачу можно переформулировать так: дано множество таких S-выражений, можно ли путём подстановки их друг в друга получить любое достаточно большое S-выражение? Дальше можно попробовать свести это безобразие к известной неразрешимой задаче по формальным грамматикам. Или можно попробовать любую программу для машины Тьюринга представить в виде такого S-выражения, если получится — победа близка.
Если это учебная задача, то надо посмотреть, какие техники Вы изучаете.
Если дали на собеседовании, то у собеседующих хорошее чувство юмора

[Dima_VGEML]

worm2 в сообщении #636378 писал(а):

Кажется, ответ на Ваш вопрос отрицательный. Слишком уж обширно множество частных случаев.
По крайней мере, я бы попробовал это доказать (если бы владел техникой)
Дерево эквивалентно некоторому S-выражению с единственным атомом, поэтому задачу можно переформулировать так: дано множество таких S-выражений, можно ли путём подстановки их друг в друга получить любое достаточно большое S-выражение? Дальше можно попробовать свести это безобразие к известной неразрешимой задаче по формальным грамматикам. Или можно попробовать любую программу для машины Тьюринга представить в виде такого S-выражения, если получится — победа близка.
Если это учебная задача, то надо посмотреть, какие техники Вы изучаете.
Если дали на собеседовании, то у собеседующих хорошее чувство юмора

Это не учебная задача. Просто одну важную задачу я умею сводить к этой. Да, очень хочется доказать неразрешимость, но здесь есть принципиальная трудность. В большинстве неразрешимых задач всё сводится к возможности получить какой-то особенный объект (проблема соответствий Поста, однородные продукции Поста, проблема домино и т.д.), а не к возможности получить все (почти все).

Пока же до этого далеко. Для начала хочется придумать пример деревьев размером меньше $N$, такой что наибольшее дерево, которое из них нельзя собрать, имело размер хотя бы $N^2.$

[arseniiv]

(Оффтоп)

Dima_VGEML в сообщении #636222 писал(а):

По сути задачи есть что добавить?

Задача интересная, но ничего в голову пока не пришло.

[INGELRII]

Для простоты при счете количества этажей у дерева корень за этаж считать не будем. Назовем деревом класса INGELRII с $n$ этажами такое бинарное дерево, что каждая вершина на каждом этаже, кроме последнего, имеет ровно 2 потомка. (На последнем этаже, естественно, у вершин потомков нету)

(Оффтоп)

Возьмем множество деревьев класса INGELRII, обладающих тем свойством, что их количество этажей делится на некоторое натуральное $d>1$. Это множество может быть хоть конечным, хоть даже бесконечным - очевидно, что склеивая их по вершинам как угодно, нам никогда не удастся построить дерево класса INGELRII с количеством этажей, на $d$ не делящихся. А таких деревьев бесконечно много. Вот.