El “Orden predeterminado” sigue el orden de los números que identifican a cada uno de los
vértices del grafo dibujado. De ahí su nombre, ya que el usuario no necesita determinar el
orden en el que se van a colorear los vértices.

Si ejecutamos la versión “Orden predeterminado” del algoritmo de Coloración Secuencial,
en modo paso a paso, veremos que primero se le dará color al vértice 1, luego al 2, y así
sucesivamente hasta el último vértice. Lo vemos con un ejemplo.
 

Inicialmente tenemos dibujado en ALGRAF el grafo Rueda W6, tal y como se muestra en
la siguiente figura:

Una vez escogido el modo “Paso a Paso”, vemos que cambian algunas cosas. Tal y como
se ve en la siguiente figura:
 

Además, la caja de texto informativa muestra el nombre del algoritmo que se está
procesando y el “Orden de Coloración”, es decir, el orden de vértices que se va a
seguir en la coloración:

En éste caso, puesto que la versión del algoritmo secuencial es la del
“Orden predeterminado”, el “Orden de Coloración” sigue la numeración de los
propios vértices.

Continuamos con el ejemplo pulsando el botón “Continuar”, y esto es lo que vemos:

La asignación se muestra tanto en el dibujo del grafo, cambiando el color del vértice:

Como en la caja de texto informativa:

En éste primer paso, vemos que el color asignado al “vértice 1” es el “color 1”. Que se
corresponde con el color rojo que tiene el “vértice 1” en el dibujo del grafo. De éste
modo podemos saber en todo momento la correspondencia unívoca que existe entre
número de color y el color visualizado en el dibujo del grafo.

En la caja de texto informativa, vemos que el “vértice 1” está en negrita. Esto quiere
decir que es el vértice al que se le acaba de asignar un color.
De éste modo, podemos visualizar fácilmente durante toda la ejecución “Paso a Paso”
cual es el último vértice colorado.
 

Si volvemos a pulsar el botón “Continuar”, veremos que se le asigna color al “vértice 2”,
tal y como se ve en la siguiente figura:
 

En éste caso, a diferencia del caso del “Orden predeterminado”, el orden que seguirá el
algoritmo secuencial será el que el usuario escoja.
Veamos como, con un ejemplo:

Partimos de nuevo del grafo W6 dibujado en ALGRAF.
Tras seleccionar el ítem “Orden definido por el usuario” vemos que la caja de texto
informativa nos muestra lo siguiente:

En éste momento, sólo los vértices son seleccionables. Al pasar el ratón por encima de
las aristas, éstas ya no se marcan. Solo se marcan los vértices. De éste modo se facilita
la selección de los vértices.

Ahora seleccionamos los vértices en el orden en que queramos que el algoritmo los
coloree luego.
Empezamos por ejemplo escogiendo el vértice número 5. Y esto es lo que vemos:

Como en la caja de texto informativa:

Así mismo, en la lista de vértices seleccionados de la caja de texto informativa, aparece
el nuevo vértice seleccionado.

De forma muy similar al algoritmo de coloración secuencial, al ejecutar éste algoritmo
en modo paso a paso, veremos que los vértices se van colorando uno a uno.

La principal diferencia está en el orden en que se van coloreando los vértices.
Éste algoritmo primero ordena los vértices. Del de mayor grado al de menor grado.
Luego, siguiendo este orden, se colorean todos los vértices, al igual que se hace con el
algoritmo de coloración secuencial.

Lo vemos con el siguiente ejemplo.
Partimos del siguiente grafo:

Tras seleccionar el ítem “Coloración de Welsh-Powell”, al igual que como ocurre con
el algoritmo de coloración secuencial versión “Orden predeterminado”, se nos pregunta,
lo primero, por el modo de ejecución.
Si se escoge “Completo” vemos directamente el resultado final.

En éste ejemplo escogemos el modo “Paso a Paso”. Esta es la información presentada
por la caja de texto informativa:

En ella vemos el nombre del algoritmo que se está procesando y también el orden de
coloración de los vértices. Ordenados del de mayor grado al de menor grado.

A continuación igual que como se hizo en el ejemplo del algoritmo de coloración
secuencial, pulsamos el botón “Continuar”.
Por cada pulsación vemos que un nuevo vértice ha sido colorado, siguiendo el orden
descrito inicialmente. Hasta que todos han sido colorados:

Esto es lo que muestra la caja de texto informativa en éste punto:

En ella se ven las asignaciones de color realizadas por el algoritmo de Welsh-Powell.

Cuando todos los vértices han sido colorados, pulsar el botón “Continuar” tiene el
mismo efecto que pulsar el botón “Fin”. Ver el resultado final del algoritmo:

De forma muy similar al algoritmo de coloración secuencial, al ejecutar éste algoritmo
en modo paso a paso, veremos que los vértices se van colorando uno a uno.

Al igual que como ocurre con el algoritmo de Welsh-Powell, la principal diferencia está
en el orden en que se van coloreando los vértices.
Éste algoritmo también ordena primero los vértices. Esta ordenación previa, es lo que lo
hace distinto a los anteriores.
Luego, siguiendo el orden obtenido, se colorean todos los vértices.

Lo vemos con el siguiente ejemplo, que parte del mismo grafo usado para el ejemplo
de Welsh-Powell:

Tras seleccionar el ítem “Coloración de Matula-Marble-Isaacson”, al igual que como
ocurre con el algoritmo de coloración secuencial versión “Orden predeterminado”, se
nos pregunta, lo primero, por el modo de ejecución.
Si se escoge “Completo” vemos directamente el resultado final.

Escogemos modo “Paso a Paso” para el ejemplo. Acto seguido, la caja de texto
informativa nos muestra el nombre del algoritmo que se está procesando, así como
su “Orden de Coloración”:

A continuación igual que como se hizo en el ejemplo del algoritmo de coloración
secuencial, pulsamos el botón “Continuar”.
Por cada pulsación vemos que un nuevo vértice ha sido colorado, siguiendo el orden
descrito inicialmente. Hasta que todos han sido colorados:

Esto es lo que muestra la caja de texto informativa en éste punto:

En ella se ven las asignaciones de color realizadas por el algoritmo de
Matula-Marble-Isaacson.
 

Cuando todos los vértices han sido colorados, pulsar el botón “Continuar” tiene
el mismo efecto que pulsar el botón “Fin”. Ver el resultado final del algoritmo:

Este algoritmo, aunque también colorea los vértices uno a uno al ejecutarse en modo paso
a paso, es distinto a los tres anteriores.

Los tres algoritmos anteriores, primero ordenaban los vértices y luego los coloreaban uno
a uno. Sin embargo, con éste algoritmo no se sabe cual es el Orden de Coloración de los
vértices antes de empezar a colorearlos.

El Orden de Coloración se va buscando sobre la marcha en cada paso, en función del
estado de coloración y del grado de cada vértice.
Para ello el algoritmo se fija tanto en el “grado” (d), como en el “grado de color” (dc) de
cada vértice en cada paso.

Lo vemos en el siguiente ejemplo, partiendo del grafo que se muestra en la siguiente figura:

Seleccionamos el ítem “Coloración de Brelaz”. Y como con todos los demás algoritmos
de coloración, se nos pregunta por el modo de ejecución. Para nuestro ejemplo,
escogemos modo “Paso a Paso”. Si se escoge “Completo” vemos directamente el
resultado final.

Seguidamente, la caja de texto informativa nos muestra el nombre del algoritmo que se
está procesando:

Y también vemos que aparecen tres columnas informativas justo encima de los tres botones
de control del modo “Paso a Paso”:

- La primera columna contiene el “número” de cada vértice (nº).
- La segunda columna contiene el “grado” de cada vértice (d).
- La tercera columna contiene el “grado de color” de cada vértice (dc).

A partir de éstas tres columnas, se sabe cual es el siguiente vértice que se va a colorear.
Para saberlo, primero se escogen los vértices con “grado de color” máximo. Si hay varios,
de entre ellos, se escogen entonces los que tengan “grado” máximo.
Si después de haber aplicado estas dos restricciones, sigue habiendo más de un vértice,
escogemos el que tenga menor “número”.

Apliquemos en el ejemplo éstas restricciones para saber cual es el vértice que se va a
colorear primero.
Inicialmente todos los vértices tienen “grado de color” cero. Luego todos tienen grado de
color máximo. Pasamos entonces a la siguiente restricción. El “grado” máximo es 5 y lo
tienen los vértices 2, 3 y 4. Pasamos a la siguiente restricción, y por tanto, nos quedamos
con el vértice 2.

Pulsamos el botón “Continuar”, y vemos que efectivamente el vértice 2 es el que se
colorea:

 

Vemos que los datos de la fila del vértice 2 dejan de estar “activos”. En el dibujo del grafo
se colorea el vértice 2.

Y la caja de texto informativa muestra la nueva asignación:

Volvemos a aplicar las restricciones con los datos “activos” de la tabla. Y vemos que el
siguiente vértice es el 3. Al pulsar el botón “Continuar” lo vemos:

Y así sucesivamente, hasta que todos los vértices han sido colorados:

Con ésta operación obtenemos el grafo complementario al que tenemos dibujado.

Lo vemos con el siguiente ejemplo. Inicialmente tenemos dibujado el grafo Rueda W6.
Seleccionamos la opción “Complementario” del menú “Operaciones” y este es el grafo
obtenido:

 
 
 

Con la Operación LineGraph obtenemos el grafo L(G), grafo “lineal de G”, siendo G
el que tenemos dibujado en el momento de llamar a la operación.

Lo vemos con el siguiente ejemplo. Inicialmente tenemos dibujado G, que es el grafo
Rueda W6. Seleccionamos la opción “Lineal” del menú “Operaciones” y éste es el
grafo L(W6) obtenido: