Cycles d'Euler dans les composants biconnectés

9

Si un graphique a un cycle d'Euler, les composants biconnectés ont-ils également des cycles d'Euler?

graph-theory eulerian-paths
la source
1
S'il s'agit d'un problème de devoirs, peut-être qu'il vaut mieux que vous l'essayiez vous-même? Un graphique peut avoir un cycle d'Euler, mais il ne semble pas suivre naturellement qu'un sous-ensemble (même biconnecté) devrait l'être. Avez-vous essayé de trouver un contre-exemple?

Réponses:

9

Oui. Si vous commencez avec un cycle d'Euler pour le graphique et que vous vous limitez à un composant biconnecté, alors ce que vous avez est toujours un cycle sur le composant biconnecté (en gros, si le cycle euler laisse le sommet v dans le composant biconnecté, alors vous savez qu'il doit retourner au composant biconnecté via v, sinon nous pourrions agrandir notre composant biconnecté - contredisant sa maximalité).


la source