TAD de los grafos: Algoritmo de Prim

El algoritmo de Prim calcula 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 de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Prim funciona de la siguiente manera:

  • Inicializar un árbol con un único vértice, elegido arbitrariamente, del grafo.
  • Aumentar el árbol por un lado. Llamamos lado a la unión entre dos vértices: de las posibles uniones que pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar el lado de menor distancia y unirlo al árbol.
  • Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que prim g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Prim. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

entonces

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Algoritmo de Kruskal

El algoritmo de Kruskal calcula 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 de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Kruskal 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.

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que kruskal g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Kruskal. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

entonces

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Nodos conectados en un grafo

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que conectados g v1 v2 se verifica si los vértices v1 y v2 están conectados en el grafo g. Por ejemplo, si grafo1 es el grafo definido por

entonces,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Nodos aislados de un grafo

Dado un grafo dirigido G, diremos que un nodo está aislado si o bien de dicho nodo no sale ninguna arista o bien no llega al nodo ninguna arista. Por ejemplo, en el siguiente grafo

podemos ver que del nodo 1 salen 3 aristas pero no llega ninguna, por lo que lo consideramos aislado. Así mismo, a los nodos 2 y 4 llegan aristas pero no sale ninguna, por tanto también estarán aislados.

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que aislados g es la lista de nodos aislados del grafo g. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Coloreado correcto de un mapa

Un mapa se puede representar mediante un grafo donde los vértices son las regiones del mapa y hay una arista entre dos vértices si las correspondientes regiones son vecinas. Por ejemplo, el mapa siguiente

se pueden representar por

Para colorear el mapa se dispone de 4 colores definidos por

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que correcta ncs m se verifica si ncs es una coloración del mapa m tal que todos las regiones vecinas tienen colores distintos. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python