Dos algoritmos voraces

Sobre Prim Y Kruskal

(Para los chicos de UPN)

Evolución del Algoritmo de Kruskal

Siguiendo el desarrollo de la teoría de grafos es importante mencionar  un tema fundamental como lo es árboles. Se entiende por árbol (en esta parte de las matemáticas) a un grafo (no digrafo) conexo y  acíclico. Ahora bien, dentro de  estos conceptos encontramos a arboles generadores mínimos.

Para encontrar árboles generadores mínimos debemos mencionar a Prim y Kruskal, dos personajes que han contribuido con métodos de identificación (algoritmos) facilitando el reconocimiento de árboles generadores mínimos.

Los algoritmos tanto de Prim como de Kruskal (con bastante parecido) permiten la construcción de árboles generadores mínimos. Ambos actúan añadiendo aristas de peso mínimo de manera secuencial  al recorrido de tal manera que estos algoritmos (algoritmos voraces) permiten obtener soluciones óptimas de un problema dado. Si bien es cierto que ambos  son muy parecidos, en cuanto a la metodología, debemos establecer una diferencia bien pronunciada en cuanto a estos se refiere.

 En el algoritmo de Prim las aristas de peso mínimo deben ser incidentes con alguno de los vértices del árbol ya construido y no deben formar un ciclo con las ya añadidas; mientras que en el algoritmo de Kruskal las aristas de peso mínimo si bien es cierto no pueden formar un ciclo con las ya elegidas, pero no deben ser necesariamente incidentes con vértices del árbol. Estas serían fundamentalmente la diferencia más notable entre estos dos algoritmos. Cabe indicar también que al inicio en el algoritmo de Prim la arista asignada es la de peso mínimo; mientras que en el algoritmo de Kruskal se le asigna un grafo vacío.

Terminología para entender Teoría de Grafos

Terminología para entender Teoría de Grafos

(Para los chicos de UPN)

Chicos para entender teoría de grafos es  necesario conocer los conceptos básicos en relación al tema. Acá les dejo algunos conceptos (aparte de lo que tenemos en las separatas) muy interesantes, ojalá que les sirva para comprender acerca del  tema tratado.

·        Grafo ponderado.- Es aquel grafo cuyas aristas se les ha asignado un determinado peso o valor (número).

·        Problema del camino de longitud mínima.- El problema de determinar un camino en un grafo ponderado tal que la suma de los pesos de las aristas de dicho grafo sea mínima entre todos los caminos que conectan entre sí los vértices especificados.

·        Problema del viajante.- El problema que pide determinar el circuito de menor longitud total que visita cada vértice del grafo exactamente una  vez.

·        Homeomorfo.- Dos grafos dirigidos son homeomorfos si pueden obtenerse a partir de un mismo grafo por medio de una sucesión de subdivisiones elementales.

·        Bucle o lazo.- Un arista que conecta un vértice consigo mismo (en los pseudografos).

·        Grafo simple.- Es un grafo no dirigido sin bucles ni aristas múltiples.

·        Aristas múltiples.- Aristas distintas conectando a los mismos vértices.

·        Hoja.- Se denomina hoja a un vértice de grado uno.

·        Circuito.-Un camino que comienza y termina en el mismo vértice.

·        Árbol generador.- Llamado también recubridor, es aquel es subgrafo y contiene todos los vértices del grafo.

·        Altura de un árbol.-  Refiere al nivel máximo de los vértices de un árbol.

·        Algoritmo voraz.- Algoritmo que busca una solución óptima realizando la elección óptima en cada paso secuencial del mismo.

·        Algoritmo de Prim.- Procedimiento para construir un árbol generador mínimo en un grafo ponderado mediante la incorporación de las aristas de menor peso que sean incidentes con un vértice que ya esté en el árbol y que no forme un ciclo con las ya seleccionadas.

·        Algoritmo de Kruskal.- Procedimiento para construir un árbol generador mínimo en un grafo ponderado mediante la incorporación de las aristas de menor peso que no estén ya en el árbol en el momento en que se añaden y que no formen un ciclo con las ya seleccionadas

EL NUEVO PROTOCOLO DE INTERNET.

(comentario)

      Desde la aparición de Internet hasta nuestros días, los cambios que se han generado en torno a esta tecnología han sido, y seguirán siendo, consistentemente paralelos y se han desarrollado a velocidades exponenciales; de tal manera que los "aparatos" conectados a la red de redes se ha multiplicado a tal punto que los mecanismos de soporte de conexión están casi saturados, problema que ya se había previsto mucho antes. Ante esta situación Xerox diseñó la versión 6 de IP (IPV6) con la finalidad de abastecer de nuevas direcciones a los nuevos dispositivos que soliciten conexión.
      Como estaba planificado, para este año, nuestro país implementó la semana pasada  este protocolo que reemplazará de manera gradual al antiguo IPV4. Una de las grandes ventajas que ofrece el IPV6 es la capacidad casi ilimitada de direcciones, suficientes para abastecer en el futuro a todas los equipos que requieran de este servicio. Considerando ello podríamos afirmar que las rutas están garantizadas para el futuro de Internet que es un campo en expansión y más aún con el auge de nuevos dispositivos, como los móviles, que solicitan un "dni" para tener acceso y además  en un futuro no tan lejano la interacción del mundo físico y virtual se va a estrechar con el llamado Internet of things que es el futuro de Internet, según los especialistas.
      En conclusión lo que podríamos decir es bienvenido a tu nuevo hogar, bienvenido a IPV6.