*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
, 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
tem
, não há arestas e o algoritmo simplesmente retorna o ciclo trivial que fica no vértice
. Assim a afirmação vale.
Passo 3
Hipótese indutiva: suponha que, em todo grafo euleriano com menos de
arestas, o algoritmo de Fleury gera um ciclo euleriano.
Agora considere um grafo euleriano com
. Escolhemos o vértice inicial
. Como
é par, ou
(caso trivial) ou
. Nesse último caso, existem pelo menos duas arestas em
, e pelo princípio de blocos de 2-arestas-conexidade, uma delas não é ponte. O algoritmo então escolhe uma aresta
que não seja ponte.
Agora considere um grafo
Passo 4
Removendo
, obtemos o grafo
com
arestas. Como
não era ponte,
continua conexo. Além disso, a remoção de
faz
tirando a paridade de ambos, enquanto todos os outros vértices mantêm grau par. Logo
é semi-euleriano, tendo exatamente dois vértices de grau ímpar:
e
. Portanto, existe uma trilha euleriana de
até
em
.
Pelo passo indutivo, aplicando Fleury em
a partir de
encontramos essa trilha que percorre todas as arestas de
uma vez.
Passo 5
Bastou então concatenar a aresta inicial
com a trilha de
até
obtida em
. O resultado é um ciclo em
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.