El $ \ text {k-clave} $ problema

Question

Dado un grafo no dirigido, defino una estructura llamada k-clave como una ruta que contiene $ k $ vértices que están conectados a un ciclo simple que contiene $ k $ vértices también.

Aquí está la k-clave problema . Dado un grafo no dirigido G $ $ $ y un número k $, decidir si $ G $ k contiene $ k $ tecla

Quiero mostrar que el problema clave k-es un NP-completo.

Quiero hacer una reducción del problema 'no dirigido hamiltoniano Ciclo' en el que la entrada es un gráfico, y el problema es decidir si contiene un camino de Hamilton. Ya sé que este problema es NP-completo. La entrada para la reducción sería un grafo no dirigido G $ $ y la salida es de $ gráfico $ G 'y $ k $. Puede usted por favor ayuda a entender lo que la manipulación que debo hacer para el gráfico original con el fin de mostrar esta reducción? Y ¿por qué debería trabajar?

Answer 1

Usted quiere encontrar una manera de crear $ G '$ de $ G $ tal que $ G' tiene un $ $ k $ tecla si y sólo si $ G $ tiene un camino de Hamilton.

Si un gráfico G $ $ $ $ k tiene vértices y un camino simple de longitud $ k $, entonces ¿qué podemos concluir de ello que tiene una trayectoria de Hamilton?

Estoy adivinando la intención es que los vértices en el camino deben ser diferentes de los vértices en el ciclo (de lo contrario cada gráfico de ciclo de jamón contendría un $ k $ tecla y viceversa). Por lo que sólo pensamos, supongamos que sabía que $ G $ tenía un ciclo de jamón partiendo de algunos vértice. ¿Dónde estaríamos virar en algunos vértices para crear un $ G '$ que tenía un $ k $ tecla usando $ G $' s ciclo de jamón?