34.1-2

Seja G = (V, E) um grafo não-orientado.

Um ciclo simples em G é uma sequência de vértices v1, v2, ..., vk tal que k ≥ 3, além disso v1, v2, ..., vk é um caminho simples de v1 até vk e existe a aresta (vk, v1).

O tamanho de um tal ciclo é k.

Um ciclo máximo (ou ciclo mais longo) em G é um ciclo de tamanho máximo em G.

O problema do ciclo mais longo é encontrar um ciclo máximo em G (caso exista).

O problema de decisão associado é: dados G e um inteiro k ≥ 0, é verdade que o tamanho de um ciclo máximo em G é maior ou igual a k?

A linguagem associada é: { <G, k> : G é um grafo não-orientado, k ≥ 0 é um inteiro e o tamanho de um ciclo máximo em G é maior ou igual a k }.