Grafos

3.PROBLEMAS DE PROCESAMIENTO DE GRAFOS
Los algoritmos que se tratan en este texto son fundamentales y son muy útiles enmuchas aplicaciones, pero solamente son una introducción al tema de algoritmosde grafos. Existe un gran variedad de problemas relacionados con grafos y una gran variedad de algoritmos para procesamiento de grafos, pero claramente no todo problema de grafos es sencillo deresolver y en muchas ocasiones tampoco es sencillo determinar que tan difícil puede ser resolverlo.

En [5]podemos encontrar un categorización de problemas de grafos de acuerdo al grado de dificultadpara resolverlos, a saber:
−
Fáciles: Un problema fácil de procesamiento de grafos es aquel que se puederesolver utilizando un programa eficiente y elegante. Frecuentemente su tiempo de ejecución eslineal en el peor caso, o limitado por un polinomio de bajo grado
en el número de nodos o el número de aristas.
−
Tratable: Un problema tratable de procesamiento de grafos es aquel para el que seconoce un algoritmo que garantiza que sus requerimientos en tiempo y espacio están limitados por una función polinomial en el tamaño del grafo
(número de nodos + número de aristas). Todo problemafácil es tratable, pero se hace la distinción debido a que el desarrollo de una solución eficiente para resolverlo es extremadamente difícil o imposible.
−
Intratable: Un problema intratable deprocesamiento de grafos es aquel para el que no se conoce algoritmo que garantice obtener un solución del problema en una cantidad razonable de tiempo

Desconocida: Existen problemas de procesamiento degrafos cuya dificultad es desconocida. No hay un algoritmo eficiente conocido para resolverlos.
−
Conectividad Simple:Consiste en estudiar si el grafo es conexo, es decir, si existe al menos un caminoentre cada par de vértices.
−
Detección de Ciclos: Consiste en estudiar la existencia de al menos un ciclo en el grafo
−
Camino Simple: Consiste en estudiar la existencia de un camino entre...