Arboles Y Grafos

UNIVERSIDAD TECNOLOGICA DEL PERU-AREUIPA

FACULTAD: INGENIERIA

CARRERA: INGENIERIA DE SEGURIDAD INDUSTRIAL Y MINERA

TEMA: ALGORITMO MÁS CORTO DE DIJKSTRA Y ÁRBOLES RECUBRIDORES MINIMALES : LOS ALGORITMOS DE KRUSKAL Y PRIM.

INTEGRANTES:

KANA LIVANDRO ROYER

LLALLACACHI AYDE

CCAPA CAROLINA

CHUA LIZBETH

AULA: 9-B

TURNO : TARDE

AREQUIPA-PERÙ

2013-II

INTRODUCCION

Mediante el siguiente trabajo se busca dar a conocer algoritmo más corto de dijkstra y árboles recubridores minimales : los algoritmos de kruskal y prim. Mediante el siguiente el siguiente trabajo se incluirá problemas, ejercicios y definiciones del presente tema.

Los contenidos tienen como propósito motivar al estudiante de Ingeniería de seguridad, para que se familiarice con los métodos abstractos de razonamiento y de representación de la información a través del estudio de la matemática discreta.

Se busca suministrar los conocimientos de matemática discreta, que se han vuelto imprescindibles, hoy. Se tiene especialmente presente el uso práctico en las tareas de programación y materias de niveles superiores como el análisis de algoritmos y las estructuras de datos.

OBJETIVOS GENERALES:

Asimilar y comprender los algoritmos para realizar cálculos o para procesar información. La base para dar cualquier solución algorítmica a un problema y sea capaz de abstraer problemas del mundo real en forma discreta.

OBJETIVOS ESPECIFICOS:

Conocer algunos resultados básicos de la teoría elemental de números, manejar la aritmética modular y aplicar dichos resultados en los diferentes sistemas de numeración, cálculos con enteros muy grandes.

Saber los conceptos fundamentales de la teoría de grafos. Saber representar grafos en un ordenador usando matrices.

Reconocer los grafos que sean planos (mapas) y saber calcular la distancia mínima entre dos puntos de un grafo etiquetado (algoritmo de Dijkstra).

DESARROLLO DEL TEMA.

Árbol recubridor minimo

Es un grafo conexo y no dirigido, un árbol recubridor mínimo de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc.; y se usa para asignar un peso total al árbol recubridor mínimo obteniedo la suma de todos los pesos de las aristas del árbol. Un árbol recubridor mínimo o un árbol expandido mínimo es un árbol recubridor que pesa menos o igual que otros árboles recubridores. Todo grafo tiene un bósque recubridor mínimo.

EJEMPLO

Un ejemplo sería una compañía de cable trazando cable a una nueva vecindad. Si está limitada a trazar el cable por ciertos caminos, entonces se hará un grafo que represente los puntos conectados por esos caminos. Algunos de estos caminos podrán ser más caros que otros, por ser más largos. Estos caminos serían representados por las aristas con mayores pesos. Un árbol recubridor para este grafo sería un subconjunto de estos caminos que no tenga ciclos pero que mantenga conectadas todas las casas. Puede haber más de un árbol recubridor posible. El árbol recubridor mínimo será el de menos coste.

En el caso de un empate, porque podría haber más de un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso distinto existirá sólo un árbol recubridor mínimo. Si los pesos son positivos, el árbol recubridor mínimo es el subgrafo de menor costo posible conectando todos los vértices, ya que los subgrafos que contienen ciclos necesariamente tienen más peso total

ARBOLES RECUBRIDORES NOMINALES ALGORITMO DE KRUSTAL

El algoritmo de Kruskal es la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). El algoritmo de Kruskal es un ejemplo de algoritmo voraz.

Un ejemplo de árbol expandido mínimo. Cada punto representa un vértice, el cual puede ser un árbol por sí mismo. Se usa el Algoritmo para buscar las distancias más cortas (árbol expandido) que conectan todos los puntos o vértices

Ejemplos:

Este es el grafo original. Los números de las aristas indican su peso. Ninguna de las aristas está resaltada.

AD y CE son las aristas más cortas, con peso 5, y AD se ha elegido arbitrariamente, por tanto se resalta.

Sin embargo, ahora es CE la arista más pequeña que no forma ciclos, con peso 5, por lo que se resalta como segunda arista.

La siguiente arista, DF con peso 6, ha sido resaltada utilizando el mismo método.

La siguientes aristas más pequeñas son AB y BE, ambas con peso 7. AB se elige arbitrariamente, y se resalta. La arista BD se resalta en rojo, porque formaría un ciclo ABD si se hubiera elegido.

El proceso continúa marcando las aristas, BE con peso 7. Muchas otras aristas se marcan en rojo en este paso: BC (formaría el ciclo BCE), DE (formaría el ciclo DEBA), y FE (formaría el ciclo FEBAD).

Finalmente, el proceso termina

2.1 Funciona de la siguiente manera:

se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado

se crea un conjunto C que contenga a todas las aristas del grafo

mientras C es no vacío

eliminar una arista de peso mínimo de C

si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol

en caso contrario, se desecha la arista

Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.

Algoritmo más corto de djkstra

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más cortodado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de coste negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de coste negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

3.1 algoritmo

Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.

Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.

Sea a = x (tomamos a como nodo actual).

Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos nodos no marcados vi.

Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada, esto es:

si (Di > Da + d(a, vi)) entonces Di = Da + d(a, vi)

Marcamos como completo el nodo a.

Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.

Una vez terminado al algoritmo,

...