Aller au contenu

Recherche:Théorie des matrices logiques/Application: coloriage d'un graphe simple

Une page de Wikiversité, la communauté pédagogique libre.
Début de la boite de navigation du chapitre
Application: coloriage d'un graphe simple
Icône de la faculté
Chapitre no 13
Recherche : Théorie des matrices logiques
Chap. préc. :Rupture momentanée de la forme canonique
Chap. suiv. :Application: calcul de la clique maximum d'un graphe
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Théorie des matrices logiques : Application: coloriage d'un graphe simple
Théorie des matrices logiques/Application: coloriage d'un graphe simple
 », n'a pu être restituée correctement ci-dessus.

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.