MO417 - Questão para a prova oral

Número: 2010-119

Enunciado: Considere as seguintes linguagens:

CAMINHO-MAIS-CURTO: {<G,u,v,k> | G é um grafo, u e v são dois vértices de G e existe um caminho de u a v com até k arestas}

CAMINHO-MAIS-LONGO: {<G,u,v,k> | G é um grafo, u e v são dois vértices de G e existe um caminho de u a v com pelo menos k arestas}

TRILHA-DE-EULER: {<G> | G é um grafo e existe uma trilha de Euler em G}

CICLO-HAMILTONIANO: {<G> | G é um grafo e existe um ciclo hamiltoniano em G}

CLIQUE: {<G,k> | G é um grafo e existe uma clique em G com pelo menos k vértices}

COBERTURA-POR-VÉRTICES: {<G,k> | G é um grafo e existe uma cobertura das arestas de G com até k vértices}

São NP-Completas:

1. CAMINHO-MAIS-CURTO, TRILHA-DE-EULER e CLIQUE
2. CLIQUE, CICLO-HAMILTONIANO e CAMINHO-MAIS-CURTO
3. COBERTURA-POR-VÉRTICES, CICLO-HAMILTONIANO e CAMINHO-MAIS-LONGO
4. TRILHA-DE-EULER, CICLO-HAMILTONIANO e CAMINHO-MAIS-LONGO
5. NDA

Ideia original de: Juliana Galvani Greghi