Пусть G - граф и δ (G) - минимальная степень вершины. Описать алгоритм в псевдокоде, что для данного дерева T с k < = δ (G) ребрами следует построить (в полиномиальном времени) подграф H группы G, чтобы H был изоморфен T.Задача изоморфного подграфа
я даже начинаю?
Зная, что T имеет максимальные ребра δ (G), я могу начать с любого узла в G и построить T в G, выбирая любой узел, потому что у меня всегда будет достаточно ребер и вершин. Сложность - O (n).
Основная проблема здесь - время полинома, но чтобы дать вам стартер, вы должны начать с корня своего дерева и в узле вашего графика (я считаю, что обнаружение узла является одной из основных задач) и из этого места вы должны построить свое дерево.
Обратите внимание, что любые алгоритмы типа DFS или BFS не будет делать трюк, потому что они не Полином
Надежда Я могу помочь!
Ну, вам определенно нужно начинать с узла вашего графика, который имеет как минимум столько же соседей, что и корень вашего дерева имеет детей.
Ответ немного зависит от того, что ваш профессор означает k < = delta (G). Если он имеет в виду то, что, по моему мнению, он имеет в виду, что в дереве столько или меньше ребер, чем соседи «вершины», что немного упрощает ситуацию. Во-первых, он намекает, что вам нужно найти пиковый узел. Если он означает «пик» узла, который имеет более высокую степень, чем любой из его соседей, вы можете обнаружить такой узел, начиная с узла, а затем выбирая соседа более высокой степени, повторяя при необходимости.
Извините, моя ошибка, дельта (G) - минимальная степень узла в G – sdadffdfd
Затем, как указывает Виктор З., это относительно тривиально. Практически любой узел будет делать в качестве отправной точки. Вы можете использовать первый или первый шаг глубины, просто отслеживайте, какие узлы вы уже использовали. – philosodad