Witam potrzebuję następującego algorytmu:
Dany jest graf G=(V,E). Podzbiór ScV nazywamy niezależnym gdy dla dowolnych u,c S, uv1, (u, v)E. Podać algorytm wyznaczający maksymalny podzbiór wierzchołków niezależnych w drzewie .
0
1
zamiast kombinować z własna niezrozumiałą definicją trzeba było dać link do wiki: http://pl.wikipedia.org/wiki/Zbi%C3%B3r_niezale%C5%BCny albo ją zacytować.
1
@autor http://pl.wikipedia.org/wiki/Problem_zbioru_niezależnego
http://en.wikipedia.org/wiki/Independent_set_problem
Problem jest NP-zupełny więc nic poniżej wykładniczej złożoności tu nie wyciśniesz.