Résolution Polynomial : Tricoloriage

(Avec la Résolution en losange) (Sans la Résolution en Losange)

P=NP : Variante du Tricoloriage

À propos
Cet ouvrage nécessite avoir lu le référentiel de SCI Vol.1 pour le comprendre.

Ce manuscrit résout de nombreux problèmes irrésolu, tel le 3e problème de Smale (P=NP). Un logiciel accompagne ce tutoriel ( Tricoloriage.gmk ). Cette open-source s'ouvre avec Game Maker 8.0 pro, et le «gml 8» est le langage utilisé.

NOTE : Suite à la réception d'une critique depuis le mouvement M.H.C., je tiens à vous rassurer : la résolution du problème présent, malgré les apparences, n'est pas un coloriage gourmand.

Problème : Le Tricoloriage.
Pour un nombre N de cercle à colorier, relié au hasard avec plus ou moins d'arc de cercle, comment résoudre par résolution polynomiale le problème de sorte d'obtenir le minimum de couleurs que possible sans qu'aucune couleur ne soit reliée?
Source du problème : https://fr.wikipedia.org/wiki/Coloration_de_graphe

Réponse Théorique
Imaginons un paterne au hasard comme l'image ci-dessous:

Pour trouver le nombre de couleurs minimum, il faut y aller un numéro à la fois, commençons par le #1, et donnons lui une couleur avec l'ID la plus petite.

ID des couleurs utilisées :
1 : Vert
2 : Orange
3 : Rouge
4 : Mauve
5 : Bleu

Ensuite, toujours suivant le cercle collé sur le dernier cercle colorié, ayant le plus de couleurs différents autour de lui tout en priorisant l'Identifiant le plus petit non-colorié, nous ajoutons une couleur.

Le #4 n'a plus de cercle non-colorier disponible, nous reculons donc au dernier cercle, puis à l'autre d'avant et ainsi de suite jusqu'à trouver un cercle collé sur une case libre: 4, puis 6, et enfin 2:

Nous avons donc un tricoloriage de 3 couleurs pour ce paterne. Passons maintenant à la version mathématique pour comprendre comment appliquer cette logique dans une résolution polynomiale; dit grossièrement, vérifier et calculer en même temps sans jamais regarder deux fois à la même place.
Voici un deuxième exemple auquel nous appliquons les mêmes règles:

Réponse Mathématique

   SO()==
/* Calcul du Pole:
1 Variable de Limitation OL : 1-1=0
   OM(0)
   Le maximum de dimension d'itération des Variables Primitives est 2:
   OM(0+2)
Il n'y a qu'une seule Variable P : 1-1=0
      OM(2+0)
   Il n'y a qu'une seule Variable R : 1-1=0
      OM(2+0)
La valeur total des variables isolée de l'OP est de 1:
      OM(2+1)
*/
// Initialisation des variables secondaires de mémoire i, j, k.
         OM( 3 ) ;
   // L = Limite de Cercle et de possibilité de Couleur.
        OL( 100 ) ;
   // Les variables P[L,L], R[L,L] et M.L sont Créées.
   OP( L,L02 ¦ (L+1),L02 ¦ L01 ) ;
   PN() ;
   PN()==
// Choisi un nombre aléatoire de cercle.
   L = ir(2 , 2000) ;
   PR( L , i )
      {   PR( L , j )
{ RA( i = j )
{ // Variable servant à compter le nombre d'arc de cercle par cercle.
   P[ i , i ] = 0 ;
   } !
   { // Si le hasard tombe sur 1 :
   RA( ( ir( 1 , L ) ) = 1 )
{   // Crée un arc de cercle.
   P[ i , j ] = 1
   } !
   { P[ i , j ] = 0 ;
   }
}
      // Réinitialise la Variable Primitive de Résolution.
   R[ i , j ] = 0
   }
// Réinitialise les couleurs.
   M.i = 0
   // Réinitialise le nombre de couleurs qui touche chaque cercle.
   R[ ( L + 1 ) , i ] = 0 ;
   }
   SLP() ;
SLP()==
// Pour chaque cercle :
   PR( L , i )
   { // S'il n'y a pas de couleur sélectionnée :
         RA( M.i = 0 )
{ // Applique une couleur.
         AF( i )
      }
} ;
SLM.1()==
// Pour chaque possibilité d'arc de cercle,
   PR( L , j )
{ // Sauf pour lui-même,
   RA( a1 != j )
// S'il y a un arc de cercle,
   RA( P[ a1 , j ] = 1 | P[ j , a1 ] = 1 )
// Si le cercle n'a pas de couleur :
   &( M.j = 0 )
{            // Mémorise le nombre de cercle relié
   P[ a1 , a1 ] ++ ;
   // S'il n'y a pas une autre couleur identique collée sur le cercle j :
   RA( R[ j , M.a1 ] = 0 )
      { // Déclare qu'il y a une couleur de plus autour du cercle
         R[ j , ( L + 1 ) ] += 1
         // Interdit la couleur
   R[ j , M.a1 ] = 1 ;
   }
// Mémorise la suite à calculer.
   R[ a1 , P[ a1 , a1 ] ] = j ;
   // S'il y a plus d'un cercle collé
   RA( P[ a1 , a1 ] > 1 )
/* Si le dernier cercle a plus de couleur différente

autour de lui que l'avant dernier cercle ajouté:

      */
         RA( R[ j , ( L + 1 ) ] > R[ R[ a1 , ( P[ a1 , a1 ] - 1 ) ] , ( L + 1 ) ] )
     // Mesure l'ordre de calcul à établir.
   SLM.2( a1 ) ;
   }
}
      /* Cette Règle d'Application Solitaire peut également
      être placée directement AF(i) du SLP().
*/
   // Si le cercle est relié à au moins un autre cercle sans couleur:
   RA( P[ a1 , a1 ] > 0 )
{ // Calcule les cercles reliés.
         SLC.3( a1 , P[ a1 , a1 ] ) ;
   }
SLM.2()== // Suite Logique #2 imbriquée à SLM.1(), et affiché séparément.
         // Selon le nombre total d'arc de cercle en cour de mesure moins 1,
   PR( ( P[ a1 , a1 ] - 1 ) , k )
{ // S'il n'y a pas encore de couleur choisi,
   RA( M.R[ a1 , ( P[ a1 , a1 ] - k + 1 ) ] = 0 )
// Si le cercle (k+1) a plus de couleurs différentes que le cercle (k) :
   RA( R[ R[ a1 , ( P[ a1 , a1 ] - k + 1 ) ] , ( L + 1 ) ] > R[ R[ a1 , ( P[ a1 , a1 ] - k ) ] , ( L + 1 ) ] )
{ // Échange leur place de priorité.
   R[ a1 , ( P[ a1 , a1 ] - k ) ] = R[ a1 , ( P[ a1 , a1 ] - k + 1 ) ]
R[ a1 , ( P[ a1 , a1 ] - k + 1 ) ] = R[ a1 , ( P[ a1 , a1 ] - k ) ]
// Déclare que le déplacement dans la liste est en cour.
   j = ¬j ;
   } !
   {   // Sinon, si le déplacement était en cour
   RA( l = 1 )
{    // j reprend sa valeur original pour SLM.1() .

j = ¬j ;

// Termine la mesure d'échange.
   break ;
   }
}
}
SLC.3()==
// Suivant le nombre de cercle relié
   PR( a2 , P[ a1 , a1 ] )
  // S'il n'y a pas de couleur choisi :
   RA( M.R[ a1 , P[ a1 , a1 ] ] = 0 )
{ AF( R[ a1 , P[ a1 , a1 ] ] ) ;
   }
AF()==
// Suivant la limite possible de couleur,
   PR( L , j )
         // Si la couleur est libre:
         RA( R[ a1 , j ] = 0 )
      { // Assigne la couleur libre.
         M.a1 = j ;
   // Mesure les possibilités par rapport à la couleur prise.
         SLM.1( a1 )
break ;
   }