ALGORITMOS DE COLORACIÓN DE GRAFOS

Existen problemas muy complicados para los que:

No sabemos cómo encontrar su solución óptima, o bien.
Conocemos el algoritmo que permite encontrar la solución óptima, pero requiere una cantidad excesiva de tiempo (Tiene un tiempo de ejecución no polinómico)

Al hablar de algoritmos heurísticos, nos referimos a un procedimiento que puede producir una buena solución para nuestro problema, incluso una solución óptima si somos afortunados, pero que por otro lado puede no producir una solución, o dar lugar a una que no sea precisamente óptima. Una forma en la que son muy usados es con los algoritmos voraces.

En estos casos utilizaremos algoritmos heurísticos:

Proporcionan soluciones más o menos próximas a la óptima, en un tiempo de ejecución polinómico.
Permiten resolver ejemplares del problema de tamaños que serían inabordables utilizando el algoritmo óptimo.
Muchos de los algoritmos heurísticos y aproximados son algoritmos voraces.

TEORIA DE GRAFOS:

En matemáticas y en ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos.

Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas que pueden ser orientados o no.

Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Vértice

Los vértices o nodos, constituyen uno de los dos elementos que forman un grafo. Se define también como la unidad fundamental de la que están compuestos los grafos.

Los vértices son tratados, en la teoría de Grafos, como unidades indivisibles y sin propiedades, aunque pueden tener estructuras adicionales dependiendo del uso del grafo al que pertenecen.

Arista

Las aristas, junto con los vértices, forman los elementos principales de un grafo. Se definen como las uniones entre nodos o vértices. Usualmente las aristas denotan relaciones entre los vértices, como el orden, la vecindad o la herencia.

Las aristas además de unir dos vértices suelen tener una dirección establecida. Es decir, que a b sería una arista distinta que a  b, pudiendo existir ambas en el mismo grafo (a <===> b). Siendo estos grafos conocidos como dirigidos.

En algunos tipos de grafos las aristas llevan asociadas un número que indica una información asociada a ambos vértices. Pueden indicar un coste o ser una representación del trabajo necesario para recorrer el camino de un vértice al otro. Puede darse el caso en que el camino de A hacia B tenga un coste diferente que el de B hacia A.

Finalmente, no existe obligación de que dados dos vértices exista una arista que los una. Es decir, la relación entre vértices y aristas no tiene por qué producirse.

Grado

El grado de un vértice v, que se denota como (v), se define como la cantidad de aristas que llegan o salen de él. Para grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas incidentes a este vértice. Para los grafos dirigidos, a un vértice del que sólo salen aristas se le denomina fuente. Por el contrario, a aquellos en los que sólo entran aristas se les denomina pozo o sumidero.

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

COLORACIÓN DE GRAFOS

En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada arista talque aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes. El vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformados a una versión con vértices. Por ejemplo, una arista coloración de un grafo es justamente una vértice coloración del grafo línea respectivo, y una coloración de caras de un grafo plano es una vértice coloración del grafo dual.

ALGORITMOS HEURÍSTICOS PARA EL COLOREADO DE GRAFOS

Se trata de colorear los nodos de un grafo de forma que no haya dos nodos adyacentes del mismo color.

Utilizando el mínimo número de colores posible.
Es uno de los problemas NP-completos clásicos (no existe ningún algoritmo de tiempo polinómico que le resuelva de forma óptima).

Los siguientes algoritmos solucionan el problema del coloreado de grafos:

Algoritmo Secuencial o Voraz
Algoritmo de coloración Welsh- Powell
Algoritmo de coloración Matula-Marble-Isaccson

ALGORITMO SECUENCIAL O VORAZ

Este algoritmo sigue una estrategia voraz, es decir comienza la coloración de los vértices según orden de los éstos en la matriz de adyacencias del grafo. La coloración se realiza siguiendo los siguientes pasos.

Ingresamos el número de nodos y las aristas, se llenan los datos y creamos la matriz de adyacencias.
(Inicia Algoritmo Secuencial)Se tienen ordenados los vértices de 1 a n, y se selecciona el primero en la lista y se colorea o se etiqueta con el 1.
Se toma el siguiente vértice y se colorea o etiqueta con en el menor número admisible; es decir, se verifican adyacencias.
Se repite el paso (3) hasta que todos los vértices hayan sido coloreados.
Se imprime la solución.

Ejemplo:

ALGORITMO DE COLORACION WELSH-POWELL:

En este algoritmo la única diferencia respecto al algoritmo voraz es el orden en el que se realiza la coloración de vértices.

En este caso los vértices se ordenan de mayor a menor grado es decir en función del número de vértices adyacentes

ALGORITMO:

Se ordenan los vértices de mayor a menor grado, se selecciona el primero en la lista y se colorea o se etiqueta con el 1.
Se toma el siguiente vértice y se colorea o etiqueta con en el menor número admisible; es decir, se verifican adyacencias.
Se repite el paso (2) hasta que todos los vértices hayan sido coloreados.
Se imprime la solución.

EJEMPLO:

ALGORITMO DE COLORACIÓN MATULA-MARBLE-ISACCSON

La única diferencia respecto a los otros dos algoritmos de coloraciones el orden en el que se realiza la coloración vértices. En este caso el orden de los vértices es inverso al proceso de selección.

Primero se elige V(n) como el vértice menor grado, luego se elige V(n-1) como el vértice de menor grado en G-{V(n)} (prescindiendo del vértice V(n)), y así se continua examinando los vértices de menor grado.

ALGORITMO:

Se ordenan los vértices de menor a mayor grado, se selecciona el primero en la lista y se colorea o se etiqueta con el 1.
Se toma el siguiente vértice y se colorea o etiqueta con en el menor número admisible; es decir, se verifican adyacencias.
Se repite el paso (2) hasta que todos los vértices hayan sido coloreados.
Se imprime la solución.

Implementación

#include  < cstdlib > 
#include  < iostream > 
#include  < conio.h > 
#include  < windows.h > 
#include  < stdio.h > 
#include  < stdlib.h > 
#define vertices 500
#define nodos 300

using namespace std;

struct  orden{
int  grado; //representa el numero  de conexiones
int  color; // representa el valor del numero
int  n;  //representa el numero  de vertice 
};
typedef struct  orden ver;

int B[nodos];//,ad[vertices][vertices];

//Ordenamos Mediante el Metodo de Ordenacion: Inserccion
void OrdenarMayaMen(int n, ver v[])
{
    int i,k;
    int aux,aux1;
    for(i=1;i < n;i++)
    {
            aux=v[i].grado;
            aux1=B[i];
            k=i-1;
            while(k > =0 && aux > v[k].grado)
            {
                v[k+1].grado=v[k].grado;
                B[k+1]=B[k];
                k=k-1;
            }
            v[k+1].grado=aux;
            B[k+1]=aux1;
    }
}

void IngresarMatriz(int ad[][vertices],int nds, int arst)//,int ad[][vertices]) //Es  para guardar la matriz de  Adyacencias :P
{   
  int i,j,nodoi,nodof; 
  
  for(i=0;i < nds;i++)
   { for(j=0;j < nds;j++)
        { ad[i][j]=0;}
   }
   
  //Llenamos la  matriz
  for(i=0;i < arst;i++)  
   { cout <  < "\n\n\tArista " <  < i+1 <  < "\n";
     cout <  < "\tN. inicio: ";
     cin >  > nodoi;
     cout <  < "\tN. termino: ";
     cin >  > nodof;   
     
     ad[nodoi-1][nodof-1]=1;
     ad[nodof-1][nodoi-1]=1;
   } 
  
   //Matriz de Adyacencia    
  /* for(i=0;i < nds;i++)
     { for(j=0;j < nds;j++)
         ad[i][j]=ad[i][j]; 
     
      }*/
}


void Greedy(int ad[][vertices],int nds)//,int  ad[vertices][vertices])
{ 
  ver v[nds];
  int i,j,aux,zz,max=1;   

  //Etapa de  Coloracion
   for(i=0;i < nds;i++)
    {v[i].color=1;
     zz=0;
     aux=1;
     while(aux==1)
      {for(j=0;j < nds;j++)
         { if(ad[j][i]==1)
            {if(v[i].color==v[j].color)
               { zz=1;}
            }
         }
         if(zz==1)
           {aux=1;
            zz=0;
            v[i].color++;
           }
         else
            {aux=0;}
            if(v[i].color   >   max)
              { max=v[i].color;}
       }
     }

  cout <  < "\n\tAlgoritmo Voraz \n" <  < "\tmaxcolor= " <  < max <  < "\n";

  //Se imprime el  conjunto de  vertices  de  cada color    
  for(i=0;i < max;i++)
  {printf("\t  %c= { ",'a'+i);
    for(j=0;j < nds;j++)
     { if(v[j].color==i+1)
         cout <  < " " <  < j+1;        
     }
    cout <  < "  }\n";
  }

}

void WelshPowell(int ad[][vertices],int  nds)//,int ad[][vertices])
{
  ver v[nds]; 
  int x,y,i,j,aux,zz,max=1;
  //Se inicializa  el  grado y  color en  cero
  for(i=0;i < nds;i++)
  { v[i].grado=0; 
    v[i].color=0;
    v[i].n=i;
  }
   //Se encuentra el  grado de  los vertices.
   for(i=0;i < nds;i++)
   {for(j=0;j < nds;j++)
       {if(ad[i][j]==1)
          {v[i].grado++;
           v[j].grado++;
           //cout <  < " " <  < v[i].grado <  < " " <  < v[j].grado <  < endl;
          }
        }
   }
   
   for(i=0;i < nds;i++)
   {  v[i].grado=v[i].grado/2;
      //cout <  < " " <  < v[i].grado <  < endl;
      B[i]=i;
   }
   //Ordenacion en  funcion  de  sus   grados!
   OrdenarMayaMen(nds,v);
   for(i=0;i < nds;i++)
      v[i].n=B[i];   

  //Etapa de Coloracion
   for(i=0;i < nds;i++)
    {v[i].color=1;
     zz==0;
     aux=1;
      while(aux==1)
      { for(j=0;j < nds;j++)
         { if(ad[v[j].n][v[i].n]==1)
             {if(v[i].color==v[j].color)
               {zz=1;}
             }
          }
         if(zz==1)
         {v[i].color++;
          zz=0;
          aux=1;
         }else
          {aux=0;
          }
          if(v[i].color > max)
            {max=v[i].color;
            }
      }
     }
 //Se  Imprime el  Coloreo
 
  cout <  < "\n\tAlgoritmo de coloraci\xa2n Welsh-Powell\n" <  < "\tmaxcolor= " <  < max <  < "\n";
  
  //Se imprime el  conjunto de  vertices  de  cada color
  for(i=0;i < max;i++)
   { printf("\t %c= { ",'a'+i); 
      for(j=0;j < nds;j++)
       { if(v[j].color==i+1)
          cout <  < " " <  < v[j].n+1;         
       }
      cout <  < "  }\n"; 
   }
 
}

void MMI(int ad[][vertices],int  nds)//,int ad[][vertices])
{
ver v[nds];
int x,y,i,j,k,aux,zz,max=1;

  //Se inicializa  el  grado y  color en  cero
   for(i=0;i < nds;i++)
    {v[i].grado=0;
     v[i].color=0;
     v[i].n=i+1;
    }
   //Se encuentra el  grado de  los vertices.
    for(i=0;i < nds;i++)
     {for(j=0;j < nds;j++)
       { if(ad[i][j]==1)
           {v[i].grado++;
            v[j].grado++;
           }
       }
     }
     
    for(i=0;i < nds;i++)
       v[i].grado=v[i].grado/2;     

   k=nds;
   for(i=0;i < nds;i++)
     { v[i].n=B[k-1];
       k--;
     } 

    //Etapa de  Coloracion 
   //v[0].color=1; 
   for(i=0;i < nds;i++)
    { v[i].color=1;
      zz==0;
      aux=1;
      while(aux==1)
       { for(j=0;j < nds;j++)
           {if(ad[v[i].n][v[j].n])
              { if(v[i].color==v[j].color)
                {zz=1;}
              }
           }
           if(zz==1)
           { v[i].color++;
             zz=0;
             aux=1;
           }else
           {aux=0;}
              if(v[i].color > max)
               { max=v[i].color;}
        }
     }

   //Se  Imprime el  Coloreo  
  cout <  < "\n\tAlgoritmo de  coloraci\xa2n Matula-Marble-Isaacson\n" <  < "\tmaxcolor= " <  < max <  < "\n";

  //Se imprime el  conjunto de  vertices  de  cada   color
  for(i=0;i < max;i++)
    {printf("\t %c= { ",'a'+i);
     for(j=0;j < nds;j++)
      { if(v[j].color==i+1)
         cout <  < " " <  < v[j].n+1;        
      }
    cout <  < "  }\n";
   }

}

int main(int argc, char *argv[])
{
  int i,j,cant_nodos,cant_aristas,ad[vertices][vertices];
  char s,N,n;
  do{  
  cout <  < "\n\t\tALGORITMOS HEURISTICOS PARA EL COLOREADO DE GRAFOS\n";  
  cout <  < "\t\t--------------------------------------------------\n"; 

  cout <  < "\n\n\t Ingrese Datos \n"; 
  cout <  < "\n\t Num. Nodos: ";
  cin >  > cant_nodos;
  cout <  < "\t Aristas: ";
  cin >  > cant_aristas;  
  
  //Aqui se  crea la matriz de  adyacencia
  IngresarMatriz(ad,cant_nodos,cant_aristas);//,ad);
  //Mostrar Matriz de Adyacencia
  /* cout <  < "\n\t";
   for(i=0;i < nds;i++)
     { for(j=0;j < nds;j++)
         ad[i][j]=ad[i][j]; 
        cout <  < "\n\t";
      }
  */    
  //Se colorea vertice  a  vertice en  el  orden inicial
  Greedy(ad,cant_nodos);//,ad);  
  //Se colorea vertice  a  vertice iniciando  por los de  mayor  grado  
  WelshPowell(ad,cant_nodos);//,ad);
  //Se colorea vertice  a  vertice iniciando  por los de  menor  grado
  MMI(ad,cant_nodos);//,ad);
  
 cout <  < "\n\tSi desea continuar presione cualquier tecla \n\tSi no escriba 'n' o 'N': ";
 s=getch();
 system("cls");
  }while(s!='N' && s!='n');
 cout <  < "Hasta Luego!!!!";
 Sleep(1600);
 exit(0);    
  
 cout <  < "\n\n";
 system("PAUSE");
}