Graf subkubiczny to graf, w którym wszystkie wierzchołki mają stopnie nie większe niż 3. Udowodnij, że następujący problem decyzyjny jest NP-zupełny.
Egzemplarz: Graf subkubiczny G i liczba naturalna k.
Pytanie: Czy istnieje w G zbiór niezależny o mocy k?
0
0
Też mi się podoba to zadanie.
Potrzebujesz w czymś konkretnym czy chciałeś się tylko pochwalić?
0
Mam problem z udowodnieniem, może jakaś wskazówka?
0
Dużo Ci nie podpowiem, ale musisz próbować podać algorytm przekształcenia jakiegoś innego znanego problemu NP-zupełnego w ten problem. Przekształcenie musi działać w czasie wielomianowym.