@html-profi

Всем привет!
Препод дал задание написать программу, которая бы находила максимальное независимое множество в дереве(т.е. дано дерево, надо найти максимальное множество вершин, никакие две из которых не связаны ребром)
Нашел на псевдокод
function get_independent_set(Node u)
{
если I(u) уже посчитано, то возвратить I(u)
//мощность множества, которое можно получить, если не брать вершину u
children_sum = 0
//мощность множества, которое можно получить, если взять вершину u
grandchildren_sum = 0
//цикл по всем детям
for i := 1 to child_num do
children_sum = children_sum + get_independent_set(children[i])
//цикл по всем внукам
for i:= 1 to grandchildren_num
grandchildren_sum = grandchildren_sum + get_independent_set(grandchildren[i])
//запоминаем, чтобы не персчитывать ещё раз
I(u) = max(1 + grandchildren_sum, children_sum)
возвратить I(u)
}

но ничего не пойму. Помогите плиз.
Буду благодарен за помощь.

0