En la teoría de grafos, la coloración de vértices es una forma de etiquetar cada vértice individual de manera que no haya dos vértices adyacentes que tengan el mismo color. Pero necesitamos averiguar la cantidad de colores que necesitamos para satisfacer la condición dada. No es deseable tener una gran variedad de colores o etiquetas. Entonces, tenemos un algoritmo llamado algoritmo Welsh Powell que proporciona los colores mínimos que necesitamos. Este algoritmo también se utiliza para encontrar el número cromático de un gráfico. Este es un enfoque codicioso iterativo .
Número cromático : Un gráfico G que requiere K colores distintos para su coloración adecuada, y nada menos, se llama un gráfico K-cromático, y el número K se llama el número cromático del gráfico G.
El algoritmo Welsh Powell consta de los siguientes pasos:
- Encuentra el grado de cada vértice.
- Enumera los vértices en orden de grados descendentes.
- Colorea el primer vértice con el color 1.
- Muévase hacia abajo en la lista y coloree todos los vértices que no estén conectados al vértice coloreado, con el mismo color.
- Repita el paso 4 en todos los vértices sin color con un nuevo color, en orden descendente de grados hasta que todos los vértices estén coloreados.
Al comenzar con el grado más alto, nos aseguramos de que el vértice con el mayor número de conflictos pueda solucionarse lo antes posible.
| Vértice | La licenciatura |
|---|---|
| A | 2 |
| B | 2 |
| C | 1 |
| D | 4 |
| mi | 2 |
| F | 2 |
| GRAMO | 3 |
| H | 5 |
| yo | 3 |
| j | 3 |
| k | 5 |
Primero, ordene la lista en orden descendente de grados. En caso de empate, podemos elegir al azar cualquier forma de romperlo.
Entonces, el nuevo orden será: H, K, D, G, I, J, A, B, E, F, C
Ahora, siguiendo el algoritmo de coloración de gráficos de Welsh Powell,
H: colorea rojo
K: no colorea rojo, ya que se conecta a HD
D: colorea rojo
G: no colorea rojo, ya que se conecta a H
I: no colorea rojo , ya que se conecta a H
J – no colorea Rojo, ya que se conecta a H
A – no colorea Rojo, ya que se conecta a H
B – no colorea Rojo, ya que se conecta a D
E – colorea Rojo
F – no colorear rojo, ya que se conecta a E
C – no colorear rojo, ya que se conecta a D
Después de esto, el gráfico se verá como el siguiente.
Ignorando los vértices ya coloreados, nos queda : K, G, I, J, A, B, F, C
Podemos repetir el proceso con el segundo color Verde
K – color verde
G – no color verde, ya que se conecta con K
I – color verde
J – no color verde, ya que se conecta con I
A – color verde
B – no color verde, ya que se conecta con A
F – color verde
C – color verde
Nuevamente, ignorando los vértices coloreados, nos quedamos con G, J, B. Vamos a colorearlo con Azul.
G – color azul
J – color azul
B – color azul
La figura final se muestra a continuación. Ahora, podemos ver que usando el algoritmo de Welsh Powell podemos colorear los vértices con solo 3 tipos de colores ( el número cromático de este gráfico es 3 ), que es la solución óptima, ya que este gráfico contiene al menos un triángulo.
Publicación traducida automáticamente
Artículo escrito por ArnabBhattacharya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA