OLA, TD4 : Arbres
=================

Exercice 1 : Vrai ou faux
-------------------------

1) Vrai ! Il y a $n-1$ arêtes cf TD précédent
2) Pas déterminé dépend de l'arbre.
3) Vrai : par définition, un arbre esr connexe, donc si on rajoute une arête $a \rightarrow b$, comme il existe déjà un chemin $b\rightarrow^* a$ dans l'arbre en les raccordant on forme un cycle.
4) Faux : si on enlève un noeud interne, on obtient un graphe non connexe. Cela dit l'énonce devient vrai si on enlève des feuilles.

Exercice 2 : Bismuth
--------------------
Ce n'est pas un bon argument, cela n'implique pas que N n'a pas essayé de corrompre G.

Exercice 3 : Morpion
--------------------

1) a) La hauteur est de 9 : 9 coups au maximum peuvent être joués dans une partie.
b) Après $k$ coups déjà joué, il y a 9-k coups possibles (un par cas vide) pour le joueur dont c'est le tour.
c) Il y a au maximum $\sum_{k = 1}^9 \frac{9!}{k!}$ sommets et $9!$ feuilles.
2) Eloïse joue à toutes les profondeurs paires de l'arbre. Pour savoir qui doit jouer étant donné une configuration, il suffit de compter le nombre de X + nombre de O : si c'est pair c'est à Eloïse sinon, c'est à Abélard.
3) a) Possible si Eloïse joue "mal" : on dit que la position est gagnante quand c'est son tour de jouer si il existe un coup qui lui garantie de gagner, mais ce n'est pas dit que n'importe quel coup soit bon.
b) Impossible : par définition d'une position gagnante pour Eloïse, quoi que joue Adémard, Eloïse a encore une façon de gagner.
c) Impossible : si il existe un coup gagnant pour Eloïse, par définition, la position de départ n'est pas irrésolue.
d) Possible : il suffit que Abélard joue "mal" (c'est la situation symmétrique de la question a)
4) a) Gagnant !
b) Rien en particulier
c) Gagnant
d) Rien en particulier : Abélard pourrait jouer d'une façon qui écarte la partie de ce chemin.
e) Gagnant
f) Perdant
5) Il est facile de savoir si les feuilles sont gagnantes, perdantes ou irrésolues. Pour les noeuds internes supposons que l'on ait déterminé si les noeuds fils sont gagnants, perdants ou irrésolus. Alors un noeud est :
a) Gagnant si c'est à Eloïse de jouer et qu'au moins un des fils est gagnant, ou si c'est à Abélard de jouer et que tous les fils sont gagnants.
b) Perdant si c'est à Abélard de jouer et qu'au moins un des fils est perdant, ou si c'est à Eloïse de jouer et que tous les fils sont perdants.
c) Irrésolu dans les autres cas.
6) Eloïse gagne si au tour d'Eloïse, *il existe* un coup gagnante, ou si au tour d'Abélard *quel que soit* le coup choisi par Abélard, il est gagnant pour Eloïse.

Exercice 4 : Tournée Générale
-----------------------------

1) La couverture connexe est un sous-graphe connexe de $G$ qui contient tous les sommets, ce qui est suffisant pour que $G$ soit connexe car un chemin dans la couverture est aussi un chemin dans $G$.
2) Supposons qu'il y a ait un cycle $c$ dans une couverture connexe et retirons une arrête $a$ de ce cycle : on a encore une couverture connexe car dans tous les chemins entre deux sommets de $G$, on peut remplacer $a$ par $c \setminus a$.
3) Le graphe a un sommet et deux boucles de poids 1 a deux couvertures connexes minimales.
4)
5)
6) On garde l'arbre couvrant constitué des arêtes 2,3,4,5,6,9
7) Il y a essentiellement deux étapes : le tri des arêtes, qui peu être fait en $n \log(n)$ et la gestion des composantes connexes (appartenance et union) qui peut être fait de façon quasi-linéaire avec la structure d'union-find.
8) On prend le graphe complet dont les sommets sont les points de $E$ et les arêtes ont pour poids la distance euclidienne entre les deux points qu'elles relient. Dans le vocabulaie des graphes, il s'agit de trouver un cycle passant par tous les sommets de poid minimal.
9) Une tournée est une couverture connexe, elle a donc un poids supérieur à celui de la couverture connexe minimale.
10) Il suffit de faire un parcours en profondeur sur l'arbre qui est la couverture connexe minimale.

Exercice 5 : Classification hiérarchique
----------------------------------------

1)
2)
3)
4)
5)
6)
7)
8)
9)
10)