Grafos de Ejemplo

=====Grafos de testeo obligatorio=====

Los siguientes grafos muestran variabilidad en los coloreos de Greedy con los reordenamientos.

Observación obvia: Greedy con un orden dado es determinístico y OrdenNatural también. Asi que Greedy con OrdenNatural les debe dar igual que lo que se dice acá. Por otro lado, WelshPowell y los RMBCs no son determísticos según el proyecto (no especificamos cómo se ordenan vertices con el mismo grado o el mismo color) asi que les puede dar distinto.

Grafo relativamente chico, Deberia dar mas colores con WelshPowell que con otros reordenes.(esta construido para que WelshPowell ande particularmente mal)

queen10.Numero de vertices=100. Numero de lados=1470.
Greedy en OrdenNatural:16 colores
Greedy en WelshPowell:17 colores
100SwitchVertices lo baja a 14.
RMBCs lo bajan a 13 y luego a 12
X(G) es 10.

queen13.Numero de vertices=169. Numero de lados=3328
Greedy en OrdenNatural:21 colores
Greedy en WelshPowell:23 colores
100 SwitchVertices lo baja a 19 y con los RMBCs se lo puede bajar a 17. X(G)=13.

School1 de la pagina de DIMACS. Numero de vertices=385. Numero de lados=19095
Greedy en OrdenNatural:42 colores
Greedy en WelshPowell:34 colores
100 SwitchVertices lo baja a: 32
Con 426 RMBCs logro bajarlo a 14,pero incluso con 3000 RMBC no parece mejorar.

Grafo con una trampa chiquita para testear un error especifico.

Numero de vertices=1010. Numero de lados=60980
Greedy en OrdenNatural:42 colores
Greedy en WelshPowell:34 colores
Con SwitchVertices y RMBCS se lo puede bajar a 14 colores.
X(G) es mayor o igual que 11.

Numero de vertices=3779. Numero de lados=371357
reedy en OrdenNatural:77 colores
Greedy en WelshPowell:97 colores
Lo puedo bajar con SwitchVertices y RMBCs a 72 colores, pero X(G)=61.

Los siguientes grafos son completos. Deben obtener siempre esa cantidad de colores con Greedy en cualquier orden

K100: X(G)=100

K500: X(G)=500

K1000: X(G)=1000

Grafos grandes para testear velocidad y uso de memoria.

No es necesario que ustedes obtengan estos mismos tiempos pero si deben poder hacer OrdenNatural, WelshPowell, 100 SwitchVertices mas 1000 RMBCs diversos, con Greedy luego de cada orden, en 15 minutos para cada uno de ellos. (los tiempos que se detallan abajo son con 3000 RMBCs)

Numero de vertices=221651. Numero de lados=12528006
Greedy en OrdenNatural:600 colores
Greedy en WelshPowell:581 colores
100 SwitchVertices a partir de WP no logra bajar ese número.
3000 RMBCs lo baja a 523.
Tiempo total:6m4.944s

Numero de vertices=2210104. Numero de lados=8807410
Greedy en OrdenNatural:5 colores
Greedy en WelshPowell:2099 colores.
Con SwitchVertices a partir de OrdenNatural y algunos RMBCs se puede bajar el coloreo a 4 colores.
Tiempo total para 3102 Greedys: 6m15.192s

Numero de vertices=3080. Numero de lados=4303060
Greedy en OrdenNatural:339 colores
Greedy en WelshPowell:264 colores
100 SwitchVertices: 262
642 RMBCs lo disminuye a 112.
Tiempo total para 3102 Greedys:1m39.539s

Numero de vertices=23658. Numero de lados=5586907
Greedy en OrdenNatural:173 colores
Greedy en WelshPowell:239 colores
Luego de 100 SwitchVertices: 172
Luego de 33 RMBCs :167
y luego de un total de 3000 RMBCs eso es lo mejor.
tiempo total 2m41.231s

GRAFO BIPARTITO con 2135792 vertices y 2162836 lados.
Greedy en OrdenNatural:6 colores
Greedy en WelshPowell:5 colores
Switch Vertices mas RMBCs lo bajan a 4.
Tiempo total para 3102 Greedys:3m41.215s