Ciclos de Euler em componentes com conexão dupla

9

Se um gráfico tiver um ciclo de Euler, os componentes biconetados também têm ciclos de Euler?

graph-theory eulerian-paths
fonte
11
Se esse é um problema de lição de casa, talvez seja melhor você tentar por conta própria? Um gráfico pode ter um ciclo de Euler, mas não parece seguir naturalmente que um subconjunto (mesmo um biconetado) deva. Você já tentou criar um exemplo contrário?

Respostas:

9

Sim. Se você começar com um ciclo de Euler para o gráfico e se restringir a um componente biconetado, então o que você tem ainda é um ciclo no componente biconetado (basicamente, se o ciclo de Euler deixar o vértice v no componente biconetado, você saberá que ele deve retornar para o componente biconetado através de v, caso contrário, poderíamos ampliar nosso componente biconetado - contradizendo sua máxima).


fonte