Seja G = (V, E) um gráfico não direcionado. Um subconjunto S ⊆ V de nós em G é chamado de "conjunto dominante" se, para todos v ∈ V, tivermos v ∈ S ou houver algum nó ∈ S tal que (u, v) ∈ E. Em outras palavras, cada O nó em V \ S é conectado por uma aresta a um nó em S. Dados os pesos não negativos w (v) nos nós de V, o objetivo é encontrar um conjunto dominante de peso mínimo em G. (Nota: esse problema é conhecido como NP-Hard em gráficos gerais) Precisamos projetar um algoritmo de tempo POLINOMIAL para solucionar esse problema quando G é uma árvore.

Eu li sobre o problema da árvore Steiner no Wiki, que está um pouco relacionado a isso, mas ainda está confuso.

Como precisamos fazer isso?