Réduction de la clique à autre chose
-
04-11-2019 - |
Question
Donné $ G (v, e) $ et $ k $. Y a-t-il une clique avec une taille $ k $?
Donné set $ x = {x_1, x_2, dots, x_n } $, et la collection $ a = {a_1, a_2, ..., a_n } $ de sous-ensembles de $ x $ et $ k $. Y a-t-il des éléments différents $ k $ dans $ a $, que tous les deux d'entre eux ont une intersection qui n'est pas vide? Par exemple $ a_1 = {x_1, x_2, x_3 } $, $ a_2 = {x_4, x_5, x_1 } $ donc leur intersection est $ x_1 $ et son valide, mais il devrait être appliqué pour chaque deux $ a_i , A_j $ dans $ a $.
Prouver: Ce problème anonyme (qui a sûrement un nom) est du NP.
La réduction est ..
$ X = e $, et chaque $ a_i $ en $ a $ est composé de bords connectés au sommet $ v_i $.
Je ne peux pas comprendre la réduction, quelqu'un peut-il expliquer pourquoi cela fonctionne s'il vous plaît?
Pas de solution correcte