Проблема изоморфного подграфа

Question

Пусть G - граф, а δ (G) - минимальная степень вершины.Опишите алгоритм в псевдокоде, согласно которому для заданного дерева T с k <= δ (G) ребрами необходимо построить (за полиномиальное время) подграф H в G так, чтобы H изоморфно T. </p>

Как мне вообще начать?

Answer 1

Ну, вам определенно нужно начать с узла вашего графа, у которого есть как минимум столько же соседей, сколько у корня вашего дерева есть дочерние элементы.

Ответ немного зависит от того, что именно ваш профессор имеет в виду под k <= delta (G) гранями. Если он имеет в виду то, что, я думаю, он имеет в виду, что в дереве столько же или меньше ребер, чем соседей «пикового» узла, что значительно упрощает ситуацию. С одной стороны, это намекает на то, что вам нужно найти пиковый узел. Если он имеет в виду «пик» узла, который имеет более высокую степень, чем любой из его соседей, вы можете обнаружить такой узел, начав с узла, а затем выбрав соседа более высокой степени, при необходимости повторите. </p>

Answer 2

Зная, что T имеет δ (G) максимальных ребер, я могу начать с любого узла в G и построить T в G, выбрав любой узел, потому что у меня всегда будет достаточно ребер и вершин.Сложность O (n).

Answer 3

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

Обратите внимание, что любые алгоритмы типа DFS или BFS не сработают, потому что они не полиномиальны

Надеюсь, я могу помочь!