*51. Expresse o algoritmo de Fleury em pseudocódigo.

Passo 1

O enunciado pede para escrever em pseudocódigo o algoritmo de Fleury, que constrói um caminho ou circuito euleriano em um grafo conexo. Para isso precisamos dos conceitos de grafo Euleriano (grau par em todos os vértices, ou exatamente dois de grau ímpar), detecção de ponte (aresta cuja remoção aumenta o número de componentes) e operações básicas em grafos (grau, listas de adjacência, remoção de aresta).

Passo 2

Primeiro verificamos se o grafo G tem caminho ou circuito euleriano:
  • Se não tiver 0 ou 2 vértices de grau ímpar, o algoritmo não é aplicável.
  • Se tiver 0 vértices de grau ímpar, vamos gerar um circuito; se tiver 2, geramos um trilha começando em um dos vértices de grau ímpar.
    Em seguida inicializamos:
    - v \leftarrow vértice inicial
    - \mathrm{path} \leftarrow lista vazia para acumular arestas na ordem visitada

Passo 3

Agora entramos no laço principal:
Enquanto houver arestas incidentes em v:
  1. Examine cada aresta e=(v,u) em \mathrm{Adj}[v].
  2. Escolha a primeira que não seja ponte, a menos que seja a única aresta restante em v.
  3. Adicione e ao fim de \mathrm{path}.
  4. Remova e de G.
  5. Atualize v\leftarrow u.

Passo 4

Quando não restarem arestas incidentes em v, o laço termina e \mathrm{path} contém o caminho (ou circuito) euleriano de G.

Resposta

Algoritmo Fleury G
se número de vértices de grau ímpar \neq 0 e \neq 2
então
retornar “não é Euleriano”
fim se
se existem 2 vértices de grau ímpar
então v \leftarrow um vértice de grau ímpar
senão
v \leftarrow qualquer vértice de grau não-nulo
fim se
\mathrm{path} \leftarrow lista vazia
enquanto grau v > 0 faça
para cada aresta e=(v,u) em \mathrm{Adj}[v] faça
se e não é ponte em G ou é a única aresta incidente em v então
escolha e e interrompa o laço interno
fim se
fim para
\mathrm{path}.\text{append}(e)
remover e de G v \leftarrow u
fim enquanto
retornar \mathrm{path}

Exercícios de Livros Relacionados