Procedimento para encontrar decomposição
de G em ciclos disjuntos.
Dados:
G = grafo com todos os vértices de grau par;
Declaração de variaveis:
S = lista de ciclos de G;
H = grafo parcial de G;
a = aresta de G;
c = cadeia elementar de G;
Inicialização:
S={ };
H=G;
WHILE ( H tiver arestas ) {
a= escolha aleatória de uma aresta em H;
c={a};
H= grafo parcial de G obtido por remoção das arestas
em S, e em c ;
WHILE ( c não fôr um ciclo ) {
//** as extremidades de c têm grau ímpar em H. **
a= escolha de uma aresta de H com extremidade comum a c;
c=c + {a} ;
H = grafo parcial de G obitdo de H removendo
a aresta a; }
S=S+{c} ; }
RETURN S;
Verifique na animação seguinte a aplicação do algorítmo acima,
que dá origem a uma decomposição em três ciclos: vermelho, verde e branco.
Em cada instante são mostrados os graus de todos os vértices em H,
que é o grafo parcial de G formado pelas arestas amarelas.
Para correr a animação coloque o rato sobre a figura.
A animação pára sempre que afaste o rato da figura.
