Grafos

GRAFOS |
|
Bipartitos Y Coloreado De Grafos |
LISETH PAOLA HERRERA GILDocente: Carlos Alberto OcampoMatemáticas Discretas |
Ingeniería de Sistemas |
|
|
28/09/2012 |

GRAFOS BIPARTITOS
Un grafo Bipartito se denomina en teoría de grafos a un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen vértices de un conjunto con vérticesde otro:
V1 ∪ V2 = V
V1 ∩ V2 = ∅
De tal manera que toda arista ∈ E conecta un vértice de V1 con un vértice de V2. Esto significa que el subgrafo completo generado por por V1 es libre de lados; asimismo el subgrafo completo generado por V2.

Siendo V el conjunto que contiene todos los vértices del grafo.

Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores:si pintamos los vértices en U de azul y los vértices de V de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.
Un grafo bipartito suele con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los dossubconjuntos tiene la misma cantidad de elementos, decimos que el grafo bipartito G es Balanceado.

Todo grafo sin ciclos con cantidad de nodos impar es bipartito. Como consecuencia de esto:
* Todo árbol es bipartito.
* Los grafos cíclicos con un número par de vértices son bipartitos.
* Todo grafo planar donde todas las caras tienen un número par de aristas es bipartito.
El conjuntode todos los grafos bipartitos es denominado ; en particular, un grafo bipartito uniendo dos conjuntos, de m y n elementos, respectivamente, se denota por o simplemente, Km,n.
Un grafo bipartito en el cual todos los elementos de V1 están unidos con todos los elementos de V2 se denomina bipartito completo.
Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) devértices y las aristas uniendo vértices de columnas (o filas) diferentes.

COLOREADO DE GRAFOS

Tenemos un grafo G y un conjunto de colores C = {a, b, . . . }.Una coloración de G con los colores de C es una asignación a los vértices de G de elementos de C (" colores") de manera que los extremos de cada arista reciban colores distintos. Formalmente, una coloración de G con colores de C es unaaplicación
γ :V (G) → C
tal que si {v, w} ∈ E(G) entonces γ(v) ≠ γ(w). El valor de γ(v) es el color que recibe el vértice v en la coloración. Coloración es la acción de colorear.
El número cromático de un grafo G, χ(G), es el número mínimo de colores necesario para colorear G.
Algunas observaciones inmediatas sobre el número cromático son las siguientes:
1. Para todo grafo G, χ(G) ≤ |V | , porquesiempre podremos colorear con |V | colores, asignando a cada vértice un color distinto. Ésta es, obviamente, la forma menos efectiva de colorear.
2. Si el grafo contiene al menos una arista, necesitaremos dos colores como mínimo; es decir, si |A| ≥ 1, entonces χ(G) ≥ 2.
3. Si G contiene a G′ como subgrafo, entonces χ(G) ≥ χ(G′)
4. Si G tiene k componentes conexas, G1, G2, . . . , Gk que tienennúmeros cromáticos χ(G1), χ(G2), . . . , χ(Gk) respectivamente, entonces

5. Si G y G′ son isomorfos, entonces χ(G) = χ(G”).
Por ejemplo, si tenemos el grafo G que representamos más abajo, y disponemos de la paleta de colores S = {a, b, c, d, e, f}, la asignación de colores de la izquierda es una coloración, pero no lo es la de la derecha, pues hay una arista con el mismo color e en sus dosvértices.

El concepto de coloración es invariante por isomorfismo. Es decir, si tenemos dos grafos isomorfos y una coloración del primero, tendremos una coloración del segundo con el siguiente (obvio) procedimiento: a cada vértice del segundo grafo le asignamos el color que lleva e vértice del primer grafo que le corresponde por el isomorfismo.
La cromático terminología que vamos a emplear en...