Vocabulaire et propriétés

Rédaction attendue. Les degrés se lisent dans le tableau : $d(A)$ $=d(B)$ $=d(C)$ $=d(D)$ $=d(E)$ $=d(F)$ $=3$ et $d(G)=2$. Leur somme vaut $6\times 3+2=20$. D’après le lemme des poignées de main, $20=2m$, donc le quartier compte $m=10$ rues.

Rédaction attendue. Depuis A, on atteint tous les carrefours : A–B, A–C, A–D, A–B–E, A–C–F et A–D–G. Deux carrefours quelconques sont donc reliés par une chaîne passant par A : le graphe est connexe. Les six carrefours A, B, C, D, E et F sont de degré $3$, impair.

Rédaction attendue. Le graphe est connexe et a six sommets de degré impair : ce n’est ni $0$ ni $2$, donc, d’après le théorème d’Euler, il n’a ni cycle ni chaîne eulérienne. Parcourir une rue deux fois revient à doubler l’arête correspondante : cela augmente de $1$ le degré de ses deux extrémités, donc change la parité de deux sommets exactement. Pour un parcours fermé, il faut rendre pairs les six carrefours A, B, C, D, E et F : chaque rue doublée en corrige au plus deux, il en faut au moins ${\displaystyle \frac{6}{2}}=3$. Trois suffisent : en doublant A–B, C–F et D–E, les degrés de A à F passent à $4$, celui de G reste $2$, et le graphe reste connexe ; d’après le théorème d’Euler, un cycle eulérien emprunte alors toutes les arêtes, et il peut partir de G.

Elle parcourt une fois chacune des $10$ rues et une seconde fois les $3$ rues doublées : $10+3=13$ rues.

Rédaction attendue. Une chaîne eulérienne non fermée existe lorsqu’il reste exactement deux sommets de degré impair : il faut corriger quatre des six carrefours impairs, donc doubler au moins ${\displaystyle \frac{4}{2}}=2$ rues. Deux suffisent : en doublant A–B et C–F, seuls D et E restent de degré impair, et la seconde saleuse peut tout saler en $12$ passages, de D à E.

Les dominos non doubles correspondent aux paires de nombres distincts : ${\displaystyle \left(\genfrac{}{}{0ex}{}{7}{2}\right)}$ $={\displaystyle \frac{7\times 6}{2}}$ $=21$. Il y a aussi $7$ doubles. Le jeu compte $21+7=28$ dominos.

Chaque nombre est relié aux $6$ autres par un domino, et porte une boucle (son double), qui compte pour $2$ : $6+2=8$. Contrôle : $7\times 8=56=2\times 28$.

Rédaction attendue. Deux nombres quelconques sont reliés par un domino : le graphe est connexe. Tous les sommets sont de degré $8$, pair : aucun n’est impair. D’après le théorème d’Euler, le graphe admet un cycle eulérien ; une ligne fermée de dominos est exactement un cycle qui emprunte chaque arête une fois, donc les $28$ dominos se disposent en boucle.

${\displaystyle \left(\genfrac{}{}{0ex}{}{6}{2}\right)}=15$ dominos non doubles et $6$ doubles : $15+6=21$.

Rédaction attendue. Chaque nombre est relié aux $5$ autres et porte une boucle : degré $5+2=7$, impair. Les $6$ sommets sont de degré impair : ni $0$ ni $2$. D’après le théorème d’Euler (le graphe est connexe), il n’a ni cycle ni chaîne eulérienne : on ne peut pas aligner tous les dominos.

Rédaction attendue. Retirer un double enlève $2$ au degré d’un sommet : cela ne change aucune parité. Retirer un domino non double change la parité de ses deux nombres. Pour passer de $6$ sommets impairs à $2$, il faut retirer au moins ${\displaystyle \frac{6-2}{2}}=2$ dominos. Deux suffisent : sans 0–1 et 2–3, seuls $4$ et $5$ restent de degré impair, et le graphe reste connexe. La ligne compte alors $21-2=19$ dominos, avec un $4$ à un bout et un $5$ à l’autre.

Chaque paire d’équipes joue un match : si l’on oublie le sens des arcs, on obtient le graphe complet $K_5$, qui a ${\displaystyle \frac{5\times 4}{2}}=10$ arêtes. On compte bien $10$ arcs.

C a battu D et E : $d^{+}(C)=2$. En fait, chaque équipe a gagné $2$ matchs et en a perdu $2$ ; la somme des degrés sortants vaut $5\times 2=10$, le nombre d’arcs.

Rédaction attendue. Les arcs A → C, C → E, E → B, B → D et D → A figurent tous dans la liste des résultats, ils se suivent dans le bon sens, le chemin revient en A et n’emprunte pas deux fois le même arc : c’est un circuit, de longueur $5$, qui passe une fois par chacune des $5$ équipes. On peut donc ranger les équipes en rond de sorte que chacune ait battu la suivante.

Rédaction attendue. Chaque match donne exactement une victoire : le nombre total de victoires est le nombre de matchs, ${\displaystyle \frac{6\times 5}{2}}=15$ (c’est la somme des degrés sortants, égale au nombre d’arcs). Si les $6$ équipes avaient toutes $v$ victoires, on aurait $6v=15$ ; or $15$ n’est pas divisible par $6$. C’est impossible.

Rédaction attendue. Supposons deux équipes X et Y invaincues. Elles se sont rencontrées, et ce match a un vainqueur : l’arc X → Y ou l’arc Y → X existe. L’une des deux a donc perdu, ce qui contredit l’hypothèse. Il y a au plus une équipe invaincue. Avec $8$ équipes, une équipe invaincue a gagné ses $7$ matchs : son degré sortant vaut $7$.

Les sommets sont les cinq zones de terre N, S, I, J, K, et chaque pont est une arête entre les deux zones qu’il relie. Certaines paires de sommets sont reliées par deux arêtes (N et I, S et K, I et J) : c’est un multigraphe, à $10$ arêtes.

Chaque pont compte pour $1$ dans le degré de chacune de ses extrémités : $d(N)=2+1=3$, $d(S)=1+2=3$, $d(I)=2+2+1=5$, $d(J)=1+1+2+1=5$ et $d(K)=2+1+1=4$. La somme vaut $3+3+5+5+4=20=2\times 10$ : le lemme est vérifié.

Rédaction attendue. Le graphe est connexe : J est relié à N, S, I et K. Une telle promenade serait une chaîne eulérienne. Or N, S, I et J sont de degré impair : il y en a $4$, ni $0$ ni $2$. D’après le théorème d’Euler, aucune promenade de ce type n’existe.

Rédaction attendue. Le pont N–S porte $d(N)$ et $d(S)$ à $4$ ; I et J restent de degré $5$. Le graphe, toujours connexe, a exactement deux sommets de degré impair, I et J : d’après le théorème d’Euler, il existe une chaîne eulérienne, et ses extrémités sont I et J. Partie de I, la promenade se termine en J. Par exemple I–J–I–K–J–N–I–N–S–K–S–J : elle emprunte les deux ponts I–J, puis I–K, J–K, N–J, les deux ponts N–I, le pont N–S, les deux ponts S–K et enfin S–J, soit les $11$ ponts, chacun une fois.

Fermer un pont diminue de $1$ le degré de ses deux extrémités. Pour une chaîne eulérienne de N à S, il faut que N et S restent impairs et que I et J deviennent pairs : le pont fermé doit relier I et J. On ferme donc l’un des deux ponts entre I et J ; il reste $9$ ponts et seuls N et S sont de degré impair.

Rédaction attendue. Une promenade fermée est un cycle eulérien : tous les degrés doivent être pairs. Les quatre sommets N, S, I et J sont de degré impair, et chaque pont construit change la parité de deux sommets exactement : il en faut au moins ${\displaystyle \frac{4}{2}}=2$. Deux suffisent : avec un pont N–S et un troisième pont I–J, les degrés deviennent $4$, $4$, $6$, $6$ et $4$, tous pairs, et le graphe reste connexe. D’après le théorème d’Euler, une promenade fermée existe.

Rédaction attendue. Les degrés se lisent dans le tableau : $d(A)=2$, $d(B)=4$, $d(C)=4$, $d(D)=2$, $d(E)=4$, $d(F)=4$, $d(G)=3$, $d(H)=3$, $d(I)=2$ et $d(J)=2$. Leur somme vaut $30$ ; d’après le lemme des poignées de main, $2m=30$, donc il y a $15$ liaisons.

Rédaction attendue. Depuis B, on atteint tous les capteurs : B–A, B–C, B–E, B–F, B–C–D, B–C–G, B–C–D–H, B–E–I et B–C–D–H–J. Le graphe est donc connexe. Seuls G et H sont de degré impair ($3$).

Rédaction attendue. Le graphe est connexe et a exactement deux sommets de degré impair, G et H. D’après le théorème d’Euler, il admet une chaîne eulérienne d’extrémités G et H : partie de G, elle se termine en H. Par exemple G–C–B–A–E–B–F–C–D–H–J–I–E–F–G–H, qui emprunte C–G, B–C, A–B, A–E, B–E, B–F, C–F, C–D, D–H, H–J, I–J, E–I, E–F, F–G puis G–H : les $15$ liaisons, chacune une fois.

Rédaction attendue. B n’est pas une extrémité du parcours, qui va de G à H. Chaque fois que le parcours traverse B, il y arrive par une liaison et en repart par une autre : il utilise deux des liaisons de B. Les $4$ liaisons de B sont toutes empruntées, une fois chacune : le parcours traverse B exactement ${\displaystyle \frac{4}{2}}=2$ fois. Un parcours eulérien peut donc repasser par un même capteur ; c’est chaque liaison qu’il n’emprunte qu’une fois.

Pour un parcours fermé, tous les degrés doivent être pairs : seule une liaison G–H doublée corrige à la fois G et H, et elle existe. Le graphe obtenu est connexe et tous ses degrés sont pairs ; d’après le théorème d’Euler, il admet un cycle eulérien. Le technicien effectue $15+1=16$ tests.

def degres(aretes):
    d = {}
    for (u, v) in aretes:
        d[u] = d.get(u, 0) + 1
        d[v] = d.get(v, 0) + 1
    return d

def nb_impairs(aretes):
    d = degres(aretes)
    k = 0
    for s in d:
        if d[s] % 2 == 1:
            k = k + 1
    return k

La fonction degres parcourt les arêtes et ajoute $1$ au degré de chacune des deux extrémités ; nb_impairs compte ensuite les sommets dont le degré a pour reste $1$ dans la division par $2$. Dans $K_6$, chacun des $6$ sommets est de degré $5$, impair : la fonction renvoie $6$. Pour le réseau de capteurs, elle renvoie $2$. Attention : elle ne teste que la parité ; la connexité, autre hypothèse du théorème d’Euler, se vérifie à part.