Respuesta :
Respuesta: La "dotación cromática" se refiere a un concepto utilizado en teoría de grafos, que es una rama de las matemáticas discretas. En términos simples, la dotación cromática de un grafo es el menor número de colores distintos necesarios para colorear todos los vértices del grafo de manera que dos vértices adyacentes no compartan el mismo color.
### Explicación detallada:
1. **Grafo**: Un grafo está compuesto por vértices (nodos) y aristas (conexiones entre los vértices). En el contexto de la dotación cromática, nos enfocamos en colorear los vértices de un grafo.
2. **Coloreo de vértices**: Un coloreo de vértices asigna un color a cada vértice del grafo de manera que vértices adyacentes (conectados por una arista) no compartan el mismo color.
3. **Dotación cromática**: Es el número mínimo de colores que se necesitan para colorear todos los vértices del grafo cumpliendo la regla de que dos vértices adyacentes no tengan el mismo color.
### Ejemplo:
Consideremos el grafo simple mostrado a continuación:
```
A --- B
| |
C --- D
```
- Este grafo tiene 4 vértices y 4 aristas.
- Para colorear este grafo, necesitamos asegurarnos de que ningún par de vértices adyacentes comparta el mismo color.
La dotación cromática de este grafo es 2, porque podemos colorear los vértices con dos colores de la siguiente manera:
- Asignamos el color rojo a los vértices A y C.
- Asignamos el color azul a los vértices B y D.
Con este coloreo, ningún par de vértices adyacentes tiene el mismo color, cumpliendo así con la regla de la dotación cromática.
### Propiedades y aplicaciones:
- La dotación cromática es un concepto fundamental en la teoría de grafos y tiene aplicaciones en problemas prácticos como la asignación de frecuencias en telecomunicaciones, el horario de exámenes escolares, entre otros.
- Determinar la dotación cromática de un grafo es un problema NP-difícil, lo que significa que no hay un algoritmo eficiente conocido para resolverlo en todos los casos.
En resumen, la dotación cromática es el número mínimo de colores necesarios para colorear todos los vértices de un grafo de manera que ningún par de vértices adyacentes comparta el mismo color.