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


==Question 1==
* Quelconque
* Connexe
* Non Connexe
* Biparti

	Remarque :
	Le graphe acyclique est impossible, car la somme des dégrés fait 16.
	Le graphe a donc 8 arêtes (nombre d'arêtes = somme des dégrés / 2) pour 8 sommets (nombre de degrés dans la liste).
	Or un graphe acyclique à n sommets a au plus n-1 arêtes (cf propriété du cours que la question 12 cherche à démontrer).
	Donc un graphe acyclique à 8 sommets devrait avoir au plus 7 arêtes.

==Question 2==
* Rien de tout cela

	Raisonnement : 
	Si on veut passer sur tous les traits en gras (et uniquement les traits en gras)
	Alors il n'y a aucun moyen de ne passer qu'une fois sur chaque arête (donc pas une marche simple)
	Ni de passer une seule fois sur chaque sommets (donc pas un chemin, et donc pas un cycle, puisqu'un cycle est un chemin particulier qui revient à son point de départ)
	
==Question 3==
* 4

	Raisonnement : 
	Le diamètre d'un graphe est la distance maximale entre 2 sommets (le plus long des plus courts chemins entre sommets).
	On commence par identifier les 2 sommets les plus éloignés possibles => on prend 2 pointes opposées.
	On cherche le plus court chemin entre ces 2 sommets => on peut les relier en passant par 4 arêtes.

	Autre méthode :
	On pouvait faire plus formel et moins intuitif (car on n'a pas vraiment montré que 2 pointes opposées sont les sommets les plus éloignés du graphe, on l'a juste fortement supposé) :
	On pouvait remarquer qu'il n'existe 2 types de sommets dans ce graphe : les 6 centres et les 6 pointes.
	Les 6 centres sont identiques à une rotation de graphe près, idem pour les 6 pointes.
	On peut donc prendre n'importe quel centre, et calculer rapidemment ses distances (plus courts chemins) avec tous les autres sommets => on trouve des distances entre 1 et 3.
	Pareil en prenant n'importe quelle pointe, on calcule rapidemment ses distances avec tous les autres sommets => on trouve des distances entre 1 et 4.
	Donc le diamètre du graphe est 4 (la plus grande des distances trouvées).
	
==Question 4==
* Biparti
* Acyclique

==Question 5==
* Faux

	Raisonnement :
	Il faut trouver un contre-exemple.
	Il suffit d'essayer avec n'importe quel n supérieur ou égale à 1 pour se rendre compte que c'est impossible.
	Par exemple, pour n=1 ou n=2, on ne peut même pas faire de graphe avec n sommets et n arêtes.
	Pour n=3, on arrive à faire un graphe, mais pas sans cycle (on ne peut faire qu'un triangle).
	
	Remarque :
	Il suffisait de trouver un seul n pour lequel cette propriété est fausse, et on vient déjà d'en trouver 3.
	Mais en réalité, cette propriété est fausse pour tout n, à cause de la (vraie) propriété déjà évoquée à la question 1 :
	Un graph acyclique à n sommet a au maximum n-1 arêtes.
	
==Question 6==
* 2^16

	Raisonnement :
	Pour chacune des 16 arêtes du graphe, on peut soit la conserver, soit ne pas la conserver.
	Pour une arêtes, on a donc 2 possibilités (la conserver, ou ne pas la conserver)
	Pour 2 arêtes, on a 4 possibilités (conserver les 2, ou aucune, ou seulement la 1ère, ou seulement la 2nde)
	Pour 3 arêtes, 8 possibilités.
	etc.
	Et pour 16 arêtes, 2^16 possibilités.
	
	Remarque :
	On peut aussi visualiser ce résultat en associant à chaque sous-graphe un nombre binaire à 16 bits.
	Chaque bits correspond à une arête du graphe : il est à 0 si l'arête est absente, ou à 1 si elle est présente.
	Il y a donc autant de sous-graphes de ce graphe à 16 arêtes que de nombres binaire à 16 bits, soit 2^16.
	Pour les matheux, on peut dire qu'on a fait une bijection entre les sous-graphes d'un graphe à n arêtes et les nombres binaires à n bits.

==Question 7==
* 8 parmi 10
(ce qui s'écrit entre parenthèses, avec le 10 au dessus et le 8 en dessous)

	Attention au piège :
	Ici, le nombre d'arêtes à conserver est imposé, contrairement à la question précédente.

	Raisonnement :
	On veut compter tous les graphes possibles qui conservent 8 arêtes parmi les 10 du graphe.
	Ce qui revient à compter de combien de façons on peut choisir 8 parmi 10.

	Remarque :
	Si on raisonne avec le triangle de Pascal :
	Dans la question 6, on faisait la somme de tous les nombres de la lignes n°16 (car on considérait tous les nombres d'arêtes possibles parmi 16).
	Dans la question 7, on ne regarde que le nombre à la ligne n°10 et à la colonne n°8 (car on ne considère que les graphes à 8 arêtes parmi 10).

==Question 8==
* Rien de tout cela

	Raisonnement simple :
	On peut simplement essayer de dessiner le graphe pendant 2 minutes, se rendre compte qu'on arrive pas à en faire un cette suite de degrés, et en déduire quelle était la réponse attendue.
	Mais on peut aussi se demander pourquoi c'est impossible...
	
	Raisonnement un peu plus avancé :
	La somme de tous les degrés fait 15, qui est un nombre impair.
	Or, la somme des degrés d'un graphe ne peut jamais être impaire, puis qu'elle est égale au double des arêtes.
	Un graphe avec cette suite de degrés est donc impossible.
	
	Raisonnement encore plus avancé :
	Cette suite de degrés contient 5 degrés impairs, et 5 est lui-même un nombre impair.
	Or une somme qui contient un nombre impair de termes impairs est elle-même impaire.
	Donc, sans même faire d'addition, en comptant simplement les degrés impairs, on pouvait déduire que ce graphe était impossible à réaliser.

==Question 9==
* 3

	Attention au piège :
	Ne pas oublier de compter le sommet isolé à droite.

==Question 10==
* Connexe

==Question 11==
* Faux

	Raisonnement :
	Il faut trouver un contre-exemple.
	Si on dessine un graphe à 5 sommets, avec 3 sommets reliés entre eux d'un coté (un triangle) et 2 sommets reliés entre eux de l'autre coté.
	Alors on a bien 4 arêtes (n-1) mais le graphe n'est pas connexe.

==Question 12==
* Faux

	Raisonnement :
	La propriété énoncée est correcte.
	La preuve par récurrence est également correcte.
	Mais elles ne correspondent pas : ce sont 2 propriétés différentes.
	La preuve par récurrence montre simplement qu'il est possible de construire un graphe acyclique à n sommets avec n-1 arêtes
	(et elle donne une méthode simple pour le faire, en plaçant chaque nouvelle arête sur le nouveau sommet, en bref on construit un arbre).
	Pour montrer qu'un graphe acyclique a au plus n-1 arêtes, il faudrait plutôt montrer que si on ajoute une arête de plus sans ajouter de sommet, alors on crée forcément un cycle.