Wolfram Language

Coloration fractionnelle d'un graphe

De nombreux problèmes modernes englobant des domaines aussi divers que le classement des pages Internet, la conception de circuits électroniques, l'analyse des réseaux sociaux et la gestion de la distribution peuvent être formulés et résolus en utilisant les outils de la théorie des graphes. En plus d'une large gamme de fonctions pour créer, calculer et utiliser des graphes, Wolfram Language inclut un grand nombre de collections de graphes.

Le domaine d'entités "Graph" tente de cataloguer les graphes non dirigés intéressants, avec leurs propriétés connues ou calculables. Les entités "Graph" fournissent une collection croissante de plus de 6 000 graphes simples et 500 propriétés pré-calculées.

La structure d'entités "Graph" inclut également de "superbes" intégrations pré-calculées pour la plupart des graphes.

Remarquez que les objets renvoyés par la propriété "Graph" ne sont pas simplement des graphiques, mais bien des objets Graph réels de Wolfram Language.

Chaque entité de graphe contient une liste détaillée des classes mathématiques auxquelles elle appartient.

Il existe également deux fonctions qui relient le monde des entités graphiques aux objets graphiques de niveau supérieur. ToEntity convertit un graphe simple inconnu en une entité (s'il en existe une).

L'inverse est fourni par FromEntity (ce qui équivaut à utiliser la propriété "Graph").

Pour se faire une idée de l'étendue des données disponibles dans le domaine d'entités "Graph" il suffit de considérer le nombre chromatique fractionnaire d'un graphe. Le nombre chromatique fractionnaire généralise le nombre chromatique habituel dans le cas des colorations dans lesquelles plusieurs couleurs sont permises à chaque sommet, avec une fraction de poids spécifiée, de sorte que les sommets adjacents ne contiennent pas deux couleurs identiques.

Par exemple, alors que le nombre chromatique du graphe dodécaédrique est de 3 (un minimum de trois couleurs est nécessaire pour colorer les sommets de sorte qu'aucun des deux sommets adjacents ne partage une couleur). L'utilisation de la coloration fractionnelle donne un nombre chromatique fractionnaire de 5/2 (dont une instanciation qui, voir plus loin, consiste en cinq couleurs attribuées à chaque nœud avec un poids de 1/2).

Le domaine des entités graphiques contient à la fois les nombres chromatiques habituels et les nombres chromatiques fractionnaires pour de nombreux graphes, ainsi que les colorations concrètes qui atteignent ces valeurs minimales. Par exemple, le graphe dodécaédrique possède le nombre chromatique 3.

Une coloration atteignant cette valeur peut être récupérée comme suit.

Il est très simple d'utiliser ces données d'incorporation et de coloration avec la fonctionnalité graphique intégrée pour créer une visualisation.

Comme on peut le constater visuellement (ou par programmation), deux sommets adjacents ne partagent pas la même couleur dans le diagramme précédent.

Le cas de la coloration fractionnée est légèrement plus compliqué, mais assouplit essentiellement la contrainte que chaque sommet a une couleur unique en permettant aux sommets de contenir des parties fractionnaires de couleurs différentes. Le nombre chromatique fractionnaire est ensuite défini en additionnant les parties fractionnaires sur tous les sommets. Ceci permet souvent une coloration en utilisant "moins" (mais pas nécessairement un nombre entier) de couleurs. Par exemple, le nombre chromatique fractionnaire du graphe dodécaédrique est , ce qui est inférieur à son nombre chromatique de 3.

Pour obtenir la coloration fractionnaire, utilisez la propriété "MinimumWeightFractionalColoring" pour obtenir une liste des sommets et des poids pour différentes couleurs.

Par exemple, la sortie précédente indique qu'une coloration fractionnelle minimale est possible en utilisant cinq couleurs, la première étant appliquée aux sommets 3, 5, 9, 12, 13, 15, 16 et 20 avec un poids de 1/2, etc. Puisque chaque couleur est appliquée avec le même poids de 1/2, le nombre chromatique fractionnaire global est .

Puisque les fractions de chaque coloration sont égales à 1/2 dans ce cas, il est facile de créer une visualisation en trouvant d'abord les deux couleurs contribuant à chaque sommet.

Par exemple, la liste précédente indique que le premier sommet utilise les couleurs 4 et 5, le second les couleurs 4 et 5, le troisième les couleurs 1 et 5, etc. Convertissez maintenant les indices numériques de couleur en couleurs réelles.

L'étape finale de la visualisation consiste à définir une fonction de forme de sommets composée de deux demi-disques de couleur appropriée.

Une fois toutes les pièces en place, vous pouvez maintenant afficher une coloration fractionnelle minimale pour le graphe dodécaédrique.

Comme prévu, les sommets adjacents ne partagent aucune couleur commune dans cette coloration fractionnée.

Les nombres chromatiques fractionnels ne sont pas distribués uniformément, mais ont tendance à se regrouper autour de certaines valeurs. La réalisation d'un histogramme à partir des données pré-calculées de tous les graphes du domaine d'entités "Graph" montre un regroupement autour des nombres entiers, bien que certains autres pics importants soient aussi visibles.

Vous pouvez utiliser BubbleChart pour représenter graphiquement les nombres de graphes ayant chacun un nombre chromatique fractionnaire (avec numérateur et dénominateur sur les axes et , respectivement) et explorer plus en détail la distribution.

Exemples connexes

de en es ja ko pt-br zh