Teoria De Grafos
Páginas: 8 (1940 palabras)
Publicado: 7 de marzo de 2013
Indice
Inv. Algoritmos Geneticos
Subtemas: Algoritmos Básicos de Grafos
Pág.
Resumen Y Conceptos Básicos …………………………….. 3
Problemas de Procesamiento de Grafos………………….. 4
Recorrido de Grafos…………………………………………… 6
Cuerpo
Conclusión
Bibliografía
Glosario
RESUMEN
Losgrafos son solo abstracciones matemáticas, pero son útiles en la práctica porque nos ayudan a resolver numerosos problemas importantes. Estas notas describen algunos de los algoritmos y métodos más conocidos para resolver problemas de procesamiento degrafos, así como proponen alternativas para la representación de los mismos en elcomputador. Cada algoritmo o método está acompañado de figuras queilustran su funcionamiento y de una breve descripción teórica que incluye el estudio de la complejidad en tiempo del mismo. En adición se incluye la descripción de una taxonomía de clasificación de problemas de procesamiento de grafos, basada en el grado de dificultad de lo mismos.
Estas notas abarcan desde problemas simples como el de recorrido de grafos, hasta problemas más complejos como los deflujo en redes. Es recomendable que el lector tenga conocimientos básicos de estructuras de datos dinámicas y de teoría de grafos.
CONCEPTOS BÁSICOS
Un grafo es un conjunto de nodos unidos por un conjunto de líneas o flechas. Por lo general, los nodos son entes de procesamiento o estructuras que contienen algún tipo de información y las líneas o flechas son conexiones o relaciones entreestos entes. Si se utilizan flechas para conectar los nodos decimos que el grafo es dirigido(también llamado digrafo) porque las relaciones entre los nodos tienen una dirección. Encaso contrario el grafo es no dirigido. En cualquiera de los dos casos, bien sea que se utilicen líneas o flechas, a estas relaciones se les puede llamar simplemente aristas.
Frecuentemente las aristas también tienenalgún tipo de información asociada (distancia,costo, confiabilidad, etc.), en cuyo caso estamos en presencia de un grafo pesado.
Las secuencias de aristas forman caminos o ciclos. Un ciclo es un camino quetermina en el mismo nodo donde comenzó. Si el camino recorre todos los nodos del grafo es llamado tour. El número de aristas en un camino es la longitud del camino.
Se dice que un grafo esconexo si se puede llegar desde cualquier nodo hasta cualquier otro mediante un camino. De lo contrario no es conexo, pero puede dividirse encomponentes conexas, que son subconjuntos de nodos y aristas del grafo original que si son conexos. Un grafo conexo sin ciclos es llamado un árbol.
PROBLEMAS DE PROCESAMIENTO DE GRAFOS
Los algoritmos que se tratan en este texto son fundamentales yson muy útiles enmuchas aplicaciones, pero solamente son una introducción al tema de algoritmos de grafos.
Existe un gran variedad de problemas relacionados con grafos y una gran variedad dealgoritmos para procesamiento de grafos, pero claramente no todo problema de grafos es sencillo de resolver y en muchas ocasiones tampoco es sencillo determinar que tan difícilpuede ser resolverlo.
En[5] podemos encontrar un categorización de problemas de grafos de acuerdo al
Grado de dificultad para resolverlos, a saber:
- Fáciles: Un problema fácil de procesamiento de grafos es aquel que se puede resolver utilizando un programa eficiente y elegante. Frecuentemente su tiempo de ejecución es lineal en el peor caso, o limitado por un polinomio de bajo grado en el número de nodos o elnúmero de aristas.
Tratable: Un problema tratable de procesamiento de grafos es aquel para el que se conoce 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).
Intratable: Un problema intratable de procesamiento de grafos es aquel para el que no se conoce algoritmo que...
Inv. Algoritmos Geneticos
Subtemas: Algoritmos Básicos de Grafos
Pág.
Resumen Y Conceptos Básicos …………………………….. 3
Problemas de Procesamiento de Grafos………………….. 4
Recorrido de Grafos…………………………………………… 6
Cuerpo
Conclusión
Bibliografía
Glosario
RESUMEN
Losgrafos son solo abstracciones matemáticas, pero son útiles en la práctica porque nos ayudan a resolver numerosos problemas importantes. Estas notas describen algunos de los algoritmos y métodos más conocidos para resolver problemas de procesamiento degrafos, así como proponen alternativas para la representación de los mismos en elcomputador. Cada algoritmo o método está acompañado de figuras queilustran su funcionamiento y de una breve descripción teórica que incluye el estudio de la complejidad en tiempo del mismo. En adición se incluye la descripción de una taxonomía de clasificación de problemas de procesamiento de grafos, basada en el grado de dificultad de lo mismos.
Estas notas abarcan desde problemas simples como el de recorrido de grafos, hasta problemas más complejos como los deflujo en redes. Es recomendable que el lector tenga conocimientos básicos de estructuras de datos dinámicas y de teoría de grafos.
CONCEPTOS BÁSICOS
Un grafo es un conjunto de nodos unidos por un conjunto de líneas o flechas. Por lo general, los nodos son entes de procesamiento o estructuras que contienen algún tipo de información y las líneas o flechas son conexiones o relaciones entreestos entes. Si se utilizan flechas para conectar los nodos decimos que el grafo es dirigido(también llamado digrafo) porque las relaciones entre los nodos tienen una dirección. Encaso contrario el grafo es no dirigido. En cualquiera de los dos casos, bien sea que se utilicen líneas o flechas, a estas relaciones se les puede llamar simplemente aristas.
Frecuentemente las aristas también tienenalgún tipo de información asociada (distancia,costo, confiabilidad, etc.), en cuyo caso estamos en presencia de un grafo pesado.
Las secuencias de aristas forman caminos o ciclos. Un ciclo es un camino quetermina en el mismo nodo donde comenzó. Si el camino recorre todos los nodos del grafo es llamado tour. El número de aristas en un camino es la longitud del camino.
Se dice que un grafo esconexo si se puede llegar desde cualquier nodo hasta cualquier otro mediante un camino. De lo contrario no es conexo, pero puede dividirse encomponentes conexas, que son subconjuntos de nodos y aristas del grafo original que si son conexos. Un grafo conexo sin ciclos es llamado un árbol.
PROBLEMAS DE PROCESAMIENTO DE GRAFOS
Los algoritmos que se tratan en este texto son fundamentales yson muy útiles enmuchas aplicaciones, pero solamente son una introducción al tema de algoritmos de grafos.
Existe un gran variedad de problemas relacionados con grafos y una gran variedad dealgoritmos para procesamiento de grafos, pero claramente no todo problema de grafos es sencillo de resolver y en muchas ocasiones tampoco es sencillo determinar que tan difícilpuede ser resolverlo.
En[5] podemos encontrar un categorización de problemas de grafos de acuerdo al
Grado de dificultad para resolverlos, a saber:
- Fáciles: Un problema fácil de procesamiento de grafos es aquel que se puede resolver utilizando un programa eficiente y elegante. Frecuentemente su tiempo de ejecución es lineal en el peor caso, o limitado por un polinomio de bajo grado en el número de nodos o elnúmero de aristas.
Tratable: Un problema tratable de procesamiento de grafos es aquel para el que se conoce 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).
Intratable: Un problema intratable de procesamiento de grafos es aquel para el que no se conoce algoritmo que...
Leer documento completo
Regístrate para leer el documento completo.