Numeros Cromaticos

NUMEROS CROMATICOS
Grafo G se define como un par (V, A), donde V es un conjunto no vacío cuyos elementos son denominados vértices o nodos y A es un subconjunto de pares no ordenados de vértices que reciben el nombre de aristas o arcos.
Si V = {v1, v2, ...,vn}, los elementos de A se representan de la forma {vi, vj} con i ≠ j . Dos vértices vi y vj se dicen adyacentes si {vi, vj}  A.
Larepresentación gráfica de un grafo se lleva a cabo asociando a cada vértice un punto del plano y a cada arista {vi, vj} una línea continua que une los puntos asociados a los vértices vi y vj. No existe ninguna restricción sobre la forma de las líneas que representan las aristas.
Una coloración propia de G ocurre cuando se asignan colores a los vértices de G de modo que si vi y vj  son adyacentes,entonces vi y vj tengan colores distintos asignados. El número mínimo de colores necesarios para una coloración propia de un grafo es lo que se conoce como número cromático del grafo.

Una forma fácil de determinar el número cromático de un grafo simple es analizando los autovalores asociados a su matriz de vecindades o matriz de adyacencia. Un grafo es simple si a lo sumo sólo una arista une dosvértices cualesquiera. Es decir, un grafo sin bucles ni aristas paralelas.
Si V = {v1, v2, ...,vn} es el conjunto de vértices, el grafo se puede describir mediante una matriz n × n, cuyas filas y columnas se hallan etiquetadas con los vértices y cuyos coeficientes serán: uno si A o cero en caso contrario. Como se puede observar, la matriz de adyacencia depende de la ordenación de los vértices. Noobstante, siempre será una matriz simétrica con diagonal principal nula.
A modo de ejemplo, se escribirá la matriz de adyacencia del grafo que se muestra en la siguiente figura.

La matriz de adyacencia del grafo mostrado es:

Como la matriz de adyacencia es simétrica, los autovalores asociados a la misma son siempre números reales. Por lo tanto, éstos pueden ser ordenados de mayor a menor.Sea 1el autovalor más grande y n, el autovalor más pequeño. Si x es el número cromático de un grafo simple, entonces se cumple:

Se determinará el número cromático del grafo de la Figura 2. Para ello, se deberán calcular los autovalores asociados a la matriz de adyacencia de este grafo. Por ejemplo, se podría utilizar Scilab para obtenerlos, con el comando spec.
Los autovalores de la matriz son:-2,6095952,  -1,9749714, -1,4179733,  -1, -0,6173948, -0,3889106,  0,3905697, 1,2850306, 2,1951342, 4,138111.
Aplicando la desigualdad (2) se obtiene:

Por lo tanto, el número cromático del grafo es x = 4. Esto significa que cuatro es el número mínimo necesario de colores distintos para colorear el grafo de la Figura 2 de manera tal que no hayan dos vértices consecutivos con el mismo color. Lacoloración se muestra en la figura siguiente:

RELACION MATEMATICA
Una relación , de los conjuntos  es un subconjunto del producto cartesiano

Una Relación binaria es una relación entre dos conjuntos.
El concepto de relación implica la idea de enumeración, de algunos de los elementos, de los conjuntos que forman tuplas.

Un caso particular es cuando todos los conjuntos de la relación soniguales:  en este caso se representa  como , pudiéndose decir que la relación pertenece a A a la n.

-------------------------------------------------
[editar]Tipos de relaciones
En las relaciones se diferencian los tipos según el número de conjuntos en el producto cartesiano, que es el número de términos de la relación:
Relación unaria: un solo conjunto 
Relación binaria: con dos conjuntos Relación ternaria: con tres conjuntos 
Relación cuaternaria: con cuatro conjuntos 
...
Relación n-aria: caso general con n conjuntos 

Arboles:
Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices.
Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos.
Un árbol con raíz, es un árbol que tiene un vértice particular...