PROGRAM Couleur;

{
Epreuve informatique de l'Ecole Polytechnique           92.023
--------------------------------------------------------------


     On cherche à colorier sur une carte N pays de telle sorte
     que chaque pays reçoive une couleur différente de ceux
     qui ont une frontière avec lui. Un coloriage est dit
     minimal si le nombre de couleurs de la palette utilisée
     est minimal.

     On va chercher à écrire un programme Pascal qui résout ce
     problème dans le cas général (méthode théorique), et le
     tester ensuite sur un exemple européen (application
     pratique).


METHODE THEORIQUE

1)   Construire une matrice C dont les coefficients valent 1
     ou 0 selon que deux pays ont ou non une frontière
     commune. Cette matrice NxN est appelée matrice de
     contiguïté. Quelles sont ses propriétés ?

2)   On note E l'ensemble constitué par les N pays et P(E)
     l'ensemble des parties de E.
                                                      N
     -    Montrer que P(E) est en bijection avec (0,1) , et en
          déduire une façon simple d'énumérer ses éléments.

     -    A partir de P(E) et à l'aide de la matrice C, écrire
          un algorithme permettant de construire P  (E),
                                                  NC
          l'ensemble des parties de E composées chacune de
          pays n'ayant deux à deux entre eux aucune frontière
          commune.

3)        Déduire de ce qui précède un programme Pascal qui
          détermine P° (E) l'ensemble  des parties p de E
                     NC
          satisfaisant aux deux conditions suivantes :

          -    p est un élément de P  (E)
                                    NC

          -    si un pays de E n'est pas contenu dans p, il a
               une frontière commune avec au moins un des pays
               contenus dans p.

4)        On appelle coloriage de E une famille d'élements de
          P  (E) qui forment une partition de E .
           NC

          Montrer comment, en utilisant la solution de la
          question précédente, on peut expliciter les
          différents coloriages de E, et en déduire les
          coloriages minimaux. Ecrire le programme Pascal
          correspondant.


APPLICATION PRATIQUE

5/   Soit à colorier la carte des 8 pays d'Europe suivante :

	E = (F, SP, P, CH, I, B, D, NL)

     où la matrice  de contiguïté se déduit de :


                   F  SP P  CH I  B  D  N

              F       1  0  1  1  1  1  0
              SP         1  0  0  0  0  0
              P             0  0  0  0  0
              CH               1  0  1  0
              I                   0  0  0
              B                      1  1
              D                         1
              NL




     Définir tous les coloriages minimaux.

     Combien faut-il de couleurs au minimum pour colorier
     cette carte ?

     En appliquant le même programme à d'autres exemples de
     cartes, quelle observation peut-on faire sur le nombre
     minimum de couleurs nécessaires pour les colorier ?



+------------------------------------------------------------+
¦              Imprimer tous les résultats                   ¦
¦     en indiquant chaque fois à quoi ils correspondent      ¦
+------------------------------------------------------------+




                            -=-=-=-
}
USES
    Modubase, Crt;


CONST
     N = 8; { N <= 16 }
     NomPays : ARRAY [ 1..N ] OF STRING
             = ('F','E','P','CH','I','B','D','HL');

     C       : ARRAY [ 1..N , 1..N ] OF BYTE
               =(
               (0,1,0,1,1,1,1,0),
               (0,0,1,0,0,0,0,0),
               (0,0,0,0,0,0,0,0),
               (0,0,0,0,1,0,1,0),
               (0,0,0,0,0,0,0,0),
               (0,0,0,0,0,0,1,1),
               (0,0,0,0,0,0,0,1),
               (0,0,0,0,0,0,0,0)
               );

     Nbpmax  =   1000;


VAR
   E            :       WORD;
   CardPE       :       WORD;
   { Pnc(E) }
   Nbpnc        :       WORD;
   PNC          :       ARRAY [1..Nbpmax] OF WORD;
   { PncM(E) }
   NbpncM       :       WORD;
   PNCM         :       ARRAY [1..Nbpmax] OF WORD;


FUNCTION Appartient ( Pays , Partie : Word ) : BOOLEAN;
  BEGIN
       Appartient := ( Partie AND (1 Shl (Pays-1)) <> 0);
  END;

PROCEDURE AffichePartie ( Partie : WORD );
  VAR
     Pays : WORD;
  BEGIN
       Write ( 'Partie : ' );
       FOR Pays :=1 TO N DO IF Appartient (Pays,Partie) THEN
           Write ( NomPays[Pays] ,',' );
       WriteLn;
  END;

¢I=
�
eËV­l«VU–d%H¨artie : LONGINT );
 2VUR
 2 2 w 2 UOTD3
2 BEUIT
2 2    WviveLn ( 'Recouvrement : '2);
       FOR2i :=1 TO NbpncM DO
        IF (Partie AND (1 Shl (i-1) ))<>0 THEN
         BEGIN
              Write('Choisir une couleur pour la ');
              AffichePartie (PNCM[i]);
         END;
  END;


PROCEDURE TITRE(t:string);
begin
     WriteLN;
     WriteLN('**********  ',t,'    ************');
     WriteLN;
end;


PROCEDURE Question1;  { Initialisation }
  VAR
     p1,p2  :  INTEGER;
  BEGIN
       Titre('Question 1');
       { Symétrisation de la matrice C à partir du triangle sup droit }
       FOR p1:=2 TO N DO FOR p2:=1 TO p1-1 DO C[p1,p2]:=C[p2,p1];
       { Calcul du cardinal de P(E) }
       CardPE := 1 Shl N;
       E:=0;
       FOR p1 := 1 TO N DO
        E := E OR ( 1 Shl ( p1-1) );
  END;




PROCEDURE Question2;  { Construction de Pnc(E) }
  VAR
     Partie     : WORD;
     Cnt        : BOOLEAN;
     Pays1,
     Pays2      : WORD;
  BEGIN
       Titre('Question 2');
       Nbpnc:=0;
       FOR Partie := 1 TO CardPE-1 DO
       BEGIN
            Cnt := FALSE;
            FOR Pays1:=1 TO N DO FOR Pays2:=1 TO N DO
              IF C[Pays1,Pays2]=1 THEN
                 IF Appartient(Pays1,Partie) AND Appartient(Pays2,Partie)
                    THEN Cnt:=TRUE;
            IF NOT Cnt THEN
            BEGIN
                 Inc(Nbpnc);
                 PNC[Nbpnc]:=Partie;

            END;
       END;
  END;

PROCEDURE Question3; { Construction de PncM(E) à partir de Pnc(E) }
  VAR
     Partie1,Partie2  :  WORD;
     Maximum          :  BOOLEAN;
  BEGIN
       Titre('Question 3');
       NbpncM:=0;
       FOR Partie1:=1 TO Nbpnc DO
       BEGIN
            Maximum := TRUE;
            FOR Partie2:=1 TO Nbpnc DO IF Partie1<>Partie2 THEN
              IF ( PNC[Partie1] OR PNC[Partie2] ) = PNC[Partie2]
                 THEN Maximum:=FALSE;
            IF Maximum THEN
            BEGIN
                 Inc(NbpncM);
                 PNCM[NbpncM]:=PNC[Partie1];
                 AffichePartie(PNCM[NbpncM]);
            END;
       END;
  END;

PROCEDURE Question4;
  VAR
     CardRec : LONGINT;
     Partie  : LONGINT;
     i       : WORD;
     Rec     : WORD;
     c       : WORD;
  BEGIN
       Titre('Question 4');
       CardRec := 1 Shl NbpncM;
       FOR Partie := 1 TO CardRec-1 DO
        BEGIN
            Rec:=0;
            c:=0;
            FOR i := 1 TO NbpncM DO
               IF ( Partie AND (1 Shl (i-1)))<>0 THEN
                    BEGIN
                         Inc(c);
                         Rec:= Rec OR PNCM[i];
                    END;
{              Write (rec,',');}
            IF (Rec=E) AND (c=3) THEN
               AfficheRec(Partie);
        END;

  END;

BEGIN
     ClrScr;
     Question1;
     Question2;
     Question3;
     Question4;
     Titre('terminé');
     Pause;