El algoritmo de Prim

A Elmer Coyla Idme, docente de la

Universidad Nacional del Altiplano de Puno

por brindarnos su enseñanza en este año académico

PRESENTACION

La utilidad académica de una monografía nunca está de más, el uso de esta es una gran ayuda para estudiantes en este caso universitarios es por eso que con esta recopilación de fuentes científicas impresas mas las conclusiones llegadas al tomar opinión de varios profesionales del área hacen de esta monografía consistente en "el algoritmo de Prim" una fuente de información más para fines académicos.

En estos tiempos el estudiantado opta por recurrir a fuentes sin sustento científico como el internet o simplemente dar por hecho algún comentario sin sustentación, ya sea con fines de curiosidad o estudiantes trabajando en algún proyecto. El uso de los libros se está perdiendo y con ello los libros mismos.

En esta monografía tocaremos el tema principal que es "El Algoritmo de Prim", dando a conocer y a repasar algunos puntos importantes en el área, como son los grafos, los arboles, y los diferentes tipos de términos que se usan en la teoría de grafos, también veremos cómo influye tal algoritmo en la vida cotidiana y cuan útil nos es…

INTRODUCCION

El hombre siempre ha tenido la necesidad de recorrer muchos lugares, utilizando caminos estratégicos y cortos buscando hallar la ruta optima con el mayor ahorro de tiempo, energía, distancia, etc. recorriendo todos los puntos designados.

En la actualidad podemos apreciar muchas cosas que nos pueden parecer de lo más habitual, caminos, líneas de comunicación telefónica, televisión por cable, el transporte ferroviario, líneas aéreas, circuitos eléctricos de nuestras casas, automóviles, etc. ; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.

En esta monografía se explicara el Algoritmo de Prim, buscando aplicarlo en problemas reales y cotidianos, utilizando en general la Teoría de Grafos.

RESUMEN

Un grafo o grafica es un conjunto finito de nodos o vértices conectados a través de aristas, los cuales pueden ser conexos, es decir existe algún enlace con cada nodo a través de algún camino formando así un grafo entero; O los grafos no conexos, que tienen la particularidad de que un segmento de grafo no este enlazado a través de algún vértice al grafo principal. En la teoría de grafos existen grafos dirigidos y grafos no dirigidos , lo grafos dirigidos son aquellos donde sus aristas tienen un sentido , quiere decir que tienen un principio especifico en algún nodo y un destino en algún otro a diferencia de los no dirigidos que son solo grafos simples (puede tomar ambas direcciones).

Arboles, un árbol es un grafo que no contiene ciclos y que conecta todos los nodos utilizando el menor número de aristas posibles.

Árbol recubridor mínimo, dentro de un grafo se tiene que cubrir todos los nodos formando un árbol (sub grafo) y utilizando el menor coste posible (menor costo, tiempo, distancia, precio, etc.)

El algoritmo de Prim es un algoritmo de la teoría de grafos que encuentra un árbol de expansión mínima para un grafo ponderado conexo. Esto significa que se encuentra un subconjunto de las aristas que forma un árbol que incluye todos los nodos, donde el total peso de todas las aristas en el árbol se reduce al mínimo.  Si el gráfico no está conectado, entonces sólo se encuentra un mínimo  árbol de expansión para uno de los componentes conectados

ABSTRACT A graph or chart is a finite set of nodes or vertices connected by edges, which can be related, ie there is a link to each node through some path thus forming a whole graph, or graphs are not related to are unique in that a segment of the graph is not bound by a vertex to the main graph. In graph theory there are directed graphs and undirected graphs, the directed graphs are where its edges have a sense, means they have a specific principle in a node and a destination unlike any other non-target are only simple graphs (can take both directions.)  Trees, a tree is a graph that contains no cycles and connecting all the nodes using the fewest possible edges.

Minimum spanning tree within a graph has to cover all the nodes forming a tree (sub graph) and using the lowest possible cost (less cost, time, distance, price, etc) Prim's algorithm is an algorithm of graph theory that finds a minimum spanning tree related to a weighted graph. This means that there is a subset of edges forms a tree with all nodes, where the total weight of all edges in the tree is minimized. If the graph is not connected, then it is only a minimum spanning tree for a connected component

PROLOGO

Mediante esta monografía tenemos como objetivo principal que los lectores cuenten en forma integra con los alcances más relevantes del Algoritmo de Prim considerando la teoría de grafos teniendo en cuenta que el estudio de los diferentes tipos de algoritmos cada vez tiene más importancia en la medida que avanza la era de las computadoras, caminos, líneas de comunicación telefónica, televisión por cable, el transporte ferroviario, líneas aéreas, circuitos eléctricos de nuestras casas, automóviles Y que se puede resolver diferentes tipos de problemas utilizando dicho algoritmo. Teniendo la ventaja de ahorrar tiempo y costos al resolver un problema determinado.

El trabajo, ha sido elaborado siguiendo una metodología dinámica, propia del grupo, lo cual garantiza a nuestros lectores un ágil manejo y acceso a la información que desee consultar.

CAPITULO I

CONCEPTOS PREVIOS

• Grafos.

ELIAS MICHA (2003)[1], En su libro Matemáticas Discretas este autor:

"Un grafo es un conjunto no vacio de objetos llamados vértices y de un conjunto de parejas no ordenadas de vértices llamadas Aristas."

SEYMOUR LIPSCHUTZ – MARC LIPSON (2007)[2], En su libro Matemáticas Discretas Indica:

"Un grafo tiene un numero finito de vértices y de aristas."

BERNARD KOLMAN – ROBERT C. BUSBY – SHARON ROSS (1995)[3], En su libro Estructuras Matemáticas Discretas nos dice:

"Un grafo G consta de un conjunto V de objetos llamados vértices, un conjunto finito E de objetos llamados aristas y una función "y" que asigna a cada arista un subconjunto {v, w}, donde "v, w" son vértices (que podrían ser iguales)."

• Conectividad

ELIAS MICHA (2003), ""Un Grafo es conexo si consiste de una sola pieza. Es decir que los vértices están unidos a través de aristas."

SEYMOUR LIPSCHUTZ – MARC LIPSON (2007), "Un Grafo de conectividad consta de una secuencia alternada de vértices y aristas de la forma donde cada arista contiene a los vértices."

Por lo tanto concluimos que la conectividad de un grafo es el enlace que puede tener 2 nodos a travez de uno o más aristas.

• Grafos Dirigidos y no dirigidos.

JIRÍ MATOUŠEK, JAROSLAV NEŠETRIL(2008) [4]En su libro Invitation to Discrete Mathematics nos dice:

"Un grafo dirigido G es un par (V,E), donde E es un subconjunto del producto cartesiano VxV. A los pares ordenados(x,y) ? E se les llama ramas dirigidas. Decimos que una rama dirigida e=(x,y) tiene origen x y por final y, o también decimos que es una rama de x a y."

ROBERT SEDGEWICK (1992) [5]En su libro Algoritmos en C++ nos dice.

" Un grafo no dirigido, la conectividad simple proporciona los vértices que pueden ser alcanzados desde un vértice dado recorriendo los aristas del grafo."

• Arboles.

Es un grafo que no tiene ciclos y que conecta a todos los puntos,. En un grafo con n vértices, los árboles tienen exactamente n – 1 aristas, y hay nn-2 árboles posibles. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas.

• Árbol Recubridor Mínimo.

BERNARD KOLMAN – ROBERT C. BUSBY – SHARON ROSS (1995)[6], En su libro Estructuras Matemáticas Discretas para la computación señala:

"Dado un grafo conexo, 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 computando la suma de todos los pesos de las aristas del árbol en cuestión. 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 bosque recubridor mínimo."

CONCLUSION

Grafo. Es el conjunto de vértices y aristas, los cuales, se representa gráficamente como un conjunto de puntos llamados nodos y las aristas se representan por líneas o puentes que unen dichos nodos

La teoría de grafos sirve como un modelo matemático para estructuras en cualquier campo , pero una de las mas importante en las aéreas de ciencias de la computación .

Árbol. Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo acíclico y a su vez es conexo. Quiere deciry que conecta a todos los puntos,. En un grafo con n vértices, los árboles tienen exactamente n – 1 aristas, y hay nn-2 árboles posibles. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas.

CAPITULO II

ALGORITMO DE PRIM

ROSA GUEREQUETA GARCIA – ANTONIO VALLECILLO MORENO (2004)[7], En su libro Técnicas de Desarrollos de Algoritmos nos dice:

"El algoritmo de Prim es tal vez el algoritmo de MST (Arboles Generadores Mínimos) más sencillo de implementar y el mejor método para grafos densos. Este algoritmo puede encontrar el MST de cualquier grafo conexo pesado.

Sea V el conjunto de nodos de un grafo pesado no dirigido. El algoritmo de Prim comienza cuando se asigna a un conjunto U de nodos un nodo inicial Perteneciente a V, en el cual "crece" un árbol de expansión, arista por arista. En cada paso se localiza la arista más corta (u, v) que conecta a U con V-U, y después se agrega v, el vértice en V-U, a U. Este paso se repite hasta que V=U. El algoritmo de Prim es de O(N2), donde | V | = N.

El siguiente ejemplo ilustra el funcionamiento del algoritmo.

La secuencia de ilustraciones va de izquierda a derecha y de arriba hacia abajo. La primera imagen muestra el grafo pesado y las siguientes muestran el funcionamiento del algoritmo de Prim y como va cambiando el conjunto U durante la ejecución.

Figura 1

Agregar un nodo al MST es un cambio incremental, para implementar el algoritmo de Prim debemos enfocarnos en la naturaleza de ese cambio incremental. La clave está en notar que nuestro interés esta en la distancia más corta de cada vértice de U a V-U.

Al U agregar un nodo v al árbol, el único cambio posible para cada vértice w fuera del árbol es que agregar v coloca a w más cerca del árbol. Esto no es necesario verificar la distancia de w a todos los demás nodos del árbol, solo se necesita verificar si la adición de v al árbol necesita actualizar dicho mínimo. Esto se puede lograr agregando una estructura de datos simple para evitar repetir cálculos excesivos, y hacer que el algoritmo sea más rápido y más simple.

El siguiente ejemplo ilustra la metodología anterior, utilizando una pila de aristas P, en donde las aristas se van apilando en menor a mayor según el peso de la misma. La secuencia de ilustraciones va de izquierda a derecha.

Figura 2

Se comienza en el nodo 0 y se apilan las aristas adyacentes a este nodo, en orden decreciente. La arista mínima es la que está en el tope de la pila, así que se des apila y se agrega al MST.

Seguidamente se procede con el nodo 1 y se apilan sus aristas adyacentes, con la diferencia de que hay que verificar si dichas aristas representan un nuevo camino mínimo con respecto a las aristas que ya están introducidas en la pila. En este caso no se apila la arista 1-3 porque ya hay una arista que lleve a 3 con el mismo costo en la pila. Se toma 1-2 porque está en el tope y se procede con el nodo 2. Cuando se va a apilar la arista 2-3, se encuentra que ya hay un camino que lleve a 3 pero de mayor costo, así que se desopila 0-3 y luego se apila 2-3. Se agrega 2-3 al MST y termina el proceso, porque el conjunto de nodos en el MST es igual al conjunto de vértices del grafo original."

ALFREDO CAICEDO BARRERO, GRACIELA WAGNER DE GARCÍA, ROSA MARÍA MÉNDEZ PARRA (2010)[8], En su libro Introducción a la Teoría de Grafos dice:

"Supóngase N = {1, 2, 3,…,n}. El algoritmo de Prim comienza con un conjunto U inicializado con cualquier nodo, por ejemplo {1}. Luego se hace crecer un árbol generador, arco por arco. En cada paso se encuentra el arco más corto (u, v) que conecta a U y N – U y luego se adiciona v, el nodo en N – U, a U. Se repite este paso hasta que U = N

El algoritmo es resumido en los siguientes pasos:

Algoritmo de PRIM.

Paso 0. Iniciar el grafo T con un solo nodo i escogido al azar: N = {i}, A = 0, T = ({i},0)

Paso 1. Seleccionar el arco (i, j) cuya longitud es la menor entre todos aquellos arcos adyacentes a T. Adicionar este arco (i,j) a T y j al conjunto de nodos de T

Paso 2. Preguntar si T ya es un árbol que contiene todos los nodos de G y detenerse. En este caso contrario repetir el paso 1"

CONCLUSION

El algoritmo de PRIM es un método para poder hallar un árbol recubridor mínimo en un grafo aciclico conexo no dirigido que nos permita hallar en un grafo el coste mínimo para una serie de actividades.

CAPITULO III:

Aplicación del Algoritmo de Prim

Este algoritmo se usa normalmente para ahorrar recursos, su aplicación mas común es la implementación de cables de redes, de servidores, de postes de luz entre otros.

Es decir el Algoritmo de Prim sirve para poder hallar el "árbol recubridor mínimo", en un grafo conexo no dirigido.

Ejemplos

Aplicando el algoritmo de Prim en un problema de la vida real:

Situación: Implementación del cableado para el servicio de televisión por cable en ciertos puntos de un sector de la ciudad de Puno.

Problema: Ahorrar la mayor cantidad de cable (recursos) en los puntos estratégicos (torres de distribución) para llegar a todos los destinos deseados.

Datos: Distancia entre torres y casas es de 10 metros (cada casa)

Planteamiento: En el figura 3 se observa la ubicación de las torres de distribución y las viviendas

Figura 3

En la figura 4 transformamos el conjunto de torres y viviendas en un Grafo.

Figura 4

En la figura 5 Aplicamos el Algoritmo de Prim en el grafo para hallar el árbol recubrir mínimo o en otras palabras la ruta optima para ahorra la distancia del cableado.

Figura 5

BIBLIOGRAFÍA

• Alfredo Caicedo Barrero, Graciela Wagner De García, Rosa María Méndez Parra (2010) Introducción a la Teoría de Grafos (2da ED)

• Bernard Kolman – Robert c. Busby – Sharon Rross (1997) Estructura

Matematicas Discretas (2da ED). Francia.

• ELIAS MICHA (2003).Matematicas Discretas (2ta ED). Mexico.

• Jirí Matoušek,Jaroslav Nešetril(1998) Invitation to Discrete Mathematics (1ra ED) EE:UU.

• Rosa Guerequeta Garcia – Antonio Vallecillo Moreno (2004) Tecnicas de Desarrollos de Algoritmos (1ra ED)

• Robert Sedgewick (1992) Algoritmos en C++ (1ra ED) EE.UU

• Seymour Lipschutz – Marc Lipson (2007). Matematicas Discretas (3ra Ed)

Autor:

Alexander Flores Mamani 

[1] ELIAS MICHA (2003).Matematicas Discretas (2ta ED). Mexico. PAG. 22, 19

[2] Seymour Lipschutz – Marc Lipson (2007). Matematicas Discretas (3ra Ed) PAG 158, 159

[3] Bernard Kolman – Robert c. Busby – Sharon Rross (1997) Estructura Matematicas Discretas (2da ED). Francia. PAG. 198

[4] Jirí Matoušek,Jaroslav Nešetril(1998) Invitation to Discrete Mathematics (1ra ED) EE:UU. PAG. 124,

[5] Robert Sedgewick (1992) Algoritmos en C++ (1ra ED) EE.UU PAG 277

[6] Bernard Kolman – Robert C. Busby – Sharon Ross (1995) Estructuras de Matemáticas Discretas para la Computación (3ra ED) Pag 321

[7] Rosa Guerequeta García – Antonio Vallecillo Moreno (2004) Técnicas de Desarrollos de Algoritmos (1ra ED) Cap 4 Pag 10

[8] Alfredo Caicedo Barrero, Graciela Wagner De García, Rosa María Méndez Parra (2010) Introducción a la Teoría de Grafos (2da ED) Pág. 109