Problema colorării hărţilor

Fiind dată o hartă cu n tări, se cer toate modalităţile de colorare a hărţii, utilizând cel mult m culori, astfel încât două ţări cu frontieră comună să fie colorare diferit. Este demonstrat faptul că sunt suficiente numai 4 culori ca orice hartă să poată fi colorată.

Pentru rezolvare se vor folosi:

k: variabilă întreagă, care reprezintă o ţară

x: vector cu componente întregi cu proprietatea xk reprezintă culoarea ţării cu numărul k

deoarece sunt n ţări şi m culori, k={1,...,n} şi xk={1,...,m}

x=(x1,x2,...,xn) unde xkÎ{1,...,n}.

Concluzie:

Ţara k şi ţara i sunt vecine, dacă (ai,k=1) sau (ak,i=1)

Ţara k şi ţara i au aceeaşi culoare dacă xk=xi

Comentarii la funcţia valid:

Trebuie verificat dacă ţara k şi ţara i ce sunt ţări vecine au culori diferite, adică dacă

ak,i=1 pentru xk¹xi, pentru i=1...k-1.

#include<iostream.h>

#include<math.h>

typedef int sir[100];

sir x;

int m,i,k,n,j;

int as,ev;

int a[100][100];

void succ(sir x, int k, int &as)

{

if(x[k]<n)

  {

  as=1;

  x[k]=x[k]+1;

  }

else as=0;

}

void valid(sir x, int k, int &ev)

{

ev =1;

for(i=1;i<=k-1;i++)

  if((a[k][i]==1)&&(x[k]==x[i]))

  ev=0;

}

void afis(sir x,int k)

{

int i;

for(i=1;i<=k;i++)

  cout<<x[i]<<" ";

cout<<endl;

}

Se verifică dacă ai,k=1 atunci

xk¹xi, unde i=1,...k-1

int main(void)

{

cout<<"Dati numarul de tari:";

cin>>n;

for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  {

  cin>>a[i][j];

  a[j][i]=a[i][j];

  }

k=1;

x[k]=0;

while(k>0)

  {

    do

      {

        succ(x,k,as);

        if(as) valid(x,k,ev);

      }

    while(as&&!ev);

    if(as)

        if(k==n) afis(x,k);

        else

  {

    k=k+1; x[k]=0;

  }

    else k=k-1;

    }

}