qwerty86
18-02-2009, 10:23
Salve a tutti mi sono imbattuto in questo esercizio e non riesco proprio a venirne fuori...potete darmi una mano?
Chiarire se i seguenti linguaggi sono nella classe P e/o nella classe NPC. Giusticare la risposta.
1)QUASI-HAM = {< G >: il grafo G = (E; V ) ha un ciclo semplice che contiene |V|-1 vertici}
2)4-HAM = {< G >: il grafo G = (E; V ) ha un ciclo semplice che contiene 4 vertici}
Pensandoci credo che il primo faccia parte di npc dato che è proprio come il problema del grafo hamiltoniano solo che invece di |V| vertici qui il ciclo può essere di |V|-1 , il secondo penso dia più semplice e possa essere della classe p. Ora...come giustifico le risposte?? Grazie a tutti anticipaamente
Chiarire se i seguenti linguaggi sono nella classe P e/o nella classe NPC. Giusticare la risposta.
1)QUASI-HAM = {< G >: il grafo G = (E; V ) ha un ciclo semplice che contiene |V|-1 vertici}
2)4-HAM = {< G >: il grafo G = (E; V ) ha un ciclo semplice che contiene 4 vertici}
Pensandoci credo che il primo faccia parte di npc dato che è proprio come il problema del grafo hamiltoniano solo che invece di |V| vertici qui il ciclo può essere di |V|-1 , il secondo penso dia più semplice e possa essere della classe p. Ora...come giustifico le risposte?? Grazie a tutti anticipaamente