jueves, 13 de agosto de 2015

CIFRADO RSA

RSA es uno de los sistemas de cifrado (encriptación) asimétricos, más exitosos en la actualidad. Originalmente descubierto 1973 por la agencia de inteligencia británica GCHQ, Government Communications Headquarters (GCHQ), recibió la clasificación de alto secreto “Top Secret”.
 El algoritmo fue descrito en 1977 y es propiedad de los criptólogos Ron Rivest,  Adi Shamir y Leonard Adleman,  del Instituto Tecnológico de Massachusetts (MIT) - RSA sol las letras iniciales de sus apellidos.

El algoritmo fue patentado por MIT en 1983 y no fue revelado hasta 1997. A diferencia de los sistemas de codificación simétrica tradicionales, RSA trabaja con dos claves diferentes: una clave "pública", y otra "privada". Ambas son complementarias entre sí (trabajan de manera conjunta) así que un mensaje cifrado con una de ellas sólo puede ser descifrado por su contraparte. Dado que la clave privada no se puede calcular a partir de la clave pública, esta última queda generalmente queda a disposición del público. Estas propiedades permiten que los cripto-sistemas asimétricos sean utilizados en una amplia variedad de funciones, tales como las firmas digitales.


Algoritmo RSA:

El Algoritmo RSA Consta de 3 partes, la primera hace referencia a la generación de las claves o llaves que serán usadas para la encriptación  del mensaje, la segunda el proceso de encriptado y la tercera el proceso de desencriptar el mensaje.


Generación de las Llaves (Pública y Privada).



























Para generar un par de claves (KP ; Kp), en primer lugar se eligen aleatoriamente dos números primos grandes, p y q (de unas 200 cifras cada uno, por ejemplo). Después se calcula el producto n = p.q Escogeremos ahora un número e primo relativo con (p-1) y con (q-1). Este par de números (e,n) pueden ser conocidos por cualquiera, y constituyen la llamada clave pública e por tanto debe tener un inverso módulo (p-1)(q-1), al que llamamos d. Por supuesto se cumple que ed ≡ 1 mod((p-1)(q-1)), que es lo mismo que decir que ed = 1+k (p-1)(q-1) para algún entero k. La clave privada será el par (d,n). Este número d debe mantenerse secreto y sólo será conocido por el propietario del par de claves.


Proceso de Encriptación y Desencriptación del Mensaje






















Ejemplo Aplicativo:


























Implementación


Clase Conversor
public class Conversor {
    public int numero(String a){
        int C=-666;
        if(a.equals(" ")){
            C=-555;
        }else if(a.equals("a")||a.equals("A")){
            C=0;
        }else if(a.equals("b")||a.equals("B")){
            C=1;
        }else if(a.equals("c")||a.equals("C")){
            C=2;
        }else if(a.equals("d")||a.equals("D")){
            C=3;
        }else if(a.equals("e")||a.equals("E")){
            C=4;
        }else if(a.equals("f")||a.equals("F")){
            C=5;
        }else if(a.equals("g")||a.equals("G")){
            C=6;
        }else if(a.equals("h")||a.equals("H")){
            C=7;
        }else if(a.equals("i")||a.equals("I")){
            C=8;
        }else if(a.equals("j")||a.equals("J")){
            C=9;
        }else if(a.equals("k")||a.equals("K")){
            C=10;
        }else if(a.equals("l")||a.equals("L")){
            C=11;
        }else if(a.equals("m")||a.equals("M")){
            C=12;
        }else if(a.equals("n")||a.equals("N")){
            C=13;
        }else if(a.equals("o")||a.equals("O")){
            C=14;
        }else if(a.equals("p")||a.equals("P")){
            C=15;
        }else if(a.equals("q")||a.equals("Q")){
            C=16;
        }else if(a.equals("r")||a.equals("R")){
            C=17;
        }else if(a.equals("s")||a.equals("S")){
            C=18;
        }else if(a.equals("t")||a.equals("T")){
            C=19;
        }else if(a.equals("u")||a.equals("U")){
            C=20;
        }else if(a.equals("v")||a.equals("V")){
            C=21;
        }else if(a.equals("w")||a.equals("W")){
            C=22;
        }else if(a.equals("x")||a.equals("X")){
            C=23;
        }else if(a.equals("y")||a.equals("Y")){
            C=24;
        }else if(a.equals("z")||a.equals("Z")){
            C=25;
        }
        return C;
    }
    
    public String numeroletra(int a){
        String C=null;
        if(a==-555){
            C=" ";
        }else if(a==0){
            C="00";
        }else if(a==1){
            C="01";
        }else if(a==2){
            C="02";
        }else if(a==3){
            C="03";
        }else if(a==4){
            C="04";
        }else if(a==5){
            C="05";
        }else if(a==6){
            C="06";
        }else if(a==7){
            C="07";
        }else if(a==8){
            C="08";
        }else if(a==9){
            C="09";
        }else if(a==10){
            C="10";
        }else if(a==11){
            C="11";
        }else if(a==12){
            C="12";
        }else if(a==13){
            C="13";
        }else if(a==14){
            C="14";
        }else if(a==15){
            C="15";
        }else if(a==16){
            C="16";
        }else if(a==17){
            C="17";
        }else if(a==18){
            C="18";
        }else if(a==19){
            C="19";
        }else if(a==20){
            C="20";
        }else if(a==21){
            C="21";
        }else if(a==22){
            C="22";
        }else if(a==23){
            C="23";
        }else if(a==24){
            C="24";
        }else if(a==25){
            C="25";
        }
        return C;
    }
    
    public String letranumero(int a){
        String C=null;
        if(a==-555){
            C=" ";
        }else if(a==0){
            C="A";
        }else if(a==1){
            C="B";
        }else if(a==2){
            C="C";
        }else if(a==3){
            C="D";
        }else if(a==4){
            C="E";
        }else if(a==5){
            C="F";
        }else if(a==6){
            C="G";
        }else if(a==7){
            C="H";
        }else if(a==8){
            C="I";
        }else if(a==9){
            C="J";
        }else if(a==10){
            C="K";
        }else if(a==11){
            C="L";
        }else if(a==12){
            C="M";
        }else if(a==13){
            C="N";
        }else if(a==14){
            C="O";
        }else if(a==15){
            C="P";
        }else if(a==16){
            C="Q";
        }else if(a==17){
            C="R";
        }else if(a==18){
            C="S";
        }else if(a==19){
            C="T";
        }else if(a==20){
            C="U";
        }else if(a==21){
            C="V";
        }else if(a==22){
            C="W";
        }else if(a==23){
            C="X";
        }else if(a==24){
            C="Y";
        }else if(a==25){
            C="Z";
        }
        return C;
    }
    
}

Clase Euclides
public class Euclides {
public long[] euclidesExtendido(long a, long b) 
{
 long[] resp = new long[3];
 long x=0,y=0,d=0;
 if(b==0)
 {
  resp[0] = a; resp[1] = 1; resp[2] = 0;
 } 
 else
 {
  long x2 = 1, x1 = 0, y2 = 0, y1 = 1;
  long q = 0, r = 0;
  while(b > 0)
  {
   q = (a/b);
   r = a - q*b;
   x = x2-q*x1;
   y = y2 - q*y1;
   a = b;
   b = r;
   x2 = x1;
   x1 = x;
   y2 = y1;
   y1 = y;
  }
  resp[0] = a;
  resp[1] = x2;
  resp[2] = y2;
    }
 return resp;  
    } 
}

Clase Exponenciación
public int CalcularExp(int a,int k,int z)
    {
        int exp=1;
        int xp=a%z;
        while(k > 0)
        {
            if((k%2)!=0)
            {
                exp=(exp*xp)%z;
            }
            xp=(xp*xp)%z;
            k=k/2;
        }
        return exp;
    }

Clase Inverso
public class Inverso {
    public double CalcularInverso(long n,long z)
    {
        long mcd[] =new long[3];
        int x=0,y = 0;
        Euclides obj = new Euclides();
        if(n > z)
        {
            mcd=obj.euclidesExtendido(n,z);
        }
        if(n < z)
        {
            mcd=obj.euclidesExtendido(z,n);
        }
        if(mcd[0] > 1)
        {
            System.out.println("EL INVERSO NO EXISTE");
            y=0;
        }
        else
        {
            y=(int) mcd[2];
            if(y < 0)
            {
                y=(int) (y+z);
            }
        }
        return y;
    }
}


Clase RSA
import java.util.ArrayList;
public class RSA {
    private long n, q, p;
    private long fi,e,d;
    private String mensaje;
    private String cifrado;
    private String MensajeLimpio;
    private String num_letra;
    private String CadenaDescifradaNumeros;
    public RSA()
    {
        //this.p=43;
        //this.q=59;
        //this.e=13;
        GenerarKey();
    }

    public String getCadenaDescifradaNumeros() {
        return CadenaDescifradaNumeros;
    }

    public String getNum_letra() {
        return num_letra;
    }



    public String getMensajeLimpio() {
        return MensajeLimpio;
    }

    public long getN() {
        return n;
    }

    public long getQ() {
        return q;
    }

    public long getP() {
        return p;
    }

    public long getFi() {
        return fi;
    }

    public long getE() {
        return e;
    }

    public long getD() {
        return d;
    }

    public String getMensaje() {
        return mensaje;
    }

    public String getCifrado() {
        return cifrado;
    }
    public void RecibirMensaje(String m)
    {
        this.mensaje=m;
    }
    public void RecibirCifrado(String c)
    {
        this.cifrado=c;
    }
    public boolean primo(int n)
    {
 for(int i=2;i < n;i++)
        {
            if(n%i==0)
            {
                return false;
            }
        }
 return true;
    }
    public void GenerarPrimos()
    {
        Boolean resP,resQ;
        do
        {
            p = (int)(Math.random()*(100-10+1)+10); 
            q = (int)(Math.random()*(100-10+1)+10); 
            resP=primo((int) p);
            resQ=primo((int) q);
        }while((p==q)||(resP==false)||(resQ==false));
        System.out.println("P:"+p);
        System.out.println("Q:"+q);
    }
    public int GenerarE()
    {
        Boolean resE;
        long mcd[]= new long[3];
        Euclides euclides = new Euclides();
        do
        {
            e = (int)(Math.random()*(100-1+1)+1);
            resE=primo((int) e);
            mcd=euclides.euclidesExtendido(e, fi);
        }while((e > =fi)||(mcd[0]!=1)||(resE==false));
        return (int) e;
    }
    public void GenerarKey()
    {
        GenerarPrimos();
        Inverso inverso= new Inverso();
        n=p*q;
        fi=(p-1)*(q-1);
        e=GenerarE();
        d=(long) inverso.CalcularInverso(e,fi);
        if(d < 0)
        {
            d=d+fi;
        }  
        System.out.println("n: "+n);
        System.out.println("fi: "+fi);
        System.out.println("e: "+e);
        System.out.println("d: "+d);
    }
    public String EliminarEspaciosCaracteresEspeciales()
    {
        //Eliminando los espacios y caracteres especiales
        String AlfabetoValido="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
        String aux_mensaje="";
        int contador=0;
        for(int i=0;i < mensaje.length();i++)
        {
            for(int j=0;j < AlfabetoValido.length();j++)
            {
                if(!String.valueOf(mensaje.charAt(i)).equals(String.valueOf(AlfabetoValido.charAt(j))))
                {
                    contador++;
                }
            }
            if(contador > =AlfabetoValido.length())
            {
                //AL EVALUAR EL CARACTER CON TODOS LOS ELEMENTOS DE LA CADENA UNA DEBE DE COINCIDIR POR LO QUE EL VALOR DEL CONTADOR DEBE SER UNO MENOS QUE
                //EL DEL TAMAÑO DE ALFABETOVALIDO, SI SON IGUALES O ES MAYOR SIGNIFICA QUE ESE CARACTER NO ES VALIDO Y DEBE SER IGNORADO
            }
            else
            {
                aux_mensaje=aux_mensaje+mensaje.charAt(i);//CREANDO UNA NUEVA CADENA SIN ESPACIOS
            }
            contador=0;
        }
        //En el caso de que falten caracteres para la agrupacion de 4, se completan con un x
        if(aux_mensaje.length()%2!=0)
        {
            aux_mensaje=aux_mensaje+"X";
        }
        return aux_mensaje;
    }
    public String ConvertirNumeros(String mensaje_sin_espacios)
    {
        int aux_num_letra;
        num_letra ="";
        Conversor letras= new Conversor();
        for(int i=0;i < mensaje_sin_espacios.length();i++)
        {
            //Realizando la conversion a numeros
            aux_num_letra=letras.numero(String.valueOf(mensaje_sin_espacios.charAt(i)));
            num_letra=num_letra+letras.numeroletra(aux_num_letra);
           
        }
        return num_letra;
    }
    public String ConvertirCadena(String cadenacifrada)
    {
        Conversor letras= new Conversor();
        int inicioC=0,finalC=2;
        String TextoCifrado="",aux_TextoCifrado;
        for(int i=0;i < cadenacifrada.length();i++)
        {
            aux_TextoCifrado=cadenacifrada.substring(inicioC,finalC);
            if(Integer.parseInt(aux_TextoCifrado) > 25)
            {
                aux_TextoCifrado=String.valueOf(Integer.parseInt(aux_TextoCifrado)%26);
            }
            TextoCifrado=TextoCifrado+letras.letranumero(Integer.parseInt(aux_TextoCifrado));//CREANDO UNA NUEVA CADENA SIN ESPACIOS
            inicioC=finalC;
            finalC=finalC+2;
            i=inicioC;
        }
        return TextoCifrado;
    }
    public String Cifrar(String num_letra)
    {
        Exponenciacion expo= new Exponenciacion();
        ArrayList < String >  Cifrado = new ArrayList <  > ();
        int inicioC=0,finalC=4,rexpo = 0;
        String auxiliar;
        for(int i =0 ;i < num_letra.length();i++)
        {
            auxiliar=num_letra.substring(inicioC,finalC);
            System.out.println("SUBCADENA ANTES DE CIFRAR: "+auxiliar);
            //Realizando operacion de encriptado
            rexpo=expo.CalcularExp(Integer.parseInt(auxiliar),(int)e,(int)n);
            System.out.println("YA ME CIFRARON: "+rexpo);
            //ALMACENANDO
            if(String.valueOf(rexpo).length()==1)
            {
                Cifrado.add("000"+String.valueOf(rexpo));
            }
            if(String.valueOf(rexpo).length()==2)
            {
                Cifrado.add("00"+String.valueOf(rexpo));
            }
            if(String.valueOf(rexpo).length()==3)
            {
                Cifrado.add("0"+String.valueOf(rexpo));
            }
            if(String.valueOf(rexpo).length()==4)
            {
                Cifrado.add(String.valueOf(rexpo));
            }
            inicioC=finalC;
            finalC=finalC+4;
            i=inicioC;
        }
        //Guardando todo en una sola cadena
        String cadena="";
        for(int i=0;i < Cifrado.size();i++)
        {
            cadena=cadena+Cifrado.get(i);
        }
        System.out.println("A MI TIENEN QUE DESCIFRARME: "+cadena);
        RecibirCifrado(cadena);//SALVANDO C , QUE SERA USADO PARA DESENCRIPTAR
        return cadena; 
    }
    public String Descifrar()
    {
        Exponenciacion expo= new Exponenciacion();
        ArrayList < String >  Descifrado = new ArrayList <  > ();
        int inicioC=0,finalC=4,rexpo = 0;
        String auxiliar;
        System.out.println("SOY EL MENSAJE CIFRADO: "+cifrado);
        for(int i =0 ;i < cifrado.length();i++)
        {
            auxiliar=cifrado.substring(inicioC,finalC); 
            System.out.println("SOY UNA SUBCADENA DEL MENSAJE CIFRADO ANTES DE SER DESCIFRADO: "+auxiliar);
            //Realizando operacion de encriptado
            rexpo=expo.CalcularExp(Integer.parseInt(auxiliar),(int)d,(int)n);
            System.out.println("ME DESCIFRARON: "+rexpo);
            //ALMACENANDO
            if(String.valueOf(rexpo).length()==1)
            {
                Descifrado.add("000"+String.valueOf(rexpo));
            }
            if(String.valueOf(rexpo).length()==2)
            {
                Descifrado.add("00"+String.valueOf(rexpo));
            }
            if(String.valueOf(rexpo).length()==3)
            {
                Descifrado.add("0"+String.valueOf(rexpo));
            }
            if(String.valueOf(rexpo).length()==4)
            {
                Descifrado.add(String.valueOf(rexpo));
            }
            inicioC=finalC;
            finalC=finalC+4;
            i=inicioC;
        }
        //Guardando todo en una sola cadena
        String cadena="";
        for(int i=0;i < Descifrado.size();i++)
        {
            cadena=cadena+Descifrado.get(i);
        }
        return cadena; 
    }
    public String OperacionRSAEncriptar()
    {
        //Generando llaves - ESTE PROCESO SE REALIZA EN EL METODO CONSTRUCTOR , AQUI SOLO LO INDICAMOS
        //Eliminando espacios y caracteres especiales
        MensajeLimpio=EliminarEspaciosCaracteresEspeciales();
        //Realizando conversion de texto a numeros
        System.out.println("SOY EL MENSAJE LIMPIO: "+MensajeLimpio);
        num_letra=ConvertirNumeros(MensajeLimpio);
        System.out.println("CADENA ANTERIOR PERO EN NUMEROS: "+num_letra);
        //Cifrando
        String cadena;
        cadena=Cifrar(num_letra);
        System.out.println("Soy el cifrado"+this.cifrado);
        //Realizando conversion de numeros a letras
        String TextoFinal;
        TextoFinal=ConvertirCadena(cadena);
        return TextoFinal;
    }
    public String OperacionRSADesencriptar()
    {
        CadenaDescifradaNumeros=Descifrar();
        String TextoFinal;
        TextoFinal=ConvertirCadena(CadenaDescifradaNumeros);
        return TextoFinal;
    }
}

RESULTADOS:



domingo, 9 de agosto de 2015

ALGORITMOS DE COLORACIÓN DE GRAFOS

Existen problemas muy complicados para los que:
  1. No sabemos cómo encontrar su solución óptima, o bien.
  2. 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:
  1. Proporcionan soluciones más o menos próximas a la óptima, en un tiempo de ejecución polinómico.
  2. Permiten resolver ejemplares del problema de tamaños que serían inabordables utilizando el algoritmo óptimo.
  3. 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.
  1. Utilizando el mínimo número de colores posible.
  2. 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:
  1. Algoritmo Secuencial o Voraz
  2. Algoritmo de coloración Welsh- Powell
  3. 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.

  1. Ingresamos el número de nodos y las aristas, se llenan los datos y creamos la  matriz de adyacencias.
  2. (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.
  3. Se toma el siguiente vértice y se colorea o etiqueta con en el menor número admisible; es decir, se verifican adyacencias.
  4. Se repite el paso (3) hasta que todos los vértices hayan sido coloreados.
  5. 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:
  1. 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.
  2. Se toma el siguiente vértice y se colorea o etiqueta  con en el menor número admisible; es decir, se  verifican adyacencias.
  3. Se repite el paso (2) hasta que todos los vértices hayan sido coloreados.
  4. 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:
  1. 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.
  2. Se toma el siguiente vértice y se colorea o etiqueta con en el menor número admisible; es  decir, se verifican adyacencias.
  3. Se repite el paso (2) hasta que todos los vértices  hayan sido coloreados.
  4. 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");
}