1. Escreva um algoritmo que recebe um caminho e verifica se ele é um ciclo simples

Passo 1

A questão pede um algoritmo que receba um caminho em um grafo e diga se esse caminho forma um ciclo simples (ou seja, começa e termina no mesmo vértice, todos os vértices internos são distintos e o comprimento mínimo é 3). Para isso vamos usar estruturas básicas: listas, conjuntos e comparações.

Passo 2

Vamos primeiro verificar se o caminho tem comprimento suficiente e fecha em si mesmo. Um ciclo simples precisa ter pelo menos 3 arestas, então a lista de vértices deve ter tamanho ≥ 4 (pois o último repete o primeiro). Também conferimos se o primeiro vértice é igual ao último.
Em seguida, precisamos garantir que nenhum dos vértices internos (todos exceto o último) apareça mais de uma vez. Para isso, percorremos os vértices de índice 1 até n−1 e vamos inserindo cada um num conjunto. Se em algum momento o vértice já estiver no conjunto, o ciclo não é simples.

Passo 3

Se todas as verificações anteriores passarem, concluímos que o caminho é um ciclo simples.
A implementação final junta esses passos em pseudocódigo, retornando verdadeiro só se todas as condições forem satisfeitas.

Resposta

Algoritmo isSimpleCycle(path):
// path é uma lista de vértices [v₁, v₂, …, vₖ]
n ← tamanho(path)
// 1) Verificar tamanho mínimo e fechamento
se n < 4 então
retorne falso
fim se
se path[1] ≠ path[n] então
retorne falso
fim se
// 2) Verificar unicidade dos vértices internos
S ← conjunto vazio
para i de 1 até n−1 faça
se path[i] ∈ S então
retorne falso
fim se
inserir path[i] em S
fim para
// Se passou em tudo, é ciclo simples
retorne verdadeiro

Exercícios relacionados