*16. Mostre que um multigrafo orientado que não tem vértices isolados tem um ciclo euleriano se e somente se o grafo for fracamente conexo e o grau de entrada e o grau de saída de cada vértice forem iguais.

Passo 1

Resumindo, queremos provar que um multigrafo orientado G sem vértices isolados tem ciclo euleriano (um circuito que percorre cada aresta exatamente uma vez) se e somente se
  1. G é fracamente conexo (o grafo subjacente não orientado é conexo), e
  2. para todo vértice v, o grau de entrada \deg^-(v) é igual ao grau de saída \deg^+(v).
O conteúdo aqui é a teoria de ciclos eulerianos em digrafos, usando argumentos de contagem de arestas em cada vértice e o algoritmo de Hierholzer para construir o ciclo.

Passo 2

Prova da condição necessária. Suponha que exista um ciclo euleriano \mathcal{C} em G.
  • Cada vez que o ciclo chega a um vértice v, uma aresta entra em v e, em seguida, uma aresta sai de v. Como \mathcal{C} passa por todas as arestas exatamente uma vez e retorna ao ponto de partida, sobra em cada vértice o mesmo número de entradas e saídas. Logo
\deg^-(v)=\deg^+(v),\quad\forall v.
  • Além disso, como \mathcal{C} visita todas as arestas, conecta todos os vértices que tenham arestas incidentes. Como não há vértices isolados, o grafo subjacente fica todo percorrido, o que implica conexidade fraca.

Passo 3

Prova da condição suficiente. Agora suponha que G seja fracamente conexo e que \deg^-(v)=\deg^+(v) para todo vértice v. Vamos construir um ciclo euleriano via o algoritmo de Hierholzer:
  1. Escolha um vértice u qualquer.
  2. Construa um caminho fechado iniciando em u, sempre seguindo arestas não usadas até retornar a u. Isso é sempre possível porque em cada vértice, enquanto houver saída disponível, há também uma entrada que equilibra.
  3. Se esse ciclo não usar todas as arestas de G, existe alguma aresta não usada. Pela conexidade fraca, há um vértice w no ciclo atual que é incidente a uma aresta ainda não usada. Inicie daí outro ciclo fechado usando apenas arestas não usadas e reinserta esse trecho em \mathcal{C}.
  4. Repita até não sobrar aresta não usada.
Cada aresta entra exatamente uma vez em algum dos ciclos e todo encaixe é possível graças a \deg^-(v)=\deg^+(v) e à fraqueza de conexidade que garante atingir vértices com arestas remanescentes.

Passo 4

Concluímos que, sob as hipóteses dadas, o algoritmo de Hierholzer constrói um ciclo que percorre cada aresta exatamente uma vez, ou seja, um ciclo euleriano.

Resposta

Um multigrafo orientado sem vértices isolados admite ciclo euleriano se, e somente se, é fracamente conexo e, para todo vértice v, \deg^-(v)=\deg^+(v).

Exercícios de Livros Relacionados