Julien Sopena

TD 04 – Théorie des graphes : Graphes Eulériens

Exercice 1: Parcours d'un musée

Question 1.1 )

Le conservateur d'un musée, dont le plan est donné dans la figure Figure 1, désire réorganiser le parcours type de son musée. Peut-il proposer un parcours qui emprunte une et une seule fois chaque porte tout en revenant au point de départ ?
Figure 1: Plan du musée

Question 1.2 )

Où faudrait-il placer l'entrée et la sortie pour pouvoir organiser un parcours qui emprunte une et une seule fois chaque porte ?

Exercice 2: Jeux de Dominos

Question 2.1 )

Peut-on réaliser une boucle utilisant tous les dominos d'un jeux dont les faces sont numérotées 0, 1, 2, 3, 4, 5 ou 6

Question 2.2 )

Généralisez ce résultat pour un jeu de dominos quelconque dont les faces seraient numérotées de 0 à n.

Question 2.3 )

Déduire de cette exercice une condition nécessaire et suffisante pour qu'un graphe complet soit Eulérien.

Designed by OWSD.org. Valid CSS & XHTML
Ce site et l'ensemble de son contenu est mis à disposition sous un contrat Creative Commons.
Creative Commons License