*52. Demonstre que o algoritmo de Fleury sempre produz um ciclo euleriano.

Passo 1

O enunciado pede para mostrar que, em qualquer grafo conexo onde todos os vértices têm grau par (ou seja, um grafo euleriano), o algoritmo de Fleury constrói sempre um ciclo que percorre cada aresta exatamente uma vez. O algoritmo faz uma caminhada a partir de um vértice inicial u, e em cada passo escolhe uma aresta incidente ao vértice atual que não seja ponte, salvo se for a única disponível. Vamos provar isso por indução no número de arestas.

Passo 2

Base da indução: se o grafo G tem \lvert E(G)\rvert=0, não há arestas e o algoritmo simplesmente retorna o ciclo trivial que fica no vértice u. Assim a afirmação vale.

Passo 3

Hipótese indutiva: suponha que, em todo grafo euleriano com menos de p arestas, o algoritmo de Fleury gera um ciclo euleriano.
Agora considere um grafo G euleriano com \lvert E(G)\rvert = p>0. Escolhemos o vértice inicial u. Como \deg_G(u) é par, ou \deg_G(u)=0 (caso trivial) ou \deg_G(u)\ge2. Nesse último caso, existem pelo menos duas arestas em u, e pelo princípio de blocos de 2-arestas-conexidade, uma delas não é ponte. O algoritmo então escolhe uma aresta e=(u,v) que não seja ponte.

Passo 4

Removendo e, obtemos o grafo G' = G - e com p-1 arestas. Como e não era ponte, G' continua conexo. Além disso, a remoção de e faz
\deg_{G'}(u)=\deg_G(u)-1,\quad \deg_{G'}(v)=\deg_G(v)-1
tirando a paridade de ambos, enquanto todos os outros vértices mantêm grau par. Logo G' é semi-euleriano, tendo exatamente dois vértices de grau ímpar: u e v. Portanto, existe uma trilha euleriana de v até u em G'.
Pelo passo indutivo, aplicando Fleury em G' a partir de v encontramos essa trilha que percorre todas as arestas de G' uma vez.

Passo 5

Bastou então concatenar a aresta inicial u\to v com a trilha de v até u obtida em G'. O resultado é um ciclo em G que passa por todas as arestas exatamente uma vez. Assim, por indução, o algoritmo de Fleury sempre produz um ciclo euleriano.

Resposta

O algoritmo de Fleury sempre produz um ciclo euleriano.

Exercícios de Livros Relacionados