DM 2A : Ensembles de Sidon

Une conjecture à 500 dollars

Un ensemble de Sidon est un ensemble d'entiers strictement positifs {s₁,...,s_r} tels que les sommes s_i+s_j pour i <= j soient deux à deux distinctes. Par exemple,

    { 1, 2, 5, 10, 12 },
    { 1, 3, 8, 9, 12 },
    { 1, 3, 8, 11, 12 },
    { 1, 4, 5, 10, 12}

sont des ensembles de Sidon (ce sont en fait tous les ensembles de Sidon de 7 nombres entre 1 et 12), alors que

    { 1, 2, 3 }

n'est pas un ensemble de Sidon, car 2+2=1+3. Une famille d'exemples plus conséquents est donnée par la suite infinie de Mian-Chowla : 1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312, 1395, 1523, 1572, 1821, 1896, 2029, 2254, 2379, 2510, 2780, 2925, 3155, 3354, 3591, 3797, 3998, 4297, 4433, 4779, 4851, ..., dont toutes les troncatures fournissent des ensembles de Sidon.

Une question difficile de théorie des nombres est de maximiser le nombre d'éléments d'un ensemble de Sidon dont le plus grand élément ne dépasse pas un entier donné b. Soit m_b la cardinalité maximale à b fixé ; on sait que m satisfait l'encadrement suivant, pour tout e > 0 :

b^1/2(1-e) < m_b <= b^1/2+b^1/4+1.

Une conjecture est l'approximation plus fine m_b=b^1/2+O(1). Le célèbre théoricien des nombres Erdös a offert 500 dollars à qui fournirait une réponse à la question. Malheureusement, depuis sa mort en 1996, nul ne sait si les héritiers honoreront l'engagement pris par Erdös :-(.

Une question duale est de minimiser l'entier maximal d'un ensemble de Sidon à m éléments. Les troncatures de la suite de Mian-Chowla donnée plus haut ne fournissent pas de bons ensembles de Sidon pour ce critère. Par exemple, tronquée à ses 14 premiers termes, l'entier maximal est 182, beaucoup moins bon que l'optimum donné par les ensembles

    { 1, 5, 7, 21, 36, 53, 60, 78, 79, 87, 90, 100, 123, 128 },
    { 1, 6, 29, 39, 42, 50, 51, 69, 76, 93, 108, 122, 124, 128 }.

Programme à réaliser

En retranchant le même entier à chaque élément d'un ensemble de Sidon, on obtient de nouveau un ensemble de Sidon. On se concentre donc ici aux ensembles de Sidon dont le petit entier est 1. L'objectif du problème est d'écrire un programme qui énumère tous les ensembles de Sidon de taille m et dont les éléments sont entre 1 et b.

Écrire une procédure (récursive) qui, lorsque les entiers s₁,...,s_k forment un ensemble de Sidon, détermine tous les ensembles de Sidon qui prolongent cet ensemble. Des valeurs étant déterminées jusqu'à s_k, on testera donc successivement toutes les valeurs possibles pour s_k+1 entre s_k+1 et b : lorsque la valeur testée fait retomber sur une somme déjà présente, elle n'est pas permise et doit être rejetée. À chaque rejet, on fera attention à bien rejeter les sommes qui viennent d'être introduites, et seulement celles-là.

Pour trouver tous les ensembles de Sidon de taille m, on partira du tableau vide dont on se servira en fait comme d'une pile et on fera s₀ = 1. Ensuite, on choisira d'abord s₁, puis s₂, etc, en revenant sur ses choix lorsqu'on détectera des incompatibilités. La recursion se termine lorsque le tableau s est rempli ; on affiche alors l'ensemble de Sidon obtenu avant de repartir en arrière.

Ainsi, pour trouver les ensembles de Sidon à 3 éléments de valeur au plus 4, on a le calcul suivant :

    1
    1, 2
    1, 2, 3 -> rejet
    1, 2, 4 -> afficher
    1, 3
    1, 3, 4 -> rejet
    1, 4    -> fini

Si la puissance des machines le permet, on pourra retrouver les quatre ensembles de Sidon de taille 11 et bornés par 73, qui sont

    { 1, 2, 5, 14, 29, 34, 48, 55, 65, 71, 73 },
    { 1, 2, 10, 20, 25, 32, 53, 57, 59, 70, 73 }, 
    { 1, 3, 9, 19, 26, 40, 45, 60, 69, 72, 73 }, 
    { 1, 4, 15, 17, 21, 42, 49, 54, 64, 72, 73 },

et montrer qu'il y en a aucun de taille 11 et borné par 72.

DM 2B : Théorème des quatre couleurs et polynômes chromatiques

Un problème de géographie : les quatres couleurs

Un graphe (non orienté) est dit planaire s'il peut être dessiné dans le plan sans que deux de ses arêtes ne se coupent. Un célèbre théorème affirme que tout graphe planaire peut être colorié à l'aide de quatre couleurs seulement. En d'autres termes, on peut colorier ses sommets à l'aide de quatre couleurs sans que deux sommets de même couleur ne soient jamais deux reliés par une arête. Une version duale de ce théorème est que sur une carte de géographie, il est toujours possible de colorier les pays de sorte que deux pays voisins soient de couleurs différentes. (Démonstration : les capitales des pays sont les sommets d'un graphe dont les arêtes joignent les capitales de pays qui ont une frontière commune.)

On se propose de vérifier ce théorème, et mieux, de réaliser l'affichage de tous les coloriages d'un graphe à l'aide de 1, 2, 3, ..., k couleurs.

Saisie du graphe

On se propose de réaliser la saisie d'un graphe à la souris, en deux temps. Le graphe sera sauvegardé par un tableau de listes de sommets adjacents.

Tout d'abord, on entrera les sommets par des clicks successifs. À chaque click, les coordonnées du nouveau sommet seront enregistrées par le programme, et le sommet sera matérialisé par un petit cercle autour du point cliqué.

Ensuite, l'utilisateur devra cliquer dans une zone réservée de l'écran (par exemple, un petit carré en haut à gauche) pour indiquer qu'il passe à la saisie des arêtes.

Deux clicks seront ensuite nécessaires pour indiquer chacune des arêtes. Les numéros des sommets indiqués seront retenus. Les arêtes seront visualisées comme des segments reliant les centres des deux sommets. Un graphe planaire pourra donc être affiché avec des croisements d'arêtes et la question n'est pas de faire un affichage sans croisements.

Pour terminer la saisie, l'utilisateur devra cliquer dans une deuxième zone réservée de l'écran (par exemple, un petit carré en haut à droite).

Si on se sent suffisament à l'aise avec le graphisme en Java, on pourra remplacer les « zones réservées » par des boutons bien plus esthétiques. On pourra aussi (même sans boutons), permettre plus d'interactivité en permettant de basculer alternativement du mode sommet au mode arêtes ; il faudra alors une troisième zone réservées (ou un troisième bouton) pour indiquer la fin de la saisie.

Énumération et dénombrement des k-colorations d'un graphe

Un graphe étant saisi, on va maintenant écrire une procédure récursive qui détermine et affiche toutes les coloriages du graphe à l'aide d'au plus k couleurs. Pour des raisons évidentes, on ne intéressera essentiellement qu'au cas de graphes connexes.

L'idée est de suivre un parcours en profondeur d'abord. À chaque sommet rencontré pour la première fois, on essaiera successivement toutes les couleurs (de 1 à k) en vérifiant que cette couleur n'est pas déjà utilisée par un voisin. (Une optimisation simple est de commencer par déterminer la liste des couleurs déjà utilisées par les voisins avant d'itérer sur les couleurs, au lieu de tester chaque voisin à chaque essai d'une nouvelle couleur.) Une fois cette coloration déterminée, on repart en arrière pour aller déterminer les autres colorations.

Pour déterminer que tout le graphe (supposé connexe) est colorié, on maintiendra à jour une variable donnant le nombre de sommets coloriés. Lorsque ce nombre est atteint, on a un k-coloriage du graphe. On demande alors de colorier chaque disque représentant un sommet à l'écran dans la couleur du sommet, puis de marquer une pause pour que l'utilisateur visualise la coloration.

À la fin du processus, imprimer le nombre de colorations obtenues.

Polynôme chromatique

Si on s'intéresse uniquement au dénombrement des k-colorations d'un graphe, et non pas à toute leur énumération, un algorithme récursif permet de calculer le polynôme chromatique p(G;X) d'un graphe G, qui est tel que pour un entier strictement positif k, p(G;k) donne le nombre de k-colorations de G. Pour donner la récurrence, on a besoin de définir deux opérations particulières sur les graphes : étant donné une arête a,

le graphe G/a résultant de la contraction d'une arête a dans un graphe G est obtenu en suppression l'arête et en identifiant les deux sommets incidents ;
la suppression d'une arête a dans un graphe G résulte en un graphe noté G\a ayant même ensemble de sommets et une arête de moins.

Pour tout graphe G possédant au moins une arête a, on a la récurrence

p(G;X) = p(G\a;X) - p(G/a;X).

De plus, le polynôme chromatique d'un graphe (possiblement non connexe) est défini comme le produit des polynômes chromatiques de ses composantes connexes. Il est clair que par cette récurrence, même en partant d'un graphe connexe sans arête multiple ni boucle (une arête d'un sommet à lui-même), l'un des graphes produits peut contenir plusieurs composantes connexes, des arêtes multiples ou des boucles.

L'algorithme consiste à suivre la récurrence tant que G est connexe et que a n'est ni une boucle, ni un pont (une arête qui, une fois retirée, sépare le graphe en deux composantes connexes ; on dit aussi isthme ou co-boucle). Dans le cas d'une boucle, aucune coloration n'est possible et le possible chromatique est nul. Dans le cas d'un pont, la récurrence est encore valable, mais il est préférable de remarquer que si le pont a sépare le graphe G en deux nouveaux graphes connexes G₁ et G₂, le polynôme chromatique de G est

p(G;X) = p(G₁;X) p(G₂;X) (X-1)/X.

La récurrence s'arrête donc sur les graphes consistant en un unique sommet sans boucle, qui ont X pour polynôme chromatique.

Un exemple de calcul par cette récurrence est donné sur cette page web (seule les premières étapes sont développées). (Merci à l'auteur !).

Les polynômes calculés seront sauvegardés sous forme non développée comme arbres de syntaxe abstraite (ASA) de l'une des natures suivantes : *, -, X et Y, ce dernier représentant (X-1)/X. De plus, une valeur particulière codera le cas du polynôme nul, permettant ainsi des simplifications arithmétiques à la volée.

Les méthodes à écrire sont les suivantes :

suppression d'une arête : cette suppression sera faite en place sur le graphe.
contraction d'une arête : la contraction, par contre, sera faite par recopie du graphe, qui nécessite un parcours en profondeur d'abord.
détection d'un pont : pour une paire (G,a) donnée, on veut savoir si l'arête a est un pont. Pour cela, on la retire du graphe, puis on détermine par un parcours en profondeur d'abord si une des extrémités est accessibles à partir de l'autre, puis on réinsère l'arête a dans le graphe.
la récurrence elle-même, renvoyant pour un graphe G son polynôme chromatique. (Pour simplifier, on pourra dans un premier temps calculer non pas le polynôme chromatique, mais son évaluation en un entier donné et ainsi s'éviter d'avoir à gérer des arbres abstraits.) L'arête servant de pivot pour la récurrence sera prise quelconque parmi les arêtes du graphe (à moins qu'on veuille essayer des optimisations).
l'évaluation du polynôme en un entier k.

Valider le programme en retrouvant les nombres de colorations obtenus par l'exploration exhaustive.

En faisant développer par un système de calcul formel les polynômes obtenus sur de petits exemples, on pourra observer une alternance des signes des polynômes chromatiques. Il existe une généralisation bivariée du polynôme chromatique, le polynôme de Tutte, qui permet de calculer plusieurs paramètres associés aux graphes (nombre d'arbres couvrants, nombre de forêts, nombre de sous-graphes connexes, nombre d'orientations acycliques, etc).