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

Passo 1

O enunciado pede um algoritmo que receba um caminho representado por uma sequência de vértices e determine se esse caminho forma um ciclo em um grafo. O conteúdo é teoria de grafos, mais especificamente a definição de ciclo simples, e vamos usar isso para estruturar nossa verificação.

Passo 2

Para que um caminho seja um ciclo simples, ele deve satisfazer três condições principais: (i) ter ao menos três arestas (ou seja, pelo menos quatro vértices na lista, já que o último repete o primeiro), (ii) o primeiro vértice coincidir com o último, e (iii) todos os vértices internos (exceto o primeiro/último) serem distintos. Vamos checar cada uma dessas condições em sequência.

Passo 3

Primeiro, vamos implementar as verificações básicas: calcular o tamanho da lista de vértices e confirmar se atende ao comprimento mínimo; comparar o primeiro e o último elemento da lista para garantir que fecham o ciclo.

Passo 4

Em seguida, para garantir a unicidade dos vértices internos, usamos um conjunto (set) para rastrear quais vértices já apareceram. Se algum vértice interno já tiver sido visto, concluímos que não é um ciclo simples. Se todas as checagens passarem, devolvemos verdadeiro; caso contrário, falso.

Resposta

função isCiclo(caminho):
// recebe uma lista de vértices [v₁, v₂, …, vₖ]
n ← comprimento(caminho)
// condição (i): pelo menos 3 arestas → n ≥ 4 vértices
se n < 4 então
retornar falso
// condição (ii): vértice inicial = vértice final
se caminho[0] ≠ caminho[n‒1] então
retornar falso
// condição (iii): vértices internos distintos
visitados ← conjunto vazio
para i de 0 até n‒2 faça
se caminho[i] ∈ visitados então
retornar falso
inserir caminho[i] em visitados
retornar verdadeiro

Exercícios relacionados