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

TAD de los grafos: Grafos conexos

Un grafo no dirigido G se dice conexo, si para cualquier par de vértices u y v en G, existe al menos una trayectoria (una sucesión de vértices adyacentes) de u a v.

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

tal que conexo g se verifica si el grafo g es conexo. 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: Recorrido en anchura

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

tal que recorridoEnAnchura i g es el recorrido en anchura del grafo g desde el vértice i. Por ejemplo, en 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: Recorrido en profundidad

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

tal que recorridoEnProfundidad i g es el recorrido en profundidad del grafo g desde el vértice i. Por ejemplo, en 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: Anchura de un grafo

En un grafo, la anchura de un nodo es el máximo de los absolutos de la diferencia entre el valor del nodo y los de sus adyacentes; y la anchura del grafo es la máxima anchura de sus nodos. Por ejemplo, en el grafo

su anchura es 4 y el nodo de máxima anchura es el 5.

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

tal que (anchuraG g) es la anchura del grafo g. Por ejemplo,

Comprobar experimentalmente que la anchura del grafo ciclo de orden n es n-1.

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: Recorridos en un grafo completo

Definir la función

tal que recorridos xs es la lista de todos los posibles por el grafo cuyo conjunto de vértices es xs y cada vértice se encuentra conectado con todos los otros y los recorridos pasan por todos los vértices una vez y terminan en el vértice inicial. 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: Grafos k-regulares

Un grafo k-regular es un grafo con todos sus vértices son de grado k.

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

tal que (regularidad g) es la regularidad de g. Por ejemplo,

Comprobar que el grafo completo de orden n es (n-1)-regular (para n de 1 a 20) y el grafo ciclo de orden n es 2-regular (para n de 3 a 20).

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: Grafos regulares

Un grafo regular es un grafo en el que todos sus vértices tienen el mismo grado.

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

tal que (regular g) se verifica si el grafo g es regular. Por ejemplo,

Comprobar que los grafos completos son regulares.

Soluciones

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


Soluciones en Haskell