## 3.4.2 PROBLEMAS SOBRE GRAFOS

Un grafo (o multigrafo), es una estructura muy importante utilizada en Informática y también en ciertos ramos de Matemáticas, como por ejemplo, en Investigación de Operaciones. Muchos problemas de difícil resolución, pueden ser expresados en forma de grafo y consecuentemente resuelto usando algoritmos de búsqueda y manipulación estándar.

Entre las múltiples aplicaciones que tienen estas estructuras podemos mencionar:

- Modelar diversas situaciones reales, tales como: sistemas de aeropuertos, flujo de tráfico, etc.
- Realizar planificaciones de actividades, tareas del computador, planificar operaciones en lenguaje de máquinas para minimizar tiempo de ejecución.

Simplemente, un grafo es una estructura de datos no lineal, que puede ser considerado como un conjunto de vértices (o nodos) y arcos que conectan esos vértices.

Matemáticamente tenemos G=(V, E). Si u y v son elementos de V, entonces un arco se puede representar por (u,v).

Los grafos también se pueden clasificar como:

- Grafo No Dirigido.
- Grafo Dirigido (o Digrafo).

En el primer caso, los arcos no tienen una dirección y, por lo tanto, (u,v) y (v,u) representan el mismo arco. En un Grafo No Dirigido, dos vértices se dicen adyacentes si existe un arco que une a esos dos vértices.

En el segundo caso, los arcos tienen una dirección definida, y así (u,v) y (v,u) entonces representan arcos diferentes. Un Grafo Dirigido (o digrafo) puede también ser fuertemente conectado si existe un camino desde cualquier vértice hacia otro cualquier vértice.

Ejemplo Coloreado de grafos y número cromático

Un coloreado de un grafo G = (V, E) es una correspondencia C : V → S, donde S es un conjunto finito (de "colores") tal que si vw ∈ E, entonces C(v) <>C(w); dicho de otro modo, no se asigna el mismo color a vértices adyacentes.
El número cromático de G, denotado por χ(G), es el menor número de colores que se necesitan para colorear G (es decir, el k más pequeño tal que exista un coloreado C para G y IC(V)I = k).

Problema: Coloreado de grafos
Se nos da un grafo no dirigido G = (V, E) para colorear.

Problema de optimización: Dado G, determinar χ(G) (y producir un coloreado óptimo, es decir, uno que sólo use χ(G) colores).

Problema de decisión: Dado G y un entero positivo k, ¿existe un coloreado de G que use cuando más k colores? (Si lo hay, decimos que G es k-coloreable.)

El problema de coloreado de grafos es una abstracción de ciertos tipos de problemas de calendarización. Por ejemplo, supóngase que los exámenes finales de una universidad se van a calendarizar durante una semana con tres horas de examen por día, para un total de 15 horarios.

Los exámenes de algunos cursos, digamos Cálculo y Física, se deben efectuar en horarios distintos porque muchos estudiantes están tomando ambos cursos. Sea V el conjunto de cursos, y sea E el conjunto de pares de cursos cuyos exámenes no se deben efectuar al mismo tiempo. Entonces, los exámenes se podrán calendarizar en los 15 horarios sin conflictos si y sólo si el grafo G = (V, E) se puede colorear con 15 colores.

No se conocen algoritmos de coloreo de grafos polinómicamente acotados para los que el cociente del número de colores empleados entre el número óptimo de colores esté acotado por una constante. De hecho, garantizar una cota constante pequeña para ese cociente es NP-difícil.

###