"Circuitos de Euler em Grafos"
Resumo.
Um Circuito de Euler é um ciclo que passa por cada aresta do grafo
exatamente uma vez. Por um teorema elementar, um grafo orientado
conexo contém um Circuito de Euler, se e somente se, para cada vértice v, o
grau de entrada de v é igual ao grau de saída de v.
Apresentaremos um algoritmo PRAM que utiliza, para encontrar o
Circuito de Euler, a técnica Euler-tour em árvores e o algoritmo de
Árvore Geradora.
Um Euler-tour em um grafo ou grafo dirigido é um caminho que passa
por cada aresta exatamente uma vez e retorna ao seu ponto de partida. Uma
árvore geradora de um grafo G = (V, E), é um subconjunto acíclico e
conexo T de E, que conecta todos os vértices de G.