13_Minimum_spanning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algoritmo Minimum Spanning\n",
    "##### por  Javier Vallejos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Descripción"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El algoritmo de árbol de expansión mínima (MST) no es un algoritmo de entrenamiento en el sentido convencional como los algoritmos de aprendizaje automático. En cambio, es un algoritmo computacional que se utiliza para resolver problemas específicos relacionados con la teoría de grafos y la optimización. Aquí hay más detalles sobre cómo funciona el algoritmo MST:\n",
    "\n",
    "**Objetivo:** El objetivo principal del algoritmo MST es encontrar el árbol de expansión mínimo dentro de un gráfico determinado. Un árbol de expansión es un subconjunto de aristas que conecta todos los nodos del gráfico sin formar ningún ciclo. El árbol de expansión mínimo es aquel que tiene la suma más pequeña posible de pesos de aristas entre todos los árboles de expansión del gráfico.\n",
    "\n",
    "**Algoritmo:** Hay dos algoritmos principales que se usan comúnmente para encontrar el árbol de expansión mínimo:\n",
    "\n",
    "1. **Algoritmo de Kruskal:** El algoritmo de Kruskal es un algoritmo codicioso que comienza con un conjunto vacío de aristas y agrega iterativamente las aristas con los pesos más pequeños al conjunto, al tiempo que garantiza que no se formen ciclos. Este proceso continúa hasta que todos los nodos están conectados y el conjunto de aristas resultante forma el árbol de expansión mínimo.\n",
    "\n",
    "2. **Algoritmo de Prim:** El algoritmo de Prim comienza con un nodo inicial y hace crecer el árbol de expansión mínimo un nodo a la vez. En cada paso, selecciona el borde con el peso más pequeño que conecta un nodo en el árbol existente con un nodo fuera del árbol. Este proceso continúa hasta que todos los nodos estén incluidos en el árbol, formando el árbol de expansión mínima.\n",
    "\n",
    "**Entrada:** La entrada al algoritmo MST suele ser un gráfico ponderado y no dirigido representado como un conjunto de nodos y aristas, donde cada arista tiene un peso o costo asociado. El algoritmo trabaja con este gráfico de entrada para identificar el árbol de expansión mínimo.\n",
    "\n",
    "**Salida:** La salida del algoritmo MST es el conjunto de aristas que forman el árbol de expansión mínimo, junto con el peso o costo total de este árbol. Estos bordes se pueden utilizar para construir el árbol de expansión mínimo real o para responder preguntas relacionadas con el diseño, la optimización o la agrupación de redes.\n",
    "\n",
    "**Aplicaciones:** El algoritmo MST tiene varias aplicaciones prácticas, que incluyen:\n",
    "\n",
    "- Diseño de redes: Encontrar la forma más rentable de conectar un conjunto de ubicaciones o nodos.\n",
    "- Análisis de conglomerados: Identificación de conglomerados o grupos dentro de los datos en función de la proximidad.\n",
    "- Segmentación de imágenes: dividir una imagen en regiones con propiedades similares.\n",
    "- Algoritmos de aproximación: Proporcionar soluciones eficientes a diversos problemas de optimización.\n",
    "\n",
    "En resumen, el algoritmo del árbol de expansión mínimo es un algoritmo fundamental de la teoría de grafos que se utiliza para encontrar el árbol de expansión mínimo en un gráfico ponderado y no dirigido. No es un algoritmo de entrenamiento para modelos de aprendizaje automático sino que sirve como herramienta para resolver problemas de optimización y conectividad."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Birtex y Referencias"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* @inproceedings{grygorash2006minimum,\n",
    "  title={Minimum spanning tree based clustering algorithms},\n",
    "  author={Grygorash, Oleksandr and Zhou, Yan and Jorgensen, Zach},\n",
    "  booktitle={2006 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'06)},\n",
    "  pages={73--81},\n",
    "  year={2006},\n",
    "  organization={IEEE}\n",
    "}\n",
    "* @article{paivinen2005clustering,\n",
    "  title={Clustering with a minimum spanning tree of scale-free-like structure},\n",
    "  author={P{\\\"a}ivinen, Niina},\n",
    "  journal={Pattern Recognition Letters},\n",
    "  volume={26},\n",
    "  number={7},\n",
    "  pages={921--930},\n",
    "  year={2005},\n",
    "  publisher={Elsevier}\n",
    "}\n",
    "* chatGPT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Tipo de Modelo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El algoritmo de árbol de expansión mínima (MST) no es un algoritmo de entrenamiento en el sentido convencional como los algoritmos de aprendizaje automático. En cambio, es un algoritmo computacional que se utiliza para resolver problemas específicos relacionados con la teoría de grafos y la optimización. Aquí hay más detalles sobre cómo funciona el algoritmo MST:\n",
    "\n",
    "**Objetivo:** El objetivo principal del algoritmo MST es encontrar el árbol de expansión mínimo dentro de un gráfico determinado. Un árbol de expansión es un subconjunto de aristas que conecta todos los nodos del gráfico sin formar ningún ciclo. El árbol de expansión mínimo es aquel que tiene la suma más pequeña posible de pesos de aristas entre todos los árboles de expansión del gráfico.\n",
    "\n",
    "**Algoritmo:** Hay dos algoritmos principales que se usan comúnmente para encontrar el árbol de expansión mínimo:\n",
    "\n",
    "1. **Algoritmo de Kruskal:** El algoritmo de Kruskal es un algoritmo codicioso que comienza con un conjunto vacío de aristas y agrega iterativamente las aristas con los pesos más pequeños al conjunto, al tiempo que garantiza que no se formen ciclos. Este proceso continúa hasta que todos los nodos están conectados y el conjunto de aristas resultante forma el árbol de expansión mínimo.\n",
    "\n",
    "2. **Algoritmo de Prim:** El algoritmo de Prim comienza con un nodo inicial y hace crecer el árbol de expansión mínimo un nodo a la vez. En cada paso, selecciona el borde con el peso más pequeño que conecta un nodo en el árbol existente con un nodo fuera del árbol. Este proceso continúa hasta que todos los nodos estén incluidos en el árbol, formando el árbol de expansión mínima.\n",
    "\n",
    "**Entrada:** La entrada al algoritmo MST suele ser un gráfico ponderado y no dirigido representado como un conjunto de nodos y aristas, donde cada arista tiene un peso o costo asociado. El algoritmo trabaja con este gráfico de entrada para identificar el árbol de expansión mínimo.\n",
    "\n",
    "**Salida:** La salida del algoritmo MST es el conjunto de aristas que forman el árbol de expansión mínimo, junto con el peso o costo total de este árbol. Estos bordes se pueden utilizar para construir el árbol de expansión mínimo real o para responder preguntas relacionadas con el diseño, la optimización o la agrupación de redes.\n",
    "\n",
    "**Aplicaciones:** El algoritmo MST tiene varias aplicaciones prácticas, que incluyen:\n",
    "\n",
    "- Diseño de redes: Encontrar la forma más rentable de conectar un conjunto de ubicaciones o nodos.\n",
    "- Análisis de conglomerados: Identificación de conglomerados o grupos dentro de los datos en función de la proximidad.\n",
    "- Segmentación de imágenes: dividir una imagen en regiones con propiedades similares.\n",
    "- Algoritmos de aproximación: Proporcionar soluciones eficientes a diversos problemas de optimización.\n",
    "\n",
    "En resumen, el algoritmo del árbol de expansión mínimo es un algoritmo fundamental de la teoría de grafos que se utiliza para encontrar el árbol de expansión mínimo en un gráfico ponderado y no dirigido. No es un algoritmo de entrenamiento para modelos de aprendizaje automático sino que sirve como herramienta para resolver problemas de optimización y conectividad."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Algoritmos de entrenamiento"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El algoritmo de árbol de expansión mínima (MST) no es un algoritmo de entrenamiento en el sentido convencional como los algoritmos de aprendizaje automático. En cambio, es un algoritmo computacional que se utiliza para resolver problemas específicos relacionados con la teoría de grafos y la optimización. Aquí hay más detalles sobre cómo funciona el algoritmo MST:\n",
    "\n",
    "**Objetivo:** El objetivo principal del algoritmo MST es encontrar el árbol de expansión mínimo dentro de un gráfico determinado. Un árbol de expansión es un subconjunto de aristas que conecta todos los nodos del gráfico sin formar ningún ciclo. El árbol de expansión mínimo es aquel que tiene la suma más pequeña posible de pesos de aristas entre todos los árboles de expansión del gráfico.\n",
    "\n",
    "**Algoritmo:** Hay dos algoritmos principales que se usan comúnmente para encontrar el árbol de expansión mínimo:\n",
    "\n",
    "1. **Algoritmo de Kruskal:** El algoritmo de Kruskal es un algoritmo codicioso que comienza con un conjunto vacío de aristas y agrega iterativamente las aristas con los pesos más pequeños al conjunto, al tiempo que garantiza que no se formen ciclos. Este proceso continúa hasta que todos los nodos están conectados y el conjunto de aristas resultante forma el árbol de expansión mínimo.\n",
    "\n",
    "2. **Algoritmo de Prim:** El algoritmo de Prim comienza con un nodo inicial y hace crecer el árbol de expansión mínimo un nodo a la vez. En cada paso, selecciona el borde con el peso más pequeño que conecta un nodo en el árbol existente con un nodo fuera del árbol. Este proceso continúa hasta que todos los nodos estén incluidos en el árbol, formando el árbol de expansión mínima.\n",
    "\n",
    "**Entrada:** La entrada al algoritmo MST suele ser un gráfico ponderado y no dirigido representado como un conjunto de nodos y aristas, donde cada arista tiene un peso o costo asociado. El algoritmo trabaja con este gráfico de entrada para identificar el árbol de expansión mínimo.\n",
    "\n",
    "**Salida:** La salida del algoritmo MST es el conjunto de aristas que forman el árbol de expansión mínimo, junto con el peso o costo total de este árbol. Estos bordes se pueden utilizar para construir el árbol de expansión mínimo real o para responder preguntas relacionadas con el diseño, la optimización o la agrupación de redes.\n",
    "\n",
    "**Aplicaciones:** El algoritmo MST tiene varias aplicaciones prácticas, que incluyen:\n",
    "\n",
    "- Diseño de redes: Encontrar la forma más rentable de conectar un conjunto de ubicaciones o nodos.\n",
    "- Análisis de conglomerados: Identificación de conglomerados o grupos dentro de los datos en función de la proximidad.\n",
    "- Segmentación de imágenes: dividir una imagen en regiones con propiedades similares.\n",
    "- Algoritmos de aproximación: Proporcionar soluciones eficientes a diversos problemas de optimización.\n",
    "\n",
    "En resumen, el algoritmo del árbol de expansión mínimo es un algoritmo fundamental de la teoría de grafos que se utiliza para encontrar el árbol de expansión mínimo en un gráfico ponderado y no dirigido. No es un algoritmo de entrenamiento para modelos de aprendizaje automático sino que sirve como herramienta para resolver problemas de optimización y conectividad."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. Supuestos y restricciones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El algoritmo de árbol de expansión mínima (MST) es una herramienta poderosa para resolver diversos problemas relacionados con el diseño, la agrupación y la optimización de redes. Sin embargo, opera bajo ciertos supuestos y restricciones:\n",
    "\n",
    "**1. Gráfico ponderado no dirigido:** El algoritmo MST supone que los datos de entrada se representan como un gráfico ponderado no dirigido. En este contexto:\n",
    "\n",
    "    - **Armas ponderadas:** El algoritmo supone que hay un peso numérico o costo asociado con cada arista en el gráfico. Estos pesos suelen representar distancias, similitudes o costos entre nodos.\n",
    "\n",
    "    - **No dirigido:** Los algoritmos MST funcionan con gráficos no dirigidos donde los bordes no tienen dirección. Es decir, si hay un borde que conecta el nodo A con el nodo B, implica que también hay un borde que conecta el nodo B con el nodo A.\n",
    "\n",
    "**2. Conectividad:** El algoritmo MST supone que el gráfico de entrada está conectado, lo que significa que hay una ruta entre cualquier par de nodos. Si el gráfico no está conectado, es posible que el algoritmo no produzca un árbol de expansión mínimo válido.\n",
    "\n",
    "**3. Pesos de borde únicos:** Los algoritmos MST pueden asumir que los pesos de borde son únicos. En otras palabras, no hay dos aristas que tengan el mismo peso. Esta suposición simplifica el algoritmo y garantiza que el árbol de expansión mínimo sea único.\n",
    "\n",
    "**4. Árbol de expansión mínimo único:** Los algoritmos MST encuentran un árbol de expansión mínimo único para un gráfico determinado. Si el gráfico tiene múltiples árboles de expansión mínima debido a vínculos en los pesos de los bordes, el algoritmo puede seleccionar uno arbitrariamente.\n",
    "\n",
    "**5. Datos discretos:** Los algoritmos MST se utilizan normalmente con puntos de datos discretos, como ubicaciones en un mapa o registros de datos. Es posible que no sean directamente aplicables a datos continuos o espacios de alta dimensión sin un procesamiento previo adecuado.\n",
    "\n",
    "**6. Información global:** Los algoritmos MST consideran información global sobre todo el gráfico. No se adaptan a cambios locales ni actualizaciones online de los datos, ya que son algoritmos por lotes.\n",
    "\n",
    "**7. Sin pesos de borde negativos:** Muchos algoritmos MST, como los de Kruskal y Prim, asumen que los pesos de borde no son negativos. Las ponderaciones de borde negativas pueden provocar problemas con estos algoritmos, ya que es posible que no se comporten como se esperaba en presencia de ponderaciones negativas.\n",
    "\n",
    "**8. Complejidad computacional:** Si bien los algoritmos MST son eficientes para gráficos de tamaño pequeño a moderado, pueden resultar computacionalmente costosos para gráficos grandes. La complejidad temporal suele ser O (E log V), donde E es el número de aristas y V es el número de nodos. Para gráficos muy grandes, es posible que se requieran aproximaciones o algoritmos alternativos.\n",
    "\n",
    "En resumen, los algoritmos MST son herramientas valiosas para encontrar árboles de expansión mínima en gráficos no dirigidos ponderados, pero tienen suposiciones y limitaciones específicas que deben considerarse al aplicarlos a problemas del mundo real. Estos supuestos se relacionan con la naturaleza de los datos, la estructura del gráfico y la unicidad de los pesos de los bordes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6. Ejemplo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Minimum Spanning Tree Edges:\n",
      "(1, 2, {'weight': 1})\n",
      "(1, 3, {'weight': 3})\n",
      "(2, 4, {'weight': 2})\n",
      "(3, 5, {'weight': 6})\n",
      "Total Weight of MST: 12\n"
     ]
    }
   ],
   "source": [
    "import networkx as nx\n",
    "\n",
    "# Create a graph\n",
    "G = nx.Graph()\n",
    "\n",
    "# Add nodes to the graph\n",
    "G.add_node(1)\n",
    "G.add_node(2)\n",
    "G.add_node(3)\n",
    "G.add_node(4)\n",
    "G.add_node(5)\n",
    "\n",
    "# Add weighted edges to the graph\n",
    "G.add_edge(1, 2, weight=1)\n",
    "G.add_edge(1, 3, weight=3)\n",
    "G.add_edge(2, 3, weight=4)\n",
    "G.add_edge(2, 4, weight=2)\n",
    "G.add_edge(3, 4, weight=5)\n",
    "G.add_edge(3, 5, weight=6)\n",
    "G.add_edge(4, 5, weight=7)\n",
    "\n",
    "# Find the Minimum Spanning Tree using Kruskal's algorithm\n",
    "mst = nx.minimum_spanning_tree(G)\n",
    "\n",
    "# Print the edges in the Minimum Spanning Tree\n",
    "print(\"Minimum Spanning Tree Edges:\")\n",
    "for edge in mst.edges(data=True):\n",
    "    print(edge)\n",
    "\n",
    "# Calculate the total weight of the Minimum Spanning Tree\n",
    "total_weight = sum(data['weight'] for _, _, data in mst.edges(data=True))\n",
    "print(f\"Total Weight of MST: {total_weight}\")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "machinel1",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.10"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}