Résolution Polynomial : Coloriage de Graphe

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

P=NP : Variante du Colorage de Graphe

À 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), ou encore la coloration de graphe. 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 : Coloration de Graphe.
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
Comme pour le problème des 400 étudiants, la solution est « Mesure² - Calcul ». La mesure corespond au nombre d'arc de cercle qu'un cercle possède (excluant les arcs de cercle tombant sur un cercle déjà coloré), et le calcul corespond aux cercles relié aux arc de cercle (les cercles voisins), excluent les cercles déjà coloriés. Dans le calcul, nous devons soustraire la valeur des identifiants des couleurs des cercles voisins coloriés.

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, nous regardons tout les cercles voisins aux cercle colorés, nous prenons leur mesures et leur calcul pour obtenir une valeur. Puis nous choisissons la valeur la plus grande et attribuons une couleur à ce cercle.
   Dans cet exemple, les cercles #3, #7 et #8 sont voisins d'un cercle coloré. Nous prennons leur mesure et leur calcul :
      Cercle #3 :
            Mesure : 3² = 9
         Calcul : 4+2+3 = 9
            Valeur des couleurs : 1 = 1
         Valeur totale : 9-9+1 = 1
      Cercle #7 :
            Mesure : 4² = 16
         Calcul : 3+3+2+3 = 11
            Valeur des couleurs : 1 = 1
         Valeur totale : 16-11+1 = 6
      Cercle #8 :
            Mesure : 2² = 4
         Calcul : 3+2 = 5
            Valeur des couleurs : 1 = 1
         Valeur totale : 4-5+1 = 0
Le cercle #7 à la valeur la plus grande, donc nous colorons ce cercle.

Maintenant, nous avons les Cercles #2, #3, #4, #6, et #8 qui sont voisins de cercles colorés. Nous effectuons encore une fois le même calcul :
   Cercle #2 :
            Mesure : 2² = 4
         Calcul : 2+3 = 5
            Valeur des couleurs : 2 = 2
         Valeur totale : 4-5+2 = 1
   Cercle #3 :
            Mesure : 2² = 4
         Calcul : 2+3 = 5
            Valeur des couleurs : 1+2 = 3
         Valeur totale : 4-5+3 = 2
      Cercle #4 :
            Mesure : 1² = 1
         Calcul : 2 = 2
            Valeur des couleurs : 2 = 2
         Valeur totale : 1-2+2 = 1
      Cercle #6 :
            Mesure : 2² = 4
         Calcul : 2+1 = 3
            Valeur des couleurs : 2 = 2
         Valeur totale : 4-3+2 = 3
      Cercle #8 :
            Mesure : 2² = 4
            Calcul : 2+2 = 4
            Valeur des couleurs : 1 = 1
         Valeur totale : 4-4+1 = 1

Le cercle #6 ayant la valeur la plus grande, est coloré :

   Les cercles #2, #3, #4, et #8 sont voisins de cercle coloré :
   Cercle #2 :
            Mesure : 1² = 1
      Calcul : 3 = 3
           Valeur des couleurs : 1+2 = 3
      Valeur totale : 1-3+3 = 1
   Cercle #3 :
            Mesure : 2² = 4
      Calcul : 1+3 = 4
            Valeur des couleurs : 1+2 = 3
      Valeur totale : 4-4+3 = 3
   Cercle #4 :
            Mesure : 0² = 0
         Calcul : 0 = 0
            Valeur des couleurs : 1+2 = 3
         Valeur totale : 0-0+3 = 3
      Cercle #8 :
            Mesure : 2² = 4
         Calcul : 2+2 = 4
            Valeur des couleurs : 1 = 1
         Valeur totale : 4-4+1 = 1
Suivant la même logique, les cercles #3 et #4 sont prioritaire. Colorier le #4 maintenant ou à la fin ne change rien, donc nous pouvons le colorier d'avance si nous le souhaitons :

Les Cercles #2, #8 et #9 sont des cercle voisin de cercle coloré :
   Cercle #2 :
            Mesure : 1² = 1
         Calcul : 2 = 2
            Valeur des couleurs : 1+2 = 3
         Valeur totale : 1-2+3 = 2
      Cercle #8 :
            Mesure : 1² = 1
         Calcul : 2 = 2
            Valeur des couleurs : 1+3 = 4
         Valeur totale : 1-2+4 = 3
         Cercle #9 :
            Mesure : 2² = 4
         Calcul : 1+2 = 3
            Valeur des couleurs : 3 = 3
         Valeur totale : 4-3+3 = 4
Le cercle #9 est donc coloré :

Le Cercle #2 est isolé, donc pas besoin de le calculer : il nous reste donc le cercle #5 et #8, nous continuons avec la même logique :
      Cercle #5 :
            Mesure : 1² = 1
         Calcul : 1 = 1
            Valeur des couleurs : 1 = 1
         Valeur totale : 1-1+1 = 1
      Cercle #8 :
            Mesure : 1² = 1
         Calcul : 1 = 1
            Valeur des couleurs : 1+3 = 4
         Valeur totale : 1-1+4 = 4
Le Cercle #8 est donc coloré :

Il ne reste plus que le cercle #5, pour l'obtention d'un graphe à 3 couleurs :

De ce fait, nous pouvons aussi répondre à la question du tricoloriage, qui demande a savoir à partir de quel moment il y aura toujours un minimum de 3 couleurs.

Il y aura toujours un minimum de 3 couleurs s'il y a un total de « rnd(C*(C-1)/4)+2 » d'arc de cercle, où « C » représente le nombre de cercle :
Nombre de Cercle C : ir(1,∞)
Nombre minimum d'Arc de Cercle A : rnd(C*(C-1)/4)+2
Note : Si le nombre d'arc de cercle est supérieur au maximum d'arc de cercle possible, alors le tricoloriage est simplement impossible.

Nous pouvons donc en conclure que :
   // C = Nombre de cercle.
   // c = Nombre de couleur.
   // A = Nombre minimum d'Arc de cercle.
   Pour 1 ou 2 couleurs : A = rnd(C*(C-1)/0) + (c-1)

OU : A = (c-1)
Pour plus de 2 couleurs : A = rnd(C*(C-1)/4) + (c-1)

Réponse Mathématique

SO()==
// L1 représente le nombre de cercle.
// L2 est invisible, car il représente le nombre maximum de couleur permit.
   OL(100) ;
   /* Calcul du Pole :
      2 Variable de Limitation OL : 2-1 = 1
         OM(1)
      Le maximum de dimension d'itération des Variable Primitive est de 2 :
         OM(1+2)
   Il n'y a qu'une seule variable Pn : 1-1=0
         OM(3+0)
      Il n'y a qu'une seule variable Rn : 1-1=0
         OM(3+0)
      Le nombre total de valeur isolé dans l'Origine Primitive est de 2 :
         OM(3+2)
*/
OM(5) ; // Initialise les Variables Secondaires de Mémoire i, j, k, l, et m.
/*
      P[i,j] : Arc de cercle
      P[i,i] : Mesure (nombre total d'arc de cercle)
      P[i,(L+1)] : Déclare s'il y a un cercle voisin coloré.
      R[1,i] : Liste de couleur permise (1) ou interdite (0)
      R[i,j] : Identifiant des cercles voisins & choix des couleurs.
      R[i,L] : État de calcul.
         0 : ni mesuré, ni calculé
         1 : mesuré, mais non calculé
         2 : en cour de calcul
         3 : mesuré, et calculé
      R[i,(L+1)] : Valeur du Calcul.
      M[i] : Couleur de chaque cercle.
   */
OP( L,(L+1)0² ¦ L,(L+1)0² ¦ L01 ) ;
SLP() ;
SLP()==
   // Pour chaque cercle :
PR(L,i)
{       // Si le cercle n'est pas déjà coloré :
      RA( M[i] = 0 )
      {       // Si le cercle n'est pas mesuré :
         RA( R[i,L] = 0 )
         {    SLM.1( i ) // Mesure le cercle i
         }
            // Si le cercle i possède des arcs de cercle et n'est pas calculé :
         RA( P[i,i] > 0 )
         &( R[i,L] < 3 )
         {    SLC.2( i ) // Calcul le cercle i.
         }
         AF.1( i ) ; // Attribue une couleur au cercle i
      }
}
SLM.1()==
      // Pour chaque possibilité d'arc de cercle :
PR(L,j)
{       // Excluent l'arc de cercle sur lui-même,
      RA( a1 != j )
         // S'il y a un arc de cercle,
      &( (P[a1,j] = 1) | (P[j,a1] = 1) )
         // Et que ce cercle voisin n'est pas mesuré,
      &( R[j,L] = 0 )
         // Et que ce cercle voisin n'a pas de couleur :
      &( M[j] = 0 )
      {       // Ajoute 1 à la mesure de chacun
         P[a1,a1] ++
         P[j,j] ++ ;
            // Ajoute l'identifiant de chacun dans la variable de résolution.
         R[ a1 , P[a1,a1] ] = j
         R[ j , P[j,j] ] = a1
      }
}
      // Déclare le cercle a1 comme étant mesuré.
R[ a1 , L ] = 1 ;
SLC.2()==
      // Déclare d'avance que le cercle a1 comme étant calculé.
R[ a1 , L ] = 3 ;
      // Pour chaque arc de cercle du cercle a1 :
PR( P[a1,a1] , k )
{       // Si le cercle n'est pas coloré,
      RA( M[ R[a1,k] ] = 0 )
      {       // Si le cercle voisin n'est pas mesuré :
         RA( R[ R[a1,k] , L ] = 0 )
         {    SLM.1( R[a1,k] ) ; // Mesure le cercle voisin.
         }
            // Si le cercle voisin n'est pas calculé :
         RA( R[ R[a1,k] , L ] < 3 )
         {       // Échange la valeur des mesures.
            R[ a1 , (L+1) ] += P[ R[a1,k] , R[a1,k] ]
            R[ R[a1,k] , (L+1) ] += P[a1,a1]
               // Déclare que le cercle voisin est en cour de calcul.
            R[ R[a1,k] , L ] = 2 ;
         }
      }
}
SLC.3()==
      // Pour chaque arc de cercle de a1 :
PR( P[a1,a1] , j )
{    RA( P[ R[a1,j] , (L+1) ] = 0 )
      {          // Déclare aux cercles voisins qu'il y a un cercle coloré autour d'eux.
         P[ R[a1,j] , (L+1) ] = P[ R[a1,j] , R[a1,j] ] ;
      }
         // Ajoute la valeur de la couleur du cercle coloré à ses voisins.
      R[ R[a1,j] , (L+1) ] -= M[a1]
         // Retire la valeur de la mesure de a1 aux cercles voisins.
      R[ R[a1,j] , (L+1) ] -= P[a1,a1] ;
         // Nous retirons le cercle j colorer de la liste R[a1,k].
      PR( P[ R[a1,j] , R[a1,j] ] , k )
      { RA( R[ R[a1,j] , k ] = a1 )
         { R[ R[a1,j] , k ] = R[ R[a1,j] , P[ R[a1,j] , R[a1,j] ] ]
            R[ R[a1,j] , P[ R[a1,j] , R[a1,j] ] ] = R[ R[a1,j] , k ] ;
               // Nous mettons à jour le calcul des cercles voisins.
            SLC.4( R[a1,j] )
            break ;
         }
      }
         // Retire de la mesure le cercle coloré
      P[ R[a1,j] , R[a1,j] ] -- ;
}
AF.2() ; // Choisi un nouveau cercle à colorer.
SLC.4()==
PR( P[a1,a1] , k )
{    R[ R[a1,k] , (L+1) ] -= 1
}
AF.1()==
      // Par défaut, assigne la couleur #1 au cercle a1.
M[a1] = 1 ;
      // Si le cercle a1 est voisin d'un cercle coloré
RA( P[ a1 , (L+1) ] > 0 )
{    AF.3( a1 ) ; // Sélectionne la première couleur libre.
}
      // S'il reste des cercles voisins non coloré
RA( P[a1,a1] > 0 )
{       // Actualise les possibilité de couleur.
      SLC.3( a1 ) ;
   }
AF.2()==
m = 1 ; // Par défaut, aucun cercle n'est choisi (le cercle #1 étant toujours déjà coloré).
      // Selon le nombre total de Cercle
PR(L,l)
{       // S'il est voisin d'un cercle coloré,
      RA( P[l,(L+1)] > 0 )
         // Et si le cercle n'a pas de couleur :
      &( M[l] = 0 )
      {       // Si le cercle n'est pas mesuré
         RA( R[l,L] = 0 )
         {    SLM.1( l ) ; // Mesure le cercle l
         }
            // Si le cercle n'est pas calculé :
         RA( R[l,L] < 3 )
         { SLC.2( l ) ; // Calcul le cercle l
         }
            // S'il n'a pas de cercle sélectionné :
         RA( m = 1 )
            /* Ou si la valeur des arc de cercle du cercle l est plus
            grande que celle du cercle m :
            */
         | ( (P[l,l]² - R[l,(L+1)]) > (P[m,m]² - R[m,(L+1)]) )
         {    m = l ; // Sélectionne le cercle l.
         }
      }
}
RA( m != 1 )
{    AF.1( m ) ;
}
AF.3()==
      // Par défaut, aucune couleur n'est interdite.
PR(L,j)
{    R[1, j ] = 0
}
      // Parmit tout les possibilités de couleur :
PR( P[ a1 , (L+1) ] , j )
{       // Si le cercle voisin à une couleur :
      RA( M[ R[a1,j] ] != 0 )
      {       // Mémorise la couleur.
         R[1, M[ R[a1,j] ] ] = 1 ;
      }
}
PR(L,j)
{    RA( R[ 1 , j ] = 0 )
   { M[a1] = j
         break ;
      }
}