Il $ \ text {k-chiave} $ problema

Question

Dato un grafo non orientato, definisco una struttura denominata k-chiave come un percorso contenente $ k $ vertici che sono collegati ad un semplice ciclo che contiene $ k $ vertici pure.

Ecco il k-chiave problema :. Dato un grafo non orientato $ G $ e un numero $ k $, decidere se $ G $ contiene k $ k $ tasto

Voglio mostrare che il problema k-chiave è un NP-completo.

Voglio fare una riduzione dal problema 'non orientato Hamiltonian ciclo' in cui l'ingresso è un grafico, e il problema è quello di decidere se contiene un percorso hamiltoniano. So già che questo problema è NP-completo. L'ingresso per la riduzione sarebbe un grafo non orientato G $ $ e l'uscita è $ G '$ grafico e $ k $. Potete per favore aiutarmi a capire cosa devo fare la manipolazione al grafico originale per mostrare questa riduzione? E perché dovrebbe funzionare?

Answer 1

Si vuole trovare un modo per creare $ G '$ da $ G $ tale che $ G' $ ha un $ k $ tasto se e solo se $ G $ ha un percorso hamiltoniano.

Se un grafo $ G $ è $ k $ vertici e un semplice percorso di lunghezza $ k $, allora cosa possiamo concludere circa esso avente un percorso hamiltoniano?

sto cercando di indovinare l'intenzione è che i vertici nel percorso devono essere diversi dai vertici nel ciclo (altrimenti ogni prosciutto grafico ciclo conterrebbe un $ k $ tasto e viceversa). Quindi, solo pensare, supponiamo sapevamo che $ G $ ha avuto un ciclo di prosciutto a partire da qualche vertice. Dove saremmo virare su alcuni vertici per creare un $ G '$ che ha avuto un $ k $ tasto utilizzando $ G $' s ciclo di prosciutto?