INTRODUCCIÓN

Un grupo muy numeroso de problemas se puede plantear en algún tipo de grafo. Estos problemas pueden aplicarse tanto en la computación, así como en problemas de redes, mas y rutas, diagramas de flujo, representación de moléculas químicas, circuitos eléctricos, etc. El desarrollo de algoritmos eficientes para resolver muchos problemas de grafos ha tenido un impacto considerable sobre nuestra capacidad para resolver problemas reales en todos esos campos. No obstante, para muchos problemas de grafos importantes todavía no se conocen soluciones. En otros casos, no se sabe si las soluciones que actualmente se conocen son lo más eficientes que podrían ser o si se les podría hacer mejoras sustanciales.
Veremos entonces, primero conceptos básicos de grafos y luego nos ocuparemos de los métodos primordiales para recorrer grafos de manera eficiente. Resulta que muchos problemas naturales se pueden resolver con gran eficiencia —de hecho, en tiempo lineal— utilizando un recorrido de grafo como cimiento. En términos informales, podemos calificar a estos problemas de grafos como "fáciles"; no en el sentido de que fue fácil hallar o programar la solución, sino en el sentido de que, una vez programada, es posible resolver ejemplares del problema con gran eficiencia, y resulta práctico resolver ejemplares muy grandes del problema (grafos con millones de nodos, en algunos casos).
Para continuar con nuestra clasificación informal, la clase de problemas de grafos "de mediana dificultad" consiste en aquellos que se pueden resolver en tiempo polinómico, pero que requieren más trabajo que un recorrido elemental del grafo. Es decir, para cada problema "de mediana dificultad", se conoce un algoritmo que resuelve ejemplares de "tamaño" n en un tiempo acotado por arriba por algún polinomio fijo, como n^2, n^3 o n^d para alguna otra d fija. En las potentes computadoras modernas resulta práctico resolver ejemplares relativamente grandes de estos problemas (grafos con millares o decenas de millares de nodos).
Más arriba en la escala, tenemos los problemas de grafos "difíciles", para los cuales no se conoce ningún algoritmo de tiempo polinómico. En algunos casos, es imposible resolver problemas con grafos de 50 ó 100 nodos con ningún algoritmo conocido, aunque se ejecute durante más de un año. No obstante, lo que sabemos hasta ahora no nos permite descartar la posibilidad de que se halle algún algoritmo eficiente. Estos problemas representan la verdadera frontera de nuestros conocimientos.
Uno de los aspectos fascinantes de los problemas de grafos es que cambios muy pequeños en la manera de plantear un problema a menudo pueden colocarlo en cualquiera de las tres categorías: fácil, de mediana dificultad o difícil.