Teoría de Grafos
Teoría de Grafos
Teoría de Grafos
La figura muestra un mapa con 4 distritos A, B, C y D. Se trata de pintar cada distrito con
un color de forma que, dos regiones con un borde comn (que no sea un punto) tengan
distintos colores y queremos hacer esto usando un mnimo de colores.
1.- Encuentra una representacin en trminos de vrtices y aristas de un grafo a partir del
mapa dado.
Vrtices:
El resultado es un grafo plano no dirigido, en el que sus vrtices estn unidos por las
aristas de la siguiente manera:
G: {(A,B)(A,C)(A,D)(B,C)(B,D)(C,D)}
2.- Investiga un algoritmo que aplicado a grafos te permita ir coloreando los vrtices de tal
forma que no coincidan en color, con el color de los vrtices que estn unidos a ellos a
travs de aristas.
Colorear grafo
Paso inicial. Ordenamos los vrtices del grafo. (el resultado del algoritmo
depender del orden elegido). Esto es, disponemos los vrtices del grafo en una
lista (v1, v2, . . . , vn) .
3.- Explica el algoritmo de coloracin que hayas utilizado, en conjunto con la corrida a
mano de la coloracin del grafo, la cual representa al mapa dado en la actividad.
Aplicando el algoritmo voraz al problema del mapa, donde tenemos cuatro vrtices
(A,B,C,D), conectados por aristas entre todos y cada uno de ellos, tenemos:
Grafo:
Vrtices ordenados:
3) Ahora colorearemos el vrtice C, y ya que este est conectado tanto con el vrtice
A y el vrtice B, le asignamos otro color: color 3.
Los colores se verifican del primero al ltimo que se asign.
import java.io.*;
import java.util.*;
import java.util.LinkedList;
class Graph {
//Constructor.
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// Imprimir el resultado.
for (int u = 0; u < V; u++)
System.out.println("Vrtice " + u + " ---> Color "
+ result[u]);
}
// Mtodo principal.
public static void main(String args[])
{
Graph g1 = new Graph(4);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(0, 3);
g1.addEdge(1, 2);
g1.addEdge(1, 3);
g1.addEdge(2, 3);
System.out.println("Coloracin de grafo 1");
g1.greedyColoring();