Graphes

Je publie ici des graphes sur des thèmes divers.

Ces graphes sont générés automatiquement via un programme Python (avec les extensions NetWorkX et GraphViz) qui traite un dictionnaire d'adjacence créé manuellement ou automatiquement.

N'hésitez pas à suggérer des idées en commentaires !

Graphe d'arbre de nombres

Un arbre de nombres associé à l'entier naturel N est un graphe orienté dont les sommets sont tous les entiers compris entre 1 et N, dont on précise les décompositions en facteurs premiers (sauf pour 1). Il se construit de la manière suivante :

• On établit la liste L de tous les nombres premiers entre 1 et N.

• On relie le sommet "1" à tous ces nombres en précisant leur décomposition.

• Pour un sommet n, on regarde le nombre premier le plus petit de sa décomposition puis on restreint L aux nombres premiers supérieurs ou égaux, alors notée L'. On regarde ensuite, pour chaque nombre p dans L', si n x p est inférieur ou égal à N. Si c'est le cas alors on relie le sommet n au sommet n x p.

Graphes d'arbres des diviseurs

Pour déterminer l'ensemble des diviseurs d'un nombre entier, on peut construire un arbre des diviseurs.

Quelques arbres des diviseurs ont été générés pour des nombres hautement composés, c'est-à-dire ayant beaucoup de diviseurs.

Graphe de chimie organique

En chimie organique les molécules contiennent des groupes fonctionnels (alcool, acide carboxylique, alcène, etc.) qui peuvent se transformer en d'autres groupes fonctionnels par réactions chimiques.

Graphe des décroissances radioactives

En physique nucléaire le phénomène de décroissance radioactive permet à un noyau atomique instable de gagner en stabilité. Il existe différents modes de décroissances, chacune faisant intervenir des particules issues du modèle standard :

• rayonnement : transition d'un état excité vers un état moins excité par émission d'un photon

• désintégration ß- : transformation d'un neutron en proton par émission d'un électron et d'un antineutrino électronique (antiparticule du neutrino électronique)

• désintégration ß+ : transformation d'un proton en neutron par émission d'un positron (antiparticule de l'électron) et d'un neutrino électronique

• capture électronique ε : transformation d'un proton en neutron par capture d'un électron et émission d'un neutrino électronique

• désintégration n : émission d'un neutron

• désintégration p : émission d'un proton

• désintégration α : émission d'un noyau d'hélium 4 (2 protons et 2 neutrons)

Le graphe représente pour chaque noyau instable son mode de décroissance majoritaire (hors rayonnement), en modélisant les noyaux par des sommets et les modes de décroissances par les arêtes entre les sommet des noyaux pères et les sommets des noyaux fils. Les décroissances se succèdent jusqu'à arriver à un noyau stable. Les enchaînements de décroissances les plus typiques sont les chaînes de désintégration de l'uranium 238 (famille 4n+2), de l'uranium 235 (famille 4n+3) et du thorium 232 (famille 4n).

Graphes de jeu de taquin

Dans le jeu de taquin, on déplace des petits carreaux numérotés pour passer d'une configuration à une autre. Ces configurations peuvent être représentées dans un graphe et reliées entre elles s'il ne suffit que d'une action (un déplacement de carreau) pour passer de l'une à l'autre.

On peut relier un certain nombre de configurations à la configuration à atteindre, mais ça ne concerne pas toutes les configurations possibles. Par exemple pour un taquin de taille 2x2 la configuration à atteindre est "12/3 " ("1" et "2" à la première ligne puis "3" et "vide" à la seconde); on peut y arriver à partir de "12/ 3" mais pas à partir de "13/2 ".

Dans les graphes la configuration à atteindre est tout en haut et il faut donc "remonter" le graphe pour l'atteindre à partir d'une configuration à atteindre.

Graphes de liens

On prend N sommets et on les place en cercle, puis on les relie tous entre eux.

Graphe des pays reliés par des sons

Un pays A peut être relié à un pays B si et seulement si les derniers sons de A correspondent aux premiers sons de B. Quelques exemples :

• "Afghanistan" peut être relié à "Tanzanie" car les deux derniers sons de "Afghanistan" correspondent aux deux premiers sons de "Tanzanie". Ces sons sont "/t/" puis "/ɑ̃/".

• "Algérie" ne peut pas être relié à "Allemagne" car les derniers sons de "Algérie" ne correspondent pas aux premiers sons de "Allemagne".

• "Autriche" ne peut pas être relié à "Chine" car un seul son ("/ʃ/") est commun aux deux pays.

Dans le graphe, les pays sont représentés par des nœuds. Les relations sont modélisées par des flèches partant du pays dont les derniers sons sont concernés et arrivant vers le pays dont les premiers sons sont concernés. Par exemple si le pays A peut être relié au pays B et qu'on décide de relier les deux nœuds associés, alors une flèche part de A et arrive vers B.

En raison du grand nombre de relations possibles, on se limite au maximum de sons communs. Par exemple si un pays A peut être relié aux pays B et C via trois sons et aux pays D, E et F via deux sons, on ne relie le pays A qu'aux pays B et C.

Graphe des pays voisins

Ce graphe relie simplement les pays qui partagent une frontière terrestre.

Seuls les pays ayant au moins une frontière terrestre apparaissent dans le graphe. Haïti et la République Dominicaine ont été exclus afin que le graphe soit connexe.

Graphes de pyramides de puissances

On peut organiser les nombres entiers strictement positifs en pyramides selon des puissances d'un nombre N. Ces pyramides se construisent de haut en bas de la manière suivante :

• On place le nombre 1 tout en haut.

• Dans l'étage inférieur on place les nombres entre 2 et N de gauche à droite. Tous ces nombres constituent la base du nombre 1.

• Pour chaque étage inférieur on place les nombres entre N^k et N^(k+1), où k est un nombre entier supérieur ou égal à 2 qui augmente à chaque fois qu'on descend d'un étage.

• Chaque nombre de la pyramide différent de 1 possède une base de N nombres situés dans l'étage inférieur. La base du premier nombre d'un étage est constituée des N premiers nombres de l'étage inférieur, la base du deuxième nombre de cet étage est constituée des N nombres suivants, et ainsi de suite.

Graphes de quadrillages vecteurs

Dans un quadrillage on peut choisir de relier certains points entre eux par certains segments ayant tous la même longueur L.

Le quadrillage est un carré de côté C, c'est-à-dire qu'il y a C points par ligne et C points par colonne. Sur une même ligne ou colonne, les points voisins sont espacés d'une longueur 1.

On choisit L de façon à ce que, pour un point situé pas trop près du bord du quadrillage et L suffisamment petit devant C, ce point ait 8 voisins. L ne peut notamment pas valoir 1 ou sqrt(2) (longueur entre deux points voisins dans une diagonale du quadrillage).

Plutôt que de garder L pour caractériser la longueur des segments, on prend plutôt les coordonnées du vecteur d'un des segments. Par exemple pour L=sqrt(5), les 8 vecteurs sont :

• (2,1)
• (1,2)
• (-1,2)
• (-2,1)
• (-2,-1)
• (-1,-2)
• (1,-2)
• (2,-1)

Graphe de Syracuse

La suite de Syracuse permet de relier des nombres entiers entre eux.

Dans le graphe les nombres sont représentés par des nœuds. Un nombre A est relié à un nombre B par une flèche s'ils sont successifs conformément à la suite de Syracuse, c'est-à-dire si B=A/2 ou B=3A+1.

Le graphe se limite aux nombres strictement inférieurs à 1000. Cela signifie que si la suite de Syracuse associée à un nombre contient au moins un nombre supérieur ou égal à 1000, alors ce nombre n'apparaît pas dans le graphe.

Graphes de tables modulaires

Les tables modulaires sont une manière de représenter les tables de multiplication.