3 Motivación

Grafos de forma intuitiva se encuentran por ejemplo en las siguientes situaciones:

• planos o mapas de carreteras o calles
• redes de flujos (datos, líquidos)
• redes de transportes urbanos
• conexiones químicas entre átomos de una molécula
• relaciones de vecinidad en un mapamundi
• relaciones de interferencia entre antenas en un sistema de comunicación inalámbrica
• los enlaces entre documentos en el Internet

Es decir, un grafo es el concepto abstracto detrás de la representación de relaciones (aristas) entre entidades (vértices).

Problemas que se quiere resolver:

• Dado un traje completo para vestirse con el fin de ir a una boda en Galicia en invierno, es decir, llueve, ¿En qué orden hay que ponerse las cosas?
• Dado un callejero, ¿Es posible realizar un paseo que recorra cada calle exactamente una vez?
• Dado un callejero, ¿Cuál es el recorrido más corto que debe usar un cartero si tiene que recorrer cada calle por lo menos una vez?
• Dado un callejero, ¿Cómo orientar las calles con sentido único, así que se siga podiendo ir de cada punto a cada punto?
• Dado una fiesta con igual número de chicas y chicos, ¿Cuáles son las condiciones para que sea posible organizar un baile de todos (en parejas chica-chico)?
• Dado una descripción de las interconexiones de un circuito electrónico, ¿Cómo posicionar los chips con sus interconexiones en una placa?
• Dado un conjunto de casas por proteger de fuego, ¿Dónde posicionar los bomberos disponibles para minimizar su radio de acción?