L3 Info Paris 7
Maths Discrètes - QCM n°3 - 2017-2018
Eléments de corrections (non officiels)
========================================================================================


==Question 1==
* 4

==Question 2==
* Vrai

	Voir l'image suivante (en haut à droite : graphe Eulérien mais non Hamiltonien)
	http://info.paris7.free.fr/L3/MD5/MD5-graphs.jpg
	
==Question 3==
* Non pour tous

	Raisonnement : 
	Il n'y a qu'un seul sommet de degré impair, ce graph est donc impossible à dessiner.
	(pour plus de détails, cf QCM n°2 - Question n°8)
	
==Question 4==
* Quelconque
* Connexe

	Raisonnement : 
	En essayant de dessiner les 3 sommets (4, 3, 3) on se rend vite compte qu'ils forment obligatoirement un triangle.
	Sur ce triangle viendront se greffer les 4 sommets de degré 1 (deux sur le sommet 4 et un sur chacun des sommets 3).
	Cette construction possible est connexe (ce qui exclu la réponse Non Connexe).
	Le triangle exclu les réponses Biparti, Acyclique et Arbre.
	D'autre part, on a des sommets de degrés impairs (donc pas Eulérien) et on en a plus de 2 (donc pas pseudo-Eulérien).

==Question 5==
* Eulérien
* Pseudo-Eulérien
* Pseudo-Hamiltonien

	Comme dans la question 2, il s'agit du graph en haut à droite de cette image (qui n'est toujours pas Hamiltonien)
	http://info.paris7.free.fr/L3/MD5/MD5-graphs.jpg

==Question 6==
* Vrai
	
	Raisonnement : 
	Il semble qu'il manque un morceau de la question, mais supposons que n soit nombre de sommets du graph.
	Il existe, pour tout nombre de sommet n, un arbre (graph sans cycle) pseudo-hamiltonien (avec un chemin qui passe exactement une fois par chaque sommet) :
	Il suffit de dessiner les n sommets en ligne (disposition aussi appelée "arbre dégénéré" ou "arbre filiforme").
	
==Question 7==
* Eulérien
* Pseudo-Eulérien

	Raisonnement : 
	Tous les sommets sont de degré pair, donc Eulérien, et donc Pseudo-Eulérien.
	Je n'ai pas de preuve formelle que le graph ne soit pas Hamiltonien (ni même Pseudo-Hamiltonien), mais plutôt une forte conjecture :
	Pour parcourir tous les sommets, les 2 sommets de degré 6 devront être visités en tout au moins 3 fois :
	* au moins une fois pour atteindre chacun des 2 sommets du centre (pour y aller ou en sortir)
	* au moins une fois pour passer des 3 sommets Nord-Est du carré aux 3 sommets Sud-Est
	Donc, si on doit visiter 3 fois un ensemble de 2 sommets, il y en a au moins un qu'on a visité 2 fois.
	Donc un chemin qui passe par tous les sommets de ce graph n'est pas Hamiltonien.
	(En cherchant un peu, on trouverait surement une preuve plus simple et plus formelle)
	
==Question 8==
* 2	
	
	(pour plus de détails, cf QCM n°2 - Question n°3)

==Question 9==
* Connexe
* Acyclique
* Biparti

	Remarque :
	Attrapez le graph par un bout et secouer le pour le défroisser : vous verrez que c'est simplement 5 sommets disposés en ligne
	(disposition aussi appelée "arbre dégénéré" ou "arbre filiforme")
	
==Question 10==
* Pseudo-Hamiltonien

	Raisonnement : 
	Il a des sommets de degré impair (donc pas Eulérien) et il y en a plus de 2 (donc pas pseudo-Eulérien).
	C'est un graph pseudo-Hamiltonien car on peu trouver un chemin qui parcours une seule fois chaque sommet (serpentant en forme de S par exemple, ou en forme de spirale en partant du centre).
	Encore une fois, je n'ai pas de preuve formelle que le graph n'est pas Hamiltonien, mais cela parait évident : on trouve vite tous les chemins qui passent une seule fois par chaque sommet, et on se rend compte qu'aucun ne revient à son point de départ.
	
==============	
Suite non traitée pour le moment