# OLA, TD2 : Graphes et chemins

## Exercice 1 : _Circuits hamiltoniens_
1) Cf dessin
3) Il y a $2^n$ sommets dans $HC_n$ le même nombre que de mots binaire de longueur $n$. Chaque sommet est de degré $n$ car il y a exactement $n$ mots binaires qui diffèrent d'une seule lettre d'un mot binaire donné (un par position). On sait que le nombre d'arètes est deux fois la somme des degrés. Ici on a $2^n$ sommets chacun de degré $n.$ Donc la somme des degrés est $n2^n$ donc le nombre d'arètes est $n2^{n-1}$.
4) Il suffit de suivre le périmètre du carré.
5) Une solution est donnée par le codage de Gray. En termes de graphes si on a un circuit hamiltonien $a_1 \rightarrow \dots \rightarrow a_{m-1} \rightarrow a_m$ de $HC_n$ (m = 2^n) pour obtenir les sommets de $HC_{n+1}$ on considère l'ensemble $\{0a_i\}_i \cup \{1a_i\}$ un circuit hamiltonien convenable pour $HC_{n+1}$ est $0a_1 \rightarrow \dots \rightarrow 0a_{m-1} \rightarrow 1a_{m-1} \rightarrow 1a_1 \rightarrow 0a_1$.
6) Cf dessin pour $HC_3$. Pour $HC_4$, rappelons nous comment générer le code Gray : les valeurs de $2^n$ à $2^{n+1}-1$ sont obtenues en rajoutant un 1 devant les valeurs de $0$ à $2^n$ dans l'ordre inverse. On obtient :
$$0,1,11,10,110,111,101,100,1100,1101,1111,1110,1010,1011,1001,1000$$

## Exercice 2 : _Circuits eulériens_
On note $G = (S, A)$. On le suppose fini.
1) Notons $\rho : s_1 \rightarrow \dots \rightarrow s_k \dots \rightarrow s_1$ le cycle eulérien (où on identifie le $s_1$ en première position avec celui en dernière position) et considérons un sommet $s$. Le degré de $s$ est égal au double du nombre d'occurence de $s$ dans $\rho$ (attention : dans $\rho$ ci-dessus, les $s_1$ en première et dernière position comptent pour 1 seule occurence à eux deux) : dans $r \rightarrow s \rightarrow t$, la flèche $r \rightarrow s$ contribue de $1$ au degré entrant et $s \rightarrow t$ de $1$ au degré sortant, donc l'occurence contribue de $2$ au degré total. Si on a une arête $a \rightarrow b$ avec $s = a$ ou $s = b$ elle apparaît déjà dans le cycle et on a donc déjà pris en compte sa contribution au degré de $s$.
2) L'ensemble des arêtes incidentes $A_s = \{a \in A |a$ est incidente à $s\}$ à un sommet $s$ peut être décomposé en $A_s = \{a \in A |a \in C\} \sqcup \{a \in A |a \notin C\}$. On sait que les arêtes des $A_s$ sont connectées un nombre pair de fois à $s$. Comme $C$ est un cycle eulérien du graphe $(S, C)$, on sait également, d'après la question 1, que la contribution au degré de $s$ des arêtes de $\{a \in A |a \in C\}$ est paire. Donc la contribution de $\{a \in A |a \notin C\}$ est également pair. Mais comme les arêtes de cette ensemble sont exactement celles connectées à $s$ dans $G' = (S, A \setminus C)$, le degré de $s$ dans $G'$ est pair.
3) On construit récursivement un cycle de la façon suivante. On choisit $d \rightarrow s_1$ une arête au hasard et on pose $\rho_1 = d \rightarrow s_1$. Soit $s \rightarrow t$ la dernière arêtes de $\rho_i$. Si $t = d$, on s'arrête. Sinon, par l'argument des ponts de Königsberg, $t$ est connecté à un nombre impair d'arêtes qui ne sont pas dans $\rho_i$, en particulier il n'y en a pas 0. On choisit au hasard $t \rightarrow u$ une telle arête et on pose $\rho_{i+1} = \rho_i \rightarrow u$. Il y a un nombre fini entier d'arêtes dans $G$ donc ce processus s'arrète. Notre raisonnement montre qu'il doit s'arréter sur $d$ : le $\rho$ final est bien un cycle.

4) a) C'est un raisonnement par l'absurde.

b) Tout est correct $C_1$ existe et sous réserve de l'hypothèse que $C_1$ ne contient pas toutes les arêtes $C_2$ aussi. En revanche, rien ne prouve que $C_1 \cup C_2$ soit un cycle.

c) La preuve de la question 3 montre en fait le résultat plus fort suivant : "Dans tout graphe non orienté possédant au moins un arète, dont tous les sommets sont de degré pair, pour tout sommet $d$ connecté à un arète, il existe un cycle passant par $d$" : il suffit de prendre l'arête connectée à $d$ à la première étape de notre construction. La démonstration reste essentiellement la même : soit $a \rightarrow b$ une arête de $G$ non contenue dans $C_1$ et soit $s$ un sommet contenu dans $C_1$. Par connexité de $G$, il existe un chemin $a \rightarrow b = s_0 \rightarrow \dots \rightarrow s_i \rightarrow \dots \rightarrow s_k = s$. Soit $j$ le $i$ minimal tel que $s_i$ est contenu dans $C_1$ et $d = s_j$. On peut appliquer la question 3 modifiée pour trouver un $C_2$ passant par $d$, ce qui conduit à la même absurdité !

## Exercice 3 : _Calculs de distance_
1) Ordonner les sommets, définir une matrice $W^k$ pour $k > 0$ dont le coefficient $W^k_{ij}$ contient $\inf$ s'il n'y a pas de chemin entre $i$ et $j$ qui passe (au sens strict, ie il peut y finir ou y commencer) par des sommets numérotés au plus $k$ et le poid minimal de ces chemins sinon. On définit également $W^0$ la matrice d'adjacence pondérée ($W^0_{ij} =$ poids de l'arète $ij$ si elle existe et $\inf$ sinon).

for k de 1 à nombre de sommets:
    for sommet i:
        for sommet j:
            W^k_{ij} = min(W^{k-1}_{ij}, W^{k-1}_{ik} + W^{k-1}_{kj})

2) Oui : supposons qu'un chemin de poids minimal passe par une boucle. En retirant la boucle on obtient un chemin entre les deux mêmes extrémités de poids inférieur ou égal. Dans le cas inférieur, par minimalité, c'est absurde. Dans le cas égal, on peut enlever la boucle sans rien changer. On peut donc supposer qu'il ne passe pas par une boucle. De même si on a deux arètes $a \rightarrow b$ de poids $p_1 > p_2$, on peut toujours remplacer l'arète de poids $p_1$ par celle de poid $p_2$ en diminuant le poid du chemin. Donc un chemin de poids minimal utilisera l'arète $a \rightarrow b$ de poids $p_2$.
On peut donc modifier le graphe en a) retirant les boucles et en b) retirant les arètes multiples de poids non minimal. Le graphe obtenu n'est évidemment pas le même, mais pour les raisons précédemment évoquées la réponse donnée par Roy-Warshall est la même et correcte.