Recherche:Théorie des matrices logiques/Application: coloriage d'un graphe simple
Matrice canonique permettant le coloriage des sommets du graphe G au moyen de trois couleurs, de façon à ce que deux sommets adjacents (reliés par une arête) ne reçoivent jamais la même couleur:
- Cette matrice reproduit, mutatis mutandis,
- la matrice d'adjacence de G. Les cellules
- actives correspondent aux 1 de la matrice
- d'adjacence, qui représentent des arêtes.
Après fermeture des transfuges, de nouveaux 0 sont apparus, révélant la présence d'arêtes latentes dans G.
Et une relation d'identité relie maintenant explicitement les deuxième et troisième sommets, qui ont toujours la même couleur.
Ce qui peut être vérifié dans les douze 3-coloriages de G:
Les cellules de la forme
reproduisent elles aussi la matrice d'adjacence d'un graphe.
Il s'agit du graphe complet à 3 sommets, sur lequel on cherche à appliquer G compte tenu du fait que deux sommets adjacents ne peuvent être appliqués sur un même sommet du graphe complet.
Sens de cette démarche:
- dans un graphe complet à n sommets chaque sommet est adjacent à tous les autres
- il faut donc exactement n couleurs pour colorier ce graphe
- en ramenant G à un graphe complet, on a la certitude que n couleurs suffiront à colorier G.
Tous les calculs relatifs au jeu de Sudoku peuvent être effectués au moyen d'une matrice logique analogue à celle de l'exemple: graphe à 81 sommets et 810 arêtes, 9 couleurs.
D'autres matrices canoniques reprennent le même schéma de principe (application d'un graphe sur un autre).
Exemples : calcul du code Gray, problème de la clique maximum.
