*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
sem vértices isolados tem ciclo euleriano (um circuito que percorre cada aresta exatamente uma vez) se e somente se
-
é fracamente conexo (o grafo subjacente não orientado é conexo), e - para todo vértice
, o grau de entrada é igual ao grau de saída .
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
em
.
- Cada vez que o ciclo chega a um vértice
, uma aresta entra em e, em seguida, uma aresta sai de . Como 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
- Além disso, como
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
seja fracamente conexo e que
para todo vértice
. Vamos construir um ciclo euleriano via o algoritmo de Hierholzer:
- Escolha um vértice
qualquer. - Construa um caminho fechado iniciando em
, sempre seguindo arestas não usadas até retornar a . Isso é sempre possível porque em cada vértice, enquanto houver saída disponível, há também uma entrada que equilibra. - Se esse ciclo não usar todas as arestas de
, existe alguma aresta não usada. Pela conexidade fraca, há um vértice 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 . - 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
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
,
.