Mam do określenia złożoność problemu (nie algorytmu). Mając wierzchołki z określoną wartością, chcę znaleźć maksymalną klikę. Warunkiem takiej kliki jest jest to, aby wartość wszystkich wierzchołków nie przekroczyła wartości podanej przez użytkownika.
Wiem że trzeba będzie znaleźć wszystkie kliki, wybrać te, które się mieszczą w kryterium i potem wybrać największą z nich.
Z góry dziękuję za wszelką pomoc
0
0
Muszę się zastanowić nad tym co napisałeś i co dokładnie chcesz osiagnac, ale znajdowanie kliki o zadanej wielkości to problem NP kompletny.
0
Też wyczytałam, że szukanie klik jest NP-trudne, ale czy da się to jakość uszczegółowić? Czy wystarczy powiedzieć że problem jest NP-trudny
0
Czy te wierzchołki są połączone?
1
Generalnie ilość takich klik to 3^(3/n), więc sensownie będzie przyjąć to jako maksimum. chociaż są też szybsze algporytmy.