S08_EDNoLineales_Grafos.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "49993bb6",
   "metadata": {},
   "source": [
    "<h1 align=\"center\">Estructura de Datos y Algoritmos I</h1>\n",
    "<h1 align=\"center\">Estructuras de Datos No Lineales - Grafos</h1>\n",
    "<h1 align=\"center\">2024</h1>\n",
    "<h1 align=\"center\">MEDELLÍN - COLOMBIA </h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d4f8ebf",
   "metadata": {},
   "source": [
    "*** \n",
    "|[![Outlook](https://img.shields.io/badge/Microsoft_Outlook-0078D4?style=plastic&logo=microsoft-outlook&logoColor=white)](mailto:calvar52@eafit.edu.co)||[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/S08_EDNoLineales_Grafos.ipynb)\n",
    "|-:|:-|--:|\n",
    "|[![LinkedIn](https://img.shields.io/badge/linkedin-%230077B5.svg?style=plastic&logo=linkedin&logoColor=white)](https://www.linkedin.com/in/carlosalvarez5/)|[![@alvarezhenao](https://img.shields.io/twitter/url/https/twitter.com/alvarezhenao.svg?style=social&label=Follow%20%40alvarezhenao)](https://twitter.com/alvarezhenao)|[![@carlosalvarezh](https://img.shields.io/badge/github-%23121011.svg?style=plastic&logo=github&logoColor=white)](https://github.com/carlosalvarezh)|\n",
    "\n",
    "<table>\n",
    " <tr align=left><td><img align=left src=\"https://github.com/carlosalvarezh/Curso_CEC_EAFIT/blob/main/images/CCLogoColorPop1.gif?raw=true\" width=\"25\">\n",
    " <td>Text provided under a Creative Commons Attribution license, CC-BY. All code is made available under the FSF-approved MIT license.(c) Carlos Alberto Alvarez Henao</td>\n",
    "</table>\n",
    "\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43b9ef7e",
   "metadata": {},
   "source": [
    "# Estructuras de Datos No Lineales - Grafos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c868296",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/DataStuctureClassification1.PNG?raw=true\" width=\"350\" />\n",
    "</p>\n",
    "<p style=\"text-align: center;\">\n",
    "    <strong>Fuente:</strong> Elaboración propia.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21bb9f3f",
   "metadata": {},
   "source": [
    "## Introducción a los Grafos: Contexto Histórico y Estado del Arte"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f404cf2d",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos00.PNG?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "<p style=\"text-align: center;\">\n",
    "    <strong>Fuente:</strong> GoogleMaps.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e28fd3f0",
   "metadata": {},
   "source": [
    "### Orígenes Históricos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec3d78b3",
   "metadata": {},
   "source": [
    "La [teoría de grafos](https://en.wikipedia.org/wiki/Graph_theory), como estructura de datos y concepto matemático, tienen su origen en el siglo XVIII. El problema de [los 7 Puentes de Königsberg](https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg), presentado por [Leonhard Euler](https://en.wikipedia.org/wiki/Leonhard_Euler) en 1736, es a menudo considerado el nacimiento de la teoría de grafos. *Euler* se preguntaba si era posible caminar por la ciudad de *Königsberg* y cruzar sus siete puentes una vez y solo una vez. La solución de *Euler*, demostrando que no era posible, sentó las bases para la teoría de grafos.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos01.PNG?raw=true\" width=\"250\" />\n",
    "</p>\n",
    "<p style=\"text-align: center;\">\n",
    "    <strong>Fuente:</strong> Wikipedia.\n",
    "</p>\n",
    "\n",
    "Este problema llevó a la formulación de conceptos fundamentales en grafos, como vértices, aristas y la idea de conectar nodos de manera que se puedan formar estructuras más complejas. Desde entonces, la teoría de grafos ha evolucionado significativamente, integrándose en numerosas disciplinas como la matemática, la informática, la física, la sociología, y la biología.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos02.PNG?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "<p style=\"text-align: center;\">\n",
    "    <strong>Fuente:</strong> Wikipedia.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ec8388e",
   "metadata": {},
   "source": [
    "### Desarrollo y Avances Modernos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c64c382a",
   "metadata": {},
   "source": [
    "En el siglo XX, con el avance de la computación, los grafos ganaron una nueva dimensión de relevancia. El desarrollo de algoritmos para grafos, como el [algoritmo de Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) para el camino más corto, el [algoritmo de Kruskal y Prim](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm) para árboles de expansión mínima, y los [algoritmos de búsqueda en profundidad y en amplitud](https://en.wikipedia.org/wiki/Breadth-first_search), se convirtieron en áreas de estudio fundamentales en ciencias de la computación.\n",
    "\n",
    "El estado del arte actual en grafos abarca tanto su estudio teórico como aplicaciones prácticas. Con la aparición de grandes conjuntos de datos y la necesidad de analizar relaciones complejas (como las redes sociales), los grafos se han vuelto herramientas indispensables. Se han desarrollado estructuras y algoritmos más eficientes para manejar grafos de gran escala, como grafos dispersos y bases de datos de grafos. Además, la inteligencia artificial y el aprendizaje automático han encontrado en los grafos un medio para modelar y resolver problemas complejos de optimización y reconocimiento de patrones."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b963ebe",
   "metadata": {},
   "source": [
    "### Aplicaciones Actuales y Futuras"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0bbdceb",
   "metadata": {},
   "source": [
    "- **Redes Sociales y Análisis de Redes**: Los grafos son fundamentales para analizar las complejas interacciones sociales y de redes.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Biología Computacional**: Utilizados para modelar estructuras moleculares y redes genéticas.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Optimización de Rutas y Logística**: Aplicados en la planificación de rutas para la entrega de mercancías y en sistemas de navegación GPS.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Internet y Redes de Comunicación**: Fundamental en la estructura de la web y en el análisis de la red de internet.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Teoría de Grafos en Física y Química**: Para modelar átomos en moléculas y en la física de partículas.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Computación Cuántica**: Los grafos desempeñan un papel en el diseño y análisis de algoritmos cuánticos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71731102",
   "metadata": {},
   "source": [
    "### Árboles vs Grafos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e94b5096",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos14.jpg?raw=true\" width=\"350\" />\n",
    "</p>\n",
    "<p style=\"text-align: center;\">\n",
    "    <strong>Fuente:</strong> geeksforgeeks.org.\n",
    "</p>\n",
    "\n",
    "\n",
    "| **Característica**     | **Árboles**                                                               | **Grafos**                                                                   |\n",
    "|------------------------|---------------------------------------------------------------------------|------------------------------------------------------------------------------|\n",
    "| **Definición**         | Un tipo especial de grafo no dirigido y conectado sin ciclos.             | Colección de vértices y aristas que pueden formar estructuras con ciclos.   |\n",
    "| **Jerarquía**          | Estructura jerárquica con un nodo raíz y una relación padre-hijo clara.   | No tienen una jerarquía inherente; cualquier nodo puede estar conectado con cualquier otro. |\n",
    "| **Ciclos**             | No tienen ciclos. Cada dos nodos están conectados por exactamente un camino. | Pueden tener ciclos y múltiples caminos entre nodos.                        |\n",
    "| **Tipos de Conexión**  | Conexiones unidireccionales siguiendo la jerarquía padre-hijo.            | Conexiones pueden ser unidireccionales o bidireccionales (en grafos dirigidos y no dirigidos). |\n",
    "| **Tipos**              | Solo un tipo principal, con variantes (como árbol binario, AVL, etc.).    | Variados, incluyendo dirigidos, no dirigidos, ponderados, multigrafos, etc. |\n",
    "| **Relaciones**         | Relaciones lineales y unidireccionales.                                   | Relaciones más complejas y posiblemente bidireccionales.                    |\n",
    "| **Usos**               | Modelado de jerarquías y estructuras con una sola vía de acceso.          | Modelado de redes y estructuras con múltiples vías de interconexión.        |\n",
    "| **Ejemplos**           | Árboles de decisión, árboles genealógicos, árboles de sintaxis.           | Redes sociales, mapas, grafos de dependencias en software.                  |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fba0bc18",
   "metadata": {},
   "source": [
    "## Grafos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50e52b0b",
   "metadata": {},
   "source": [
    "### Definición"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf17bd87",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos04.PNG?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "<p style=\"text-align: center;\">\n",
    "    <strong>Fuente:</strong> geeksforgeeks.org.\n",
    "</p>\n",
    "\n",
    "Los grafos son una estructura de datos que consiste en una colección de nodos conectados por aristas (*edges*). Se utiliza para representar relaciones entre diferentes entidades. Los algoritmos de grafos son métodos utilizados para manipular y analizar grafos, resolviendo diversos problemas como encontrar el camino más corto o detectar ciclos.\n",
    "\n",
    "Un grafo $G$ se define matemáticamente como un par ordenado de dos conjuntos, $G = (V, E)$, donde:\n",
    "\n",
    "- $V$ representa el conjunto de vértices o nodos. Los vértices pueden ser cualquier cosa: personas en una red social, ciudades en un mapa, o estaciones en una red de transporte.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- $E$ es el conjunto de aristas o bordes, que representan las relaciones o conexiones entre los vértices. En el contexto de un mapa, por ejemplo, una arista podría representar una carretera que conecta dos ciudades.\n",
    "\n",
    "Esta definición básica se expande para abarcar varios tipos y propiedades:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6da5eb82",
   "metadata": {},
   "source": [
    "### Tipos de Grafos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c288e21",
   "metadata": {},
   "source": [
    "Por supuesto, aquí tienes las traducciones:\n",
    "\n",
    "- **Grafo Nulo:** Un grafo se conoce como grafo nulo si no hay aristas en el grafo.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos05.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo Trivial:** Grafo que tiene solo un vértice, es también el grafo más pequeño posible.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos06.PNG?raw=true\" width=\"70\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo No Dirigido:** Un grafo en el que las aristas no tienen dirección. Es decir, los nodos son pares no ordenados en la definición de cada arista.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos07.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo Dirigido:** Un grafo en el que cada arista tiene dirección. Es decir, los nodos son pares ordenados en la definición de cada arista.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos08.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo Conectado:** El grafo en el que desde un nodo se puede visitar cualquier otro nodo en el grafo se conoce como grafo conectado.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos07.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo Desconectado:** El grafo en el que al menos un nodo no es alcanzable desde un nodo se conoce como grafo desconectado.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos09.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo Regular:** El grafo en el que el grado de cada vértice es igual a K se llama grafo regular K.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos07.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo Completo:** El grafo en el que desde cada nodo hay una arista hacia cada otro nodo.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos10.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo de Ciclo:** El grafo en el que el grafo es un ciclo en sí mismo, el grado de cada vértice es 2.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos07.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo Cíclico:** Un grafo que contiene al menos un ciclo se conoce como grafo cíclico.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos11.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo Acíclico Dirigido:** Un Grafo Dirigido que no contiene ningún ciclo.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos12.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo Bipartito:** Un grafo en el que los vértices se pueden dividir en dos conjuntos de manera que los vértices en cada conjunto no contengan ninguna arista entre ellos.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos13.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "- **Grafo Ponderado:** Un grafo en el que las aristas ya están especificadas con un peso adecuado se conoce como grafo ponderado. Los grafos ponderados pueden clasificarse además en grafos ponderados dirigidos y grafos ponderados no dirigidos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f06b3a8",
   "metadata": {},
   "source": [
    "### Representación de grafos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "461a546f",
   "metadata": {},
   "source": [
    "Los grafos pueden representarse en una computadora de varias maneras, siendo las más comunes la **Matriz de Adyacencia** y la **Lista de Adyacencia**. Cada método tiene sus propias ventajas y desventajas, dependiendo del tipo de operaciones que se necesitan realizar y las características del grafo (como su densidad)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3a1d574",
   "metadata": {},
   "source": [
    "#### Matriz de Adyacencia"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98b98d12",
   "metadata": {},
   "source": [
    "Una matriz de adyacencia es una matriz cuadrada que se utiliza para representar un grafo de forma booleana (0's y 1's). Las filas y columnas de la matriz corresponden a los vértices del grafo. Si existe una arista entre dos vértices, el valor en la celda correspondiente se establece en `1` (o el peso de la arista, en el caso de grafos ponderados); de lo contrario, se establece en `0`.\n",
    "\n",
    "Supongamos que hay $n$ vértices en el grafo. Entonces, se crea una matriz 2D `adjMat[n][n]` con dimensiones $n \\times n$.\n",
    "\n",
    "- Si hay una arista del vértice $i$ al $j$, se marca `adjMat[i][j]` como `1`.  \n",
    "- Si no hay una arista del vértice $i$ al $j$, se marca `adjMat[i][j]` como `0`.\n",
    "\n",
    "**Ventajas**:\n",
    "- Representación simple y directa de la estructura del grafo.\n",
    "- Facilita operaciones como determinar si hay una arista entre dos vértices.\n",
    "\n",
    "**Desventajas**:\n",
    "- Ineficiente en términos de espacio para grafos dispersos (grafos con pocas aristas en relación con el número de vértices).\n",
    "- Puede llevar a un uso innecesario de memoria y tiempo de procesamiento.\n",
    "\n",
    "**Ejemplo**:\n",
    "Consideremos un grafo con 4 vértices como el de la figura.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos15.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "\n",
    "La matriz de adyacencia sería:\n",
    "\n",
    "|   | A | B | C | D |\n",
    "|---|---|---|---|---|\n",
    "| A | 0 | 1 | 1 | 0 |\n",
    "| B | 1 | 0 | 1 | 0 |\n",
    "| C | 1 | 1 | 0 | 1 |\n",
    "| D | 0 | 0 | 1 | 0 |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dac03bff",
   "metadata": {},
   "source": [
    "##### Representación de un Grafo No Dirigido a Matriz de Adyacencia:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2b73cc1",
   "metadata": {},
   "source": [
    "La siguiente figura muestra un grafo no dirigido. Inicialmente, toda la matriz se inicializa en `0`. Si hay una arista de la fuente al destino, insertamos `1` en ambos casos (`adjMat[fuente]` y `adjMat[destino]`) porque podemos ir en cualquier dirección.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos16.PNG?raw=true\" width=\"500\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2de91f7",
   "metadata": {},
   "source": [
    "#### **Código para generar la matriz de adyacencia de un grafo no dirigido**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ef83ee89",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Matriz de adyacencia:\n",
      "[0, 1, 1, 0]\n",
      "[1, 0, 1, 1]\n",
      "[1, 1, 0, 1]\n",
      "[0, 1, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "# Definir los nodos y las aristas\n",
    "nodos = ['A', 'B', 'C', 'D']\n",
    "aristas = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('C', 'D')]\n",
    "\n",
    "# Crear un diccionario para asignar a cada nodo un índice numérico\n",
    "indice_nodos = {nodo: idx for idx, nodo in enumerate(nodos)}\n",
    "\n",
    "# Inicializar la matriz de adyacencia de tamaño NxN (donde N es el número de nodos)\n",
    "N = len(nodos)\n",
    "matriz_adyacencia = [[0 for _ in range(N)] for _ in range(N)]\n",
    "\n",
    "# Rellenar la matriz de adyacencia basándose en las aristas\n",
    "for arista in aristas:\n",
    "    nodo1, nodo2 = arista\n",
    "    i, j = indice_nodos[nodo1], indice_nodos[nodo2]\n",
    "    matriz_adyacencia[i][j] = 1\n",
    "    matriz_adyacencia[j][i] = 1  # Como es un grafo no dirigido, la matriz es simétrica\n",
    "\n",
    "# Imprimir la matriz de adyacencia\n",
    "print(\"Matriz de adyacencia:\")\n",
    "for fila in matriz_adyacencia:\n",
    "    print(fila)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68cbe5ed",
   "metadata": {},
   "source": [
    "##### Representación de un Grafo Dirigido a Matriz de Adyacencia"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05d52afb",
   "metadata": {},
   "source": [
    "La figura de abajo muestra un grafo dirigido. Inicialmente, toda la matriz se inicializa en `0`. Si hay una arista de la fuente al destino, insertamos `1` para ese particular `adjMat[destino]`.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos17.PNG?raw=true\" width=\"500\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ee015e7",
   "metadata": {},
   "source": [
    "#### **Código para generar la matriz de adyacencia de un grafo dirigido**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "b9c91a0b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Matriz de adyacencia para el grafo dirigido:\n",
      "[0, 0, 0]\n",
      "[1, 0, 1]\n",
      "[1, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "# Definir los nodos y las aristas dirigidas\n",
    "nodos = [0,1, 2,]\n",
    "aristas = [(1, 2), (1, 0), (2, 0)]  # Aristas dirigidas\n",
    "\n",
    "# Crear un diccionario para asignar a cada nodo un índice numérico\n",
    "indice_nodos = {nodo: idx for idx, nodo in enumerate(nodos)}\n",
    "\n",
    "# Inicializar la matriz de adyacencia de tamaño NxN (donde N es el número de nodos)\n",
    "N = len(nodos)\n",
    "matriz_adyacencia = [[0 for _ in range(N)] for _ in range(N)]\n",
    "\n",
    "# Rellenar la matriz de adyacencia basándose en las aristas\n",
    "for arista in aristas:\n",
    "    nodo_origen, nodo_destino = arista\n",
    "    i, j = indice_nodos[nodo_origen], indice_nodos[nodo_destino]\n",
    "    matriz_adyacencia[i][j] = 1  # Sólo en la dirección del grafo\n",
    "\n",
    "# Imprimir la matriz de adyacencia\n",
    "print(\"Matriz de adyacencia para el grafo dirigido:\")\n",
    "for fila in matriz_adyacencia:\n",
    "    print(fila)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b8d002c",
   "metadata": {},
   "source": [
    "#### Lista de Adyacencia"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa47e455",
   "metadata": {},
   "source": [
    "Una lista de adyacencia es una colección de listas o conjuntos, una para cada vértice en el grafo. Cada lista contiene los vértices adyacentes (es decir, directamente conectados) a ese vértice.\n",
    "\n",
    "El tamaño del arreglo es igual al número de vértices (es decir, $n$). Cada índice en este arreglo representa un vértice específico en el grafo. La entrada en el índice $i$ del arreglo contiene una lista enlazada con los vértices que son adyacentes al vértice $i$.\n",
    "\n",
    "Supongamos que hay $n$ vértices en el grafo. Entonces, creamos un arreglo de listas de tamaño $n$ como `adjList[n]`.\n",
    "\n",
    "- `adjList[0]` tendrá todos los nodos que están conectados (vecinos) al vértice `0`.\n",
    "- `adjList[1]` tendrá todos los nodos que están conectados (vecinos) al vértice `1`, y así sucesivamente.\n",
    "\n",
    "**Ventajas**:\n",
    "- Eficiente en términos de espacio para grafos dispersos.\n",
    "- Permite un acceso más rápido a los vecinos de un vértice.\n",
    "\n",
    "**Desventajas**:\n",
    "- Determinar si hay una arista entre dos vértices específicos puede ser menos eficiente que con la matriz de adyacencia.\n",
    "- La estructura de datos es ligeramente más compleja.\n",
    "\n",
    "**Ejemplo**:\n",
    "Usando el mismo grafo del ejemplo anterior, la lista de adyacencia sería:\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos15.PNG?raw=true\" width=\"150\" />\n",
    "</p>\n",
    "\n",
    "```pseudocode\n",
    "A --> [B, C]\n",
    "B --> [A, C]\n",
    "C --> [A, B, D]\n",
    "D --> [C]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a82bd30",
   "metadata": {},
   "source": [
    "##### Representación de un Grafo No Dirigido a Lista de Adyacencia"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34409466",
   "metadata": {},
   "source": [
    "El grafo no dirigido de la figura tiene $3$ vértices. Por lo tanto, se crea un arreglo de listas de tamaño $3$, donde cada índice representa los vértices. Ahora, el vértice `0` tiene dos vecinos (es decir, `1` y `2`). Entonces, insertamos los vértices `1` y `2` en el índice `0` del arreglo. De manera similar, para el vértice `1`, tiene dos vecinos (es decir, `2` y `0`). Por lo tanto, insertamos los vértices `2` y `0` en el índice `1` del arreglo. De manera similar, para el vértice `2`, insertamos sus vecinos en el arreglo de listas.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos18.PNG?raw=true\" width=\"500\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21472999",
   "metadata": {},
   "source": [
    "#### **Código para generar la lista de adyacencia de un grafo no dirigido**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7a2c4b27",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Lista de adyacencia para el grafo no dirigido:\n",
      "1: [2, 0]\n",
      "2: [1, 0]\n",
      "0: [1, 2]\n"
     ]
    }
   ],
   "source": [
    "# Definir los nodos y las aristas no dirigidas\n",
    "nodos = [1, 2, 0]\n",
    "aristas = [(1, 2), (1, 0), (2, 0)]  # Aristas no dirigidas\n",
    "\n",
    "# Inicializar la lista de adyacencia\n",
    "lista_adyacencia = {nodo: [] for nodo in nodos}\n",
    "\n",
    "# Rellenar la lista de adyacencia para grafo no dirigido\n",
    "for arista in aristas:\n",
    "    nodo_origen, nodo_destino = arista\n",
    "    lista_adyacencia[nodo_origen].append(nodo_destino)\n",
    "    lista_adyacencia[nodo_destino].append(nodo_origen)  # Añadir también la arista en sentido inverso\n",
    "\n",
    "# Imprimir la lista de adyacencia para el grafo no dirigido\n",
    "print(\"Lista de adyacencia para el grafo no dirigido:\")\n",
    "for nodo, adyacentes in lista_adyacencia.items():\n",
    "    print(f\"{nodo}: {adyacentes}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a98a32c",
   "metadata": {},
   "source": [
    "##### Representación de un Grafo Dirigido a Lista de Adyacencia"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15594c6a",
   "metadata": {},
   "source": [
    "El grafo dirigido de abajo tiene $3$ vértices. Por lo tanto, se creará un arreglo de listas de tamaño $3$, donde cada índice representa los vértices. Ahora, el vértice `0` no tiene vecinos. Para el vértice `1`, tiene dos vecinos (es decir, `0` y `2`). Entonces, insertamos los vértices `0` y `2` en el índice `1` del arreglo. De manera similar, para el vértice `2`, insertamos sus vecinos en el arreglo de listas.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos19.PNG?raw=true\" width=\"500\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32997f2b",
   "metadata": {},
   "source": [
    "#### **Código para generar la lista de adyacencia de un grafo dirigido**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "8d232f79",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Lista de adyacencia para el grafo dirigido:\n",
      "0: []\n",
      "1: [2, 0]\n",
      "2: [0]\n"
     ]
    }
   ],
   "source": [
    "# Definir los nodos y las aristas dirigidas\n",
    "nodos = [0, 1, 2,]\n",
    "aristas = [(1, 2), (2, 0), (1, 0)]  # Aristas dirigidas\n",
    "\n",
    "# Inicializar la lista de adyacencia\n",
    "lista_adyacencia = {nodo: [] for nodo in nodos}\n",
    "\n",
    "# Rellenar la lista de adyacencia para grafo dirigido\n",
    "for arista in aristas:\n",
    "    nodo_origen, nodo_destino = arista\n",
    "    lista_adyacencia[nodo_origen].append(nodo_destino)\n",
    "\n",
    "# Imprimir la lista de adyacencia para el grafo dirigido\n",
    "print(\"Lista de adyacencia para el grafo dirigido:\")\n",
    "for nodo, adyacentes in lista_adyacencia.items():\n",
    "    print(f\"{nodo}: {adyacentes}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ff02bcf",
   "metadata": {},
   "source": [
    "#### Matriz de adyacencia vs Lista de adyacencia"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07a5d00f",
   "metadata": {},
   "source": [
    "Al comparar la complejidad algorítmica de la matriz de adyacencia y la lista de adyacencia para representar grafos, es importante considerar las diferentes operaciones que se pueden realizar sobre los grafos, como agregar o eliminar aristas, verificar si existe una conexión entre dos vértices, y recorrer el grafo. A continuación se presentan las operaciones más comunes:\n",
    "\n",
    "- **Agregar un Vértice:** Añadir un nuevo vértice al grafo.\n",
    "   - **Complejidad**:\n",
    "     - En una **lista de adyacencia**, es una operación $O(1)$, ya que simplemente se añade una nueva lista para el nuevo vértice.\n",
    "     - En una **matriz de adyacencia**, puede ser más costoso, $O(V^2)$, debido a la necesidad de aumentar el tamaño de la matriz.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Eliminar un Vértice:** Eliminar un vértice existente y todas sus aristas asociadas.\n",
    "   - **Complejidad**:\n",
    "     - En una **lista de adyacencia**, es $O(V + E)$, ya que se debe eliminar el vértice y actualizar todas las listas que contienen ese vértice.\n",
    "     - En una **matriz de adyacencia**, también es $O(V^2)$, por la reestructuración necesaria de la matriz.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Agregar una Arista:** Conectar dos vértices con una arista.\n",
    "   - **Complejidad**:\n",
    "     - En una **lista de adyacencia**, es $O(1)$, simplemente añadiendo el vértice destino a la lista del vértice origen.\n",
    "     - En una **matriz de adyacencia**, es $O(1)$, actualizando el valor de la celda correspondiente.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Eliminar una Arista:** Remover la conexión entre dos vértices.\n",
    "   - **Complejidad**:\n",
    "     - En una **lista de adyacencia**, puede ser hasta $O(V)$, buscando y eliminando el vértice destino de la lista del vértice origen.\n",
    "     - En una **matriz de adyacencia**, es $O(1)$, estableciendo el valor de la celda correspondiente a 0 o infinito.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Verificar si Dos Vértices están Conectados:** Determinar si existe una arista entre dos vértices específicos.\n",
    "   - **Complejidad**:\n",
    "     - En una **lista de adyacencia**, puede ser hasta $O(V)$, buscando en la lista.\n",
    "     - En una **matriz de adyacencia**, es $O(1)$.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Encontrar el Grado de un Vértice:** Calcular el número de aristas conectadas a un vértice.\n",
    "   - **Complejidad**:\n",
    "     - En una **lista de adyacencia**, es $O(1)$ si se mantiene un contador de grado, o $O(deg(V))$ si se cuenta cada vez.\n",
    "     - En una **matriz de adyacencia**, es $O(V)$, sumando las conexiones en la fila/columna correspondiente.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **Recorrido del Grafo (BFS y DFS):** Explorar el grafo, ya sea en amplitud (BFS) o profundidad (DFS).\n",
    "   - **Complejidad**:\n",
    "     - Tanto para **lista de adyacencia** como para **matriz de adyacencia**, es $O(V + E)$, aunque en la práctica, la lista de adyacencia es más eficiente para grafos dispersos.\n",
    "\n",
    "A manera de resumen se deja la siguiente tabla para una consulta rápida:\n",
    "\n",
    "| Operación                          | Matriz de Adyacencia | Lista de Adyacencia |\n",
    "|------------------------------------|----------------------|---------------------|\n",
    "| **Espacio de Almacenamiento**      | $$O(V^2)$$           | $$O(V + E)$$        |\n",
    "| **Agregar Arista**                 | $$O(1)$$             | $$O(1)$$            |\n",
    "| **Eliminar Arista**                | $$O(1)$$             | $$O(V)$$            |\n",
    "| **Verificar Conexión**             | $$O(1)$$             | $$O(V)$$            |\n",
    "| **Recorrer Vecinos de un Vértice** | $$O(V)$$             | $$O(deg(V))$$       |\n",
    "| **Recorrido del Grafo (BFS, DFS)** | $$O(V^2)$$           | $$O(V + E)$$        |\n",
    "\n",
    "- **$V$**: Número de vértices\n",
    "- **$E$**: Número de aristas\n",
    "- **$deg(V)$**: Grado del vértice $V$ (número de vecinos)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "977f93eb",
   "metadata": {},
   "source": [
    "### Aplicaciones de la vida real"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe58b01f",
   "metadata": {},
   "source": [
    "- Las estructuras de datos de grafos pueden utilizarse para representar interacciones entre jugadores en un equipo, como pases, tiros y entradas. Analizar estas interacciones puede proporcionar perspectivas sobre la dinámica del equipo y áreas para mejorar.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Comúnmente se utilizan para representar redes sociales, como redes de amigos en medios sociales.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Los grafos pueden utilizarse para representar la topología de redes informáticas, como las conexiones entre enrutadores y conmutadores.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Los grafos se utilizan para representar las conexiones entre diferentes lugares en una red de transporte, como carreteras y aeropuertos.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- ***Redes Neuronales:*** Los vértices representan neuronas y las aristas representan las sinapsis entre ellas. Las redes neuronales se utilizan para comprender cómo funciona nuestro cerebro y cómo cambian las conexiones cuando aprendemos. El cerebro humano tiene alrededor de 10^11 neuronas y cerca de 10^15 sinapsis.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- ***Compiladores:*** Los grafos se utilizan ampliamente en compiladores. Pueden ser utilizados para la inferencia de tipos, para el llamado análisis de flujo de datos, asignación de registros y muchos otros propósitos. También se utilizan en compiladores especializados, como la optimización de consultas en lenguajes de bases de datos.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- ***Planificación Robótica:*** Los vértices representan estados en los que puede estar el robot y las aristas las posibles transiciones entre los estados. Dichos planes de grafos se utilizan, por ejemplo, en la planificación de rutas para vehículos autónomos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4e17bf9",
   "metadata": {},
   "source": [
    "### Cuándo usar Grafos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c5ce595",
   "metadata": {},
   "source": [
    "- Cuando necesitas representar y analizar las relaciones entre diferentes objetos o entidades.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Cuando necesitas realizar análisis de redes.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Cuando necesitas identificar jugadores clave, influenciadores o cuellos de botella en un sistema.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Cuando necesitas hacer predicciones o recomendaciones.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- ***Modelando Redes:*** Los grafos se utilizan comúnmente para modelar varios tipos de redes, como redes sociales, redes de transporte y redes informáticas. En estos casos, los vértices representan nodos en la red, y las aristas representan las conexiones entre ellos.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- ***Encontrar Caminos:*** Los grafos se utilizan a menudo en algoritmos para encontrar caminos entre dos vértices en un grafo, como algoritmos de camino más corto. Por ejemplo, los grafos pueden utilizarse para encontrar la ruta más rápida entre dos ciudades en un mapa o la forma más eficiente de viajar entre múltiples destinos.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- ***Representando Relaciones de Datos:*** Los grafos pueden utilizarse para representar relaciones entre objetos de datos, como en una base de datos o estructura de datos. En estos casos, los vértices representan objetos de datos, y las aristas representan las relaciones entre ellos.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- ***Análisis de Datos:*** Los grafos pueden utilizarse para analizar y visualizar datos complejos, como en algoritmos de agrupamiento de datos o modelos de aprendizaje automático. En estos casos, los vértices representan puntos de datos, y las aristas representan las similitudes o diferencias entre ellos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65be438d",
   "metadata": {},
   "source": [
    "### Ventajas y Desventajas"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17587805",
   "metadata": {},
   "source": [
    "También hay algunos escenarios donde usar un grafo puede no ser el mejor enfoque. Por ejemplo, si los datos que se representan son muy simples o estructurados, un grafo puede ser excesivo y una estructura de datos más simple podría ser suficiente. Además, si el grafo es muy grande o complejo, puede ser difícil o costoso computacionalmente analizarlo o recorrerlo, lo que podría hacer que usar un grafo sea menos deseable.\n",
    "\n",
    "***Ventajas:***\n",
    "- Los grafos son una estructura de datos versátil que se puede usar para representar una amplia gama de relaciones y estructuras de datos.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Pueden usarse para modelar y resolver una amplia gama de problemas, incluyendo la búsqueda de caminos, agrupación de datos, análisis de redes y aprendizaje automático.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Los algoritmos de grafos suelen ser muy eficientes y se pueden usar para resolver problemas complejos de manera rápida y efectiva.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Los grafos pueden usarse para representar estructuras de datos complejas de una manera simple e intuitiva, haciéndolas más fáciles de entender y analizar.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "\n",
    "***Desventajas:***\n",
    "- Los grafos pueden ser complejos y difíciles de entender, especialmente para personas que no están familiarizadas con la teoría de grafos o algoritmos relacionados.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Crear y manipular grafos puede ser computacionalmente costoso, especialmente para grafos muy grandes o complejos.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Los algoritmos de grafos pueden ser difíciles de diseñar e implementar correctamente, y pueden ser propensos a errores y fallos.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- Los grafos pueden ser difíciles de visualizar y analizar, especialmente para grafos muy grandes o complejos, lo que puede dificultar la extracción de conocimientos significativos de los datos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf203e5b",
   "metadata": {},
   "source": [
    "## Recorridos en grafos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5890bb54",
   "metadata": {},
   "source": [
    "### Búsqueda en amplitud (BFS)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7311fe78",
   "metadata": {},
   "source": [
    "#### Introducción"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbd56c01",
   "metadata": {},
   "source": [
    "Breadth First Search (BFS) es un algoritmo de recorrido de grafos que opera nivel por nivel, empezando desde un nodo específico. Utiliza una cola para visitar primero todos los nodos adyacentes a un nodo dado, antes de moverse a los nodos en el siguiente nivel de profundidad. Este método es utilizado principalmente para encontrar componentes conectados y determinar rutas más cortas en grafos no ponderados, ofreciendo una manera sistemática y eficiente de explorar todas las aristas y nodos de un grafo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ff787ae",
   "metadata": {},
   "source": [
    "#### Relación entre BFS para grafos y árboles"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe0a3f66",
   "metadata": {},
   "source": [
    "En la relación entre BFS para grafos y árboles, ambos utilizan un enfoque similar de exploración por niveles. La principal diferencia radica en cómo se manejan los nodos repetidos: los árboles, al ser una estructura sin ciclos, no requieren una verificación adicional para los nodos ya visitados, mientras que los grafos pueden contener ciclos, lo que hace esencial llevar un registro de los nodos visitados. Para esto, se emplea una matriz booleana que indica si un nodo ha sido explorado, evitando así su procesamiento múltiple y asegurando una exploración eficiente y sistemática.\n",
    "\n",
    "BFS en grafos parte del supuesto de que todos los vértices son accesibles desde el nodo inicial, utilizando una estructura tipo cola para gestionar el orden de los nodos a visitar. En grafos desconectados, se ajusta el algoritmo para explorar otras componentes desconectadas tras finalizar con la componente conectada actual. Esta estructura de cola garantiza que la exploración se realice en el orden correcto, manteniendo la integridad del recorrido por niveles característico de BFS."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9084381",
   "metadata": {},
   "source": [
    "#### **Algoritmo BFS en grafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d156c402",
   "metadata": {},
   "source": [
    "El algoritmo de Búsqueda en Amplitud (BFS) para grafos se desarrolla de la siguiente manera:\n",
    "\n",
    "```pseudocode\n",
    "1. Inicialización: Se coloca el nodo de inicio en una cola y se lo marca como visitado, estableciendo así el punto de partida para la exploración del grafo.\n",
    "\n",
    "2. Exploración: Este proceso continúa mientras la cola no esté vacía. Se realiza lo siguiente:\n",
    "   - Se retira un nodo de la cola y se realiza la acción deseada, como imprimir su valor. Esto indica que el nodo está siendo procesado.\n",
    "   - Se examinan todos los vecinos directos de este nodo. Si un vecino aún no ha sido visitado, se le encola y se le marca como visitado.\n",
    "\n",
    "3. Terminación: El algoritmo repite el proceso de exploración hasta que la cola queda vacía. Esto garantiza que todos los nodos accesibles desde el nodo inicial hayan sido explorados en su totalidad.\n",
    "```\n",
    "Este procedimiento asegura que el recorrido del grafo se realiza de manera exhaustiva y en amplitud, procesando primero todos los nodos de un nivel antes de pasar al siguiente. El uso de una estructura tipo cola es crucial, ya que mantiene el orden de visita de los nodos de acuerdo con el principio de primero en entrar, primero en salir (FIFO), característico de BFS."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ba5e88f",
   "metadata": {},
   "source": [
    "**Pseudocódigo de recorrido BFS**\n",
    "```pseudo\n",
    "cola C; vértices v, w; ord = 0;\n",
    "Mientras queden vértices sin visitar\n",
    "   v = elegir un vértice no visitado;\n",
    "   marcar v;\n",
    "   C.vaciar();\n",
    "   C.encolar(v);\n",
    "   Mientras C no sea vacía\n",
    "      w = C.primero();\n",
    "      ord++;\n",
    "      orden(w)=ord;\n",
    "      C.desencolar();\n",
    "      Para cada vecino z de w\n",
    "         Si z no está visitado\n",
    "            marcar z;\n",
    "            C.encolar(z);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ef3f0e8",
   "metadata": {},
   "source": [
    "#### Ejemplo de aplicación"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84428d87",
   "metadata": {},
   "source": [
    "Dado el grafo de la siguiente imágen:\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/BFS_grafos00.png?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "realizar el paso a paso del algoritmo BFS para recorrer dicho grafo.\n",
    "\n",
    "- ***Paso 1:*** Inicialmente, la cola y las matrices visitadas están vacías (imagen anterior).\n",
    "\n",
    "- ***Paso 2:*** inserte el nodo 0 en la cola y márquelo como visitado.\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/BFS_grafos01.png?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- ***Paso 3:*** elimine el nodo 0 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/BFS_grafos02.png?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- ***Paso 4:*** elimine el nodo 1 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/BFS_grafos03.png?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- ***Paso 5:*** elimine el nodo 2 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/BFS_grafos04.png?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- ***Paso 6:*** Elimine el nodo 3 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola. Como podemos ver, se visitan todos los vecinos del nodo 3, así que pase al siguiente nodo que está al frente de la cola.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/BFS_grafos05.png?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- ***Paso 7:*** Elimine el nodo 4 del frente de la cola, visite a los vecinos no visitados y empújelos a la cola. Como podemos ver, todos los vecinos del nodo 4 son visitados, así que pase al siguiente nodo que está al frente de la cola.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/BFS_grafos06.png?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "Ahora, la cola queda vacía, por lo tanto, finalice este proceso de iteración."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cfd4e2fb",
   "metadata": {},
   "source": [
    "### **Búsqueda en profundidad (DFS)**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b22408a3",
   "metadata": {},
   "source": [
    "#### **Introducción**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4970db42",
   "metadata": {},
   "source": [
    "El DFS en un grafo es similar al DFS en un árbol. El único inconveniente aquí es que, a diferencia de los árboles, los grafos pueden contener ciclos (un nodo puede ser visitado dos veces). Para evitar procesar un nodo más de una vez, se utiliza una matriz booleana visitada. Un grafo puede tener más de un recorrido DFS.\n",
    "\n",
    "A partir de un vértice, comienza por alguno de sus vecinos, luego un vecino de éste, y así sucesivamente hasta llegar a un vértice que ya no tiene vecinos sin visitar. Sigue entonces por algún vecino del último vértice visitado que aún tiene vecinos sin visitar. lgual que en BFS, si al finalizar quedan vértices sin visitar, se repite a partir de un vértice no visitado.\n",
    "\n",
    "**Pseudocódigo de recorrido DFS**\n",
    "```pseudo\n",
    "pila P; vértices v, w; ord = 0;\n",
    "Mientras queden vértices sin visitar\n",
    "    v = elegir un vértice no visitado;\n",
    "    marcar v;\n",
    "    P.vaciar();\n",
    "    P.apilar(v);\n",
    "    Mientras P no sea vacía\n",
    "        w = P.tope();\n",
    "        ord++;\n",
    "        orden(w)=ord;\n",
    "        P.desapilar();\n",
    "        Para cada vecino z de w\n",
    "            Si z no está visitado\n",
    "                marcar z;\n",
    "                P.apilar(z);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d11a22ce",
   "metadata": {},
   "source": [
    "#### Ejemplo de recorridos DFS en un mismo grafo"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b57b48e",
   "metadata": {},
   "source": [
    "```pseudocode\n",
    "Entrada: n = 4, e = 6  \n",
    "0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3  \n",
    "Salida: DFS desde el vértice 1: 1 2 0 3  \n",
    "```\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/DFS_grafo00.gif?raw=true\" width=\"250\" />\n",
    "</p>\n",
    "\n",
    "```pseudocode\n",
    "Entrada: n = 4, e = 6 \n",
    "2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3 \n",
    "Salida: DFS desde el vértice 2: 2 0 1 3 \n",
    "```\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/DFS_grafo01.gif?raw=true\" width=\"250\" />\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1cf0674a",
   "metadata": {},
   "source": [
    "#### Ejemplo explicado"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8aafea80",
   "metadata": {},
   "source": [
    "Dado el grafo de la siguiente imágen:\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/DFS_grafo02.webp?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "realizar el paso a paso del algoritmo DFS para recorrer dicho grafo.\n",
    "\n",
    "- ***Paso 1:*** Inicialmente, la pila y las matrices visitadas están vacías (imagen anterior)\n",
    "\n",
    "- ***Paso 2:*** visite 0 y coloque sus nodos adyacentes que aún no han sido visitados en la pila.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/DFS_grafo03.webp?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- ***Paso 3:*** Ahora, el Nodo 1 está en la parte superior de la pila, así que visite el nodo 1, sáquelo de la pila y coloque todos los nodos adyacentes que no se visitan en la pila.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/DFS_grafo04.webp?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- ***Paso 4:*** Ahora, el Nodo 2 está en la parte superior de la pila, así que visite el nodo 2, sáquelo de la pila y coloque todos sus nodos adyacentes que no sean visitados (es decir, 3, 4) en la pila.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/DFS_grafo05.webp?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- ***Paso 5:*** Ahora, el nodo 4 está en la parte superior de la pila, así que visite el nodo 4, sáquelo de la pila y coloque todos los nodos adyacentes que no se visitan en la pila.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/DFS_grafo06.webp?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- ***Paso 6:*** Ahora, el nodo 3 está en la parte superior de la pila, así que visite el nodo 3, sáquelo de la pila y coloque todos los nodos adyacentes que no se visitan en la pila.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/DFS_grafo07.webp?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "Ahora, la pila queda vacía, lo que significa que hemos visitado todos los nodos y nuestro recorrido DFS finaliza."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c69a150",
   "metadata": {},
   "source": [
    "### **Detección de ciclos en grafos usando DFS**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ad2f676",
   "metadata": {},
   "source": [
    "#### **Idea central**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5caf9151",
   "metadata": {},
   "source": [
    "La detección de ciclos en grafos dirigidos se basa en identificar si existe un \"borde de regreso\" en el grafo, es decir, un nodo que apunta a uno de sus ancestros."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fdb5aa5c",
   "metadata": {},
   "source": [
    "#### **Uso de la Técnica DFS**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe0b9ef5",
   "metadata": {},
   "source": [
    "Para encontrar ciclos, se emplea la técnica de Búsqueda en Profundidad (DFS). Esta técnica consiste en explorar el grafo de manera exhaustiva, adentrándose lo más posible a lo largo de cada rama antes de retroceder. El ciclo está presente si, y solo si, se encuentra un borde de regreso durante esta exploración."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b5902907",
   "metadata": {},
   "source": [
    "#### **Detección del Borde de Regreso**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2ced193",
   "metadata": {},
   "source": [
    "Para detectar un borde de regreso, es crucial seguir dos conjuntos de nodos:\n",
    "   1. **Nodos Visitados:** Aquellos que ya hemos explorado.\n",
    "   2. **Pila de Recursión:** Los nodos que están siendo explorados actualmente.\n",
    "\n",
    "Si durante la búsqueda en profundidad llegamos a un nodo que ya se encuentra en la pila de recursión, entonces hemos detectado un ciclo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "338a80a9",
   "metadata": {},
   "source": [
    "#### **Manejo de Grafos Desconectados**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74c14c35",
   "metadata": {},
   "source": [
    "En grafos desconectados, es necesario realizar una búsqueda en profundidad en cada componente del grafo. Esto se conoce como obtener el \"bosque DFS\". En cada árbol del bosque, se busca de manera independiente la presencia de bordes de regreso para identificar ciclos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19c7d122",
   "metadata": {},
   "source": [
    "#### **Algoritmo para Implementar la Detección de Ciclos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f39b6f01",
   "metadata": {},
   "source": [
    "```pseudocode\n",
    "1. Creación de la Función DFS Recursiva: Esta función toma los siguientes parámetros: el vértice actual, el conjunto de nodos visitados y la pila de recursión.\n",
    "2. Marcar el Nodo Actual: Al llegar a un nodo, se marca como visitado y se añade a la pila de recursión.\n",
    "3. Explorar Vértices Adyacentes:\n",
    "   - Se recorren todos los vértices adyacentes al nodo actual.\n",
    "   - Si un vértice adyacente ya está en la pila de recursión, se retorna verdadero, indicando la detección de un ciclo.\n",
    "   - Si no está en la pila, se realiza una llamada recursiva para ese vértice.\n",
    "4. Retorno de la Función Recursiva: Al concluir la exploración de un nodo, se lo elimina de la pila de recursión. Esto indica que ya no forma parte del camino actual que estamos explorando.\n",
    "5. Conclusión: Si alguna de las llamadas recursivas retorna verdadero, se detienen las llamadas futuras y se concluye que el grafo contiene al menos un ciclo.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a52ec9b5",
   "metadata": {},
   "source": [
    "#### **Ejemplo**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6c0a48b",
   "metadata": {},
   "source": [
    "Consideremos el siguiente grafo:\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos_ciclos00.webp?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "Considere que comenzamos la iteración desde el vértice `0`.\n",
    "\n",
    "- Inicialmente, se marcará `0` tanto en el arreglo `visited[]` como en el `recStack[]`, ya que es parte de la ruta actual.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos_ciclos01.webp?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- Ahora `0` tiene dos vértices adyacentes `1` y `2`. Consideremos el recorrido hasta el vértice `1`. Entonces `1` se marcará tanto en `visited[]` como en el `recStack[]`.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos_ciclos02.webp?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- El vértice `1` tiene solo un vértice adyacente. Llame a la función recursiva para `2` y márquela en `visited[]` y en `recStack[]`.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos_ciclos03.webp?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- El vértice `2` también tiene dos vértices adyacentes.\n",
    "  - Se visita el vértice `0` y ya está marcado en `recStack[]`. Entonces, si primero se marca `0`, obtendremos la respuesta de que hay un ciclo presente.\n",
    "  - Por otro lado, si se marca primero el vértice `3`, entonces se marcará `3` en `visited[]` y `recStack[]`.\n",
    "  \n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos_ciclos04.webp?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- Al regresar de la llamada recursiva para `3`, se desmarcará de `recStack[]` ya que ahora no forma parte de la ruta que se está rastreando actualmente.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos_ciclos05.webp?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- Ahora sólo nos queda una opción para comprobar, el vértice `0`, que ya está marcado en `recStack[]`.\n",
    "\n",
    "Entonces, podemos concluir que existe un ciclo. También podemos encontrar el ciclo si hemos atravesado hasta el vértice `2` desde el propio `0` de esta misma manera."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e75dc55",
   "metadata": {},
   "source": [
    "## **Definiciones formales en Grafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c933e97",
   "metadata": {},
   "source": [
    "### **Grafo**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b5f3cbfb",
   "metadata": {},
   "source": [
    "Un **grafo** es una estructura matemática que se utiliza para modelar relaciones o conexiones entre objetos. Un grafo, denotado como $ G $, está compuesto por dos elementos principales:\n",
    "\n",
    "- **Vértices (o nodos)**: Representados por el conjunto $ V(G) $, los vértices son los \"puntos\" que componen el grafo. Estos puntos pueden representar entidades como personas, ciudades, estaciones, etc. El conjunto $ V(G) $ debe ser finito, es decir, tener una cantidad limitada de vértices.\n",
    "  \n",
    "- **Aristas (o bordes)**: Representadas por el conjunto $ E(G) $, las aristas son las conexiones entre los vértices. Cada arista es un par de vértices, denotado como $ (i,j) $, que indica que existe una conexión entre el vértice $ i $ y el vértice $ j $. En el caso de grafos no dirigidos (como el que se describe aquí), los pares no están ordenados, lo que significa que la conexión entre $ i $ y $ j $ es bidireccional. Por ejemplo, si existe una arista $ (1,2) $, eso implica que 1 está conectado con 2, y viceversa.\n",
    "\n",
    "**Notación:**\n",
    "- $ n = |V(G)| $ denota el número de vértices en el grafo. Esto indica cuántos nodos o puntos existen en $ G $.\n",
    "- $ m = |E(G)| $ denota el número de aristas en el grafo, es decir, cuántas conexiones o relaciones hay entre los vértices.\n",
    "- En algunas ocasiones, también se puede utilizar la notación $ V_G $ y $ E_G $ para referirse a los conjuntos de vértices y aristas del grafo $ G $.\n",
    "\n",
    "Un grafo se llama **trivial** si contiene un solo vértice y no tiene ninguna arista, lo que implica que no existen conexiones.\n",
    "\n",
    "**Ejemplo:**\n",
    "Dado el siguiente grafo:\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos20.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- **Vértices**: $ V(G) = \\{1, 2, 3, 4, 5, 6, 7\\} $. Esto significa que hay 7 vértices en total.\n",
    "- **Aristas**: $ E(G) = \\{(1,2), (2,4), (2,7), (3,5), (3,6), (4,5), (4,6), (4,7), (5,6), (6,7)\\} $. Aquí vemos que los vértices están conectados entre sí a través de 10 aristas. Por ejemplo, el vértice 1 está conectado al vértice 2, el vértice 2 está conectado al vértice 4, y así sucesivamente.\n",
    "\n",
    "- **Número de vértices**: $ n = 7 $ (hay 7 vértices).\n",
    "- **Número de aristas**: $ m = 10 $ (hay 10 conexiones entre los vértices).\n",
    "\n",
    "Este grafo, con 7 vértices y 10 aristas, no es trivial porque tiene múltiples vértices y varias conexiones entre ellos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bcf46127",
   "metadata": {},
   "source": [
    "### **Dígrafo**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e676be1",
   "metadata": {},
   "source": [
    "Un **dígrafo**, o **grafo dirigido**, es una estructura matemática similar a un grafo, pero con una diferencia clave: las **aristas** (o conexiones) entre los vértices son **direccionales**, lo que significa que cada conexión tiene un sentido específico. En este tipo de grafo, las conexiones se representan por **pares ordenados** de vértices.\n",
    "\n",
    "**Elementos principales:**\n",
    "- **Vértices**: El conjunto de vértices, denotado como $ V(G) $, es un conjunto finito que contiene los nodos o puntos del dígrafo. Al igual que en los grafos no dirigidos, los vértices pueden representar entidades como personas, objetos, lugares, etc.\n",
    "  \n",
    "- **Aristas**: En un dígrafo, las aristas se denotan como pares ordenados $ (i, j) $, donde el vértice $ i $ está conectado al vértice $ j $ **en una dirección específica**. En otras palabras, la arista $ (i, j) $ significa que hay una conexión que **va desde** el vértice $ i $ hacia el vértice $ j $, pero **no necesariamente en sentido contrario**. Esto implica que si $ (i, j) $ pertenece al conjunto de aristas $ E(G) $, no se puede asumir que $ (j, i) $ también esté presente, a menos que se indique explícitamente.\n",
    "\n",
    "**Notación:**\n",
    "- $ n = |V(G)| $: Denota el número de vértices en el dígrafo.\n",
    "- $ m = |E(G)| $: Denota el número de aristas, es decir, cuántas conexiones direccionadas existen entre los vértices.\n",
    "\n",
    "**Ejemplo:**\n",
    "Consideremos el siguiente dígrafo:\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos21.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- **Vértices**: $ V(G) = \\{1, 2, 3, 4, 5, 6, 7\\} $. Esto significa que hay 7 vértices en total.\n",
    "- **Aristas**: $ E(G) = \\{(2,1), (4,2), (2,7), (3,5), (5,3), (3,6), (6,3), (4,5), (4,6), (7,4), (6,5), (6,7)\\} $. En este caso, cada par indica una conexión con una dirección específica. Por ejemplo:\n",
    "  - $ (2,1) $: Existe una conexión **de** $ 2 $ **a** $ 1 $, pero **no necesariamente** de $ 1 $ a $ 2 $.\n",
    "  - $ (4,2) $: Existe una conexión de $ 4 $ a $ 2 $.\n",
    "  - $ (6,7) $: Existe una conexión de $ 6 $ a $ 7 $.\n",
    "  \n",
    "- **Número de vértices**: $ n = 7 $ (hay 7 vértices).\n",
    "- **Número de aristas**: $ m = 12 $ (hay 12 conexiones dirigidas entre los vértices).\n",
    "\n",
    "**Diferencia con un grafo no dirigido:**\n",
    "A diferencia de un grafo no dirigido, donde las aristas representan una relación bidireccional entre dos vértices, en un dígrafo las aristas representan relaciones unidireccionales. Esto es útil en situaciones donde el flujo entre los nodos tiene una dirección específica. Por ejemplo, en un **sistema de carreteras** donde algunas rutas son de un solo sentido, o en una **red social** donde las relaciones pueden ser asimétricas (una persona sigue a otra, pero no al revés).\n",
    "\n",
    "Este tipo de grafo dirigido es común en muchas aplicaciones, como la representación de flujos de información, diagramas de dependencias o modelos de relaciones jerárquicas."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f21e36a",
   "metadata": {},
   "source": [
    "### **Multígrafo y pseudografo**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5121963d",
   "metadata": {},
   "source": [
    "Un **multigrafo** es una variante de grafo en la que se permite que haya más de una arista entre el mismo par de vértices. Esto significa que dos vértices pueden estar conectados por varias aristas, lo que modela situaciones donde existen múltiples conexiones o relaciones entre los mismos elementos. \n",
    "\n",
    "Por ejemplo, si los vértices representan ciudades y las aristas representan rutas de vuelo, un multigrafo podría permitir múltiples vuelos (es decir, múltiples aristas) entre dos ciudades, cada uno con diferentes horarios o aerolíneas.\n",
    "\n",
    "- Formalmente, un multigrafo $ G $ está compuesto por un conjunto de vértices $ V(G) $ y un conjunto de aristas $ E(G) $, donde cada arista conecta un par de vértices, pero puede haber varias aristas entre el mismo par de vértices.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos22.PNG?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "  \n",
    "**Ejemplo:**\n",
    "- Si $ V(G) = \\{1, 2\\} $, podríamos tener un conjunto de aristas $ E(G) = \\{(1,2), (1,2)\\} $, lo que significa que entre los vértices $ 1 $ y $ 2 $ existen dos aristas distintas.\n",
    "\n",
    "Por otro lado, un **pseudografo** es un tipo especial de grafo en el que se permiten **bucles** (o **loops**). Un bucle es una arista que conecta un vértice consigo mismo, es decir, una arista de la forma $ (v,v) $. Los pseudografos pueden ser útiles para modelar situaciones donde una entidad puede tener una relación consigo misma. \n",
    "\n",
    "Por ejemplo, en un sistema de relaciones entre personas, un bucle podría representar una relación que una persona tiene consigo misma, como la autoevaluación o la auto-referencia.\n",
    "\n",
    "**Definiciones clave:**\n",
    "- **Multigrafo**: Permite múltiples aristas entre un mismo par de vértices.\n",
    "- **Pseudografo**: Permite aristas de tipo $ (v,v) $, es decir, aristas que conectan un vértice consigo mismo (bucles).\n",
    "\n",
    "**Ejemplo de pseudografo:**\n",
    "- Si $ V(G) = \\{1, 2\\} $ y $ E(G) = \\{(1,1), (1,2)\\} $, el vértice $ 1 $ tiene un bucle que lo conecta consigo mismo, además de una arista que lo conecta con el vértice $ 2 $.\n",
    "\n",
    "**Resumen:**\n",
    "- Un **multigrafo** permite múltiples conexiones entre dos vértices, algo que no está permitido en los grafos simples.\n",
    "- Un **pseudografo** permite, además de las conexiones estándar, que un vértice se conecte consigo mismo mediante un bucle, lo cual añade flexibilidad a la representación de relaciones.\n",
    "\n",
    "Estos conceptos son especialmente útiles cuando se trata de modelar sistemas complejos donde pueden existir múltiples relaciones entre entidades o cuando una entidad puede tener una relación consigo misma."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80b31a67",
   "metadata": {},
   "source": [
    "### **Vecindario**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "160701bb",
   "metadata": {},
   "source": [
    "En el contexto de grafos, los **vecindarios** nos ayudan a describir las relaciones de un vértice con sus vértices adyacentes, es decir, aquellos con los que está directamente conectado mediante una arista.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos23.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- **Adyacencia**  \n",
    "Decimos que un vértice $ v $ es **adyacente** a otro vértice $ w $ si existe una arista entre ellos, lo que se representa matemáticamente como $ (v, w) \\in E(G) $, donde $ E(G) $ es el conjunto de aristas del grafo $ G $. Los vértices $ v $ y $ w $ son los **extremos de la arista**, ya que la arista conecta estos dos vértices.\n",
    "\n",
    "Por ejemplo, si en un grafo $ G $ tenemos la arista $ (5, 6) $, entonces los vértices 5 y 6 son adyacentes entre sí, y se consideran los extremos de esa arista.\n",
    "\n",
    "- **Vecindario**  \n",
    "El **vecindario** de un vértice $ v $ en un grafo $ G $, denotado como $ N_G(v) $, es el conjunto de todos los vértices que son adyacentes a $ v $. En otras palabras, el vecindario de $ v $ incluye todos los vértices con los que $ v $ está conectado por una arista. Este concepto es útil para analizar la red de conexiones de un vértice dentro de un grafo.\n",
    "\n",
    "Matemáticamente, podemos expresar el vecindario de $ v $ como:\n",
    "$$ N_G(v) = \\{ w \\in V(G) \\mid (v, w) \\in E(G) \\} $$\n",
    "Donde $ w $ es cualquier vértice que tiene una arista conectándolo a $ v $.\n",
    "\n",
    "- **Vecindario cerrado**  \n",
    "El **vecindario cerrado** de un vértice $ v $, denotado como $ N_G[v] $, incluye no solo los vértices adyacentes a $ v $, sino también el propio vértice $ v $. Por lo tanto, el vecindario cerrado es el vecindario regular más el propio vértice $ v $. Esto se expresa como:\n",
    "$$ N_G[v] = N_G(v) \\cup \\{v\\} $$\n",
    "Es decir, el vecindario cerrado de $ v $ contiene tanto a $ v $ como a todos los vértices conectados a él por una arista.\n",
    "\n",
    "- **Notación**  \n",
    "En algunos casos, si el grafo $ G $ está claro por el contexto, podemos simplificar la notación de los vecindarios. En lugar de escribir $ N_G(v) $ o $ N_G[v] $, simplemente utilizamos $ N(v) $ para referirnos al vecindario de $ v $, y $ N[v] $ para el vecindario cerrado de $ v $.\n",
    "\n",
    "**Ejemplo:**  \n",
    "Consideremos un grafo $ G $ con los vértices $ V(G) = \\{1, 2, 3, 4, 5, 6, 7\\} $ y las aristas $ E(G) = \\{(2,1), (4,2), (2,7), (3,5), (5,3), (3,6), (6,3), (4,5), (4,6), (7,4), (6,5), (6,7)\\} $.\n",
    "- El vecindario de $ 2 $ es $ N_G(2) = \\{2, 1\\}, \\{4, 2\\}, \\{2, 7\\} $, ya que los vértices 1, 4 y 7 están conectados a $ 2 $.\n",
    "- El vecindario cerrado de $ 2 $ es $ N_G[2] = \\{1, 2, 4, 7\\} $, que incluye tanto a $ 2 $ como a sus vértices adyacentes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e505ba7a",
   "metadata": {},
   "source": [
    "### **Grado**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7f5bc65",
   "metadata": {},
   "source": [
    "El **grado** de un vértice $ v $ en un grafo $ G $ es el número de vértices con los que $ v $ está directamente conectado. Este número corresponde a la **cardinalidad del conjunto de vecindario de $ v $**, es decir, cuántos vértices adyacentes tiene. En notación matemática, el grado de un vértice $ v $ se denota como $ d_G(v) $, y si el contexto es claro (cuando estamos hablando de un solo grafo $ G $), simplemente se denota $ d(v) $.\n",
    "\n",
    "Por ejemplo, si un vértice tiene 3 conexiones (es decir, está conectado a 3 otros vértices), entonces su grado es 3.\n",
    "\n",
    "**Grado mínimo y máximo en un grafo**  \n",
    "Además de calcular el grado de un vértice en particular, también se puede calcular:\n",
    "- **Grado mínimo** $ \\delta(G) $: Este es el menor grado entre todos los vértices del grafo $ G $, es decir, el número más pequeño de conexiones que tiene algún vértice.\n",
    "- **Grado máximo** $ \\Delta(G) $: Este es el mayor grado entre todos los vértices del grafo $ G $, es decir, el número más grande de conexiones que tiene algún vértice.\n",
    "\n",
    "**Ejemplo**  \n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos20.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "En la figura observamos que el grafo tiene 7 vértices. Calculando el grado de cada vértice:\n",
    "\n",
    "- **Vértice 1**: Está conectado solo al vértice 2, por lo que $ d(1) = 1 $.\n",
    "- **Vértice 2**: Está conectado a los vértices 1, 4 y 7, por lo que $ d(2) = 3 $.\n",
    "- **Vértice 3**: Está conectado a los vértices 5 y 6, por lo que $ d(3) = 2 $.\n",
    "- **Vértice 4**: Está conectado a los vértices 2, 5, 6 y 7, por lo que $ d(4) = 4 $.\n",
    "- **Vértice 5**: Está conectado a los vértices 3, 4 y 6, por lo que $ d(5) = 3 $.\n",
    "- **Vértice 6**: Está conectado a los vértices 3, 4, 5 y 7, por lo que $ d(6) = 4 $.\n",
    "- **Vértice 7**: Está conectado a los vértices 2, 4 y 6, por lo que $ d(7) = 3 $.\n",
    "\n",
    "- **Grado mínimo y máximo:**  \n",
    "  - El **grado mínimo** $ \\delta(G) $ es $ 1 $, ya que el vértice 1 solo tiene una conexión.\n",
    "  - El **grado máximo** $ \\Delta(G) $ es $ 4 $, ya que los vértices 4 y 6 tienen el mayor número de conexiones, ambos con 4.\n",
    "\n",
    "- **Notación resumida:**  \n",
    "  - $ d(2) = 3 $: El vértice 2 tiene 3 conexiones.\n",
    "  - $ \\delta(G) = 1 $: El grado mínimo del grafo es 1 (el vértice 1).\n",
    "  - $ \\Delta(G) = 4 $: El grado máximo del grafo es 4 (vértices 4 y 6)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf8ae227",
   "metadata": {},
   "source": [
    "### **Vértices Aislado y Universal**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "308829f5",
   "metadata": {},
   "source": [
    "**Vértice Aislado** \n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos25.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "Un **vértice aislado** es un vértice que no tiene ninguna conexión con otros vértices en el grafo. Esto significa que no existe ninguna arista que lo conecte a algún otro vértice. Matemáticamente, decimos que el **vecindario** de un vértice $ v $ es vacío, es decir, $ N(v) = \\emptyset $. Como consecuencia, el **grado** de un vértice aislado es 0, lo que se denota $ d(v) = 0 $.\n",
    "\n",
    "- En el grafo de la imagen, el vértice $ 1 $ es un vértice **aislado** porque no está conectado a ningún otro vértice, es decir, no tiene ninguna arista que lo conecte con otros vértices. Por tanto, $ N(1) = \\emptyset $ y $ d(1) = 0 $.\n",
    "\n",
    "**Vértice Universal**  \n",
    "Un **vértice universal** es un vértice que está conectado a **todos los demás vértices** en el grafo. En otras palabras, el vecindario de un vértice universal incluye a todos los demás vértices del grafo. Esto implica que, si el grafo tiene $ n $ vértices, el grado del vértice universal es $ d(v) = n - 1 $.\n",
    "\n",
    "- En el grafo $ G - \\{1\\} $ (es decir, el grafo sin el vértice $ 1 $), el vértice $ 4 $ es un **vértice universal**, porque está conectado a todos los demás vértices: $ 2, 3, 5, 6, 7 $. Esto significa que su vecindario es $ N(4) = \\{2, 3, 5, 6, 7\\} $, y el grado de $ 4 $ en $ G - \\{1\\} $ es $ d(4) = 5 $, lo que corresponde a la cantidad de vértices restantes en el grafo.\n",
    "\n",
    "**Relación entre vértices aislados y universales**  \n",
    "Un grafo **no trivial** (es decir, un grafo que tiene más de un vértice) **no puede tener simultáneamente un vértice aislado y un vértice universal**. La razón es que un vértice universal debe estar conectado a **todos** los demás vértices, lo que implica que **no puede existir ningún vértice aislado** en el mismo grafo, ya que un vértice aislado no tendría conexión con el vértice universal.\n",
    "\n",
    "- En este caso, el grafo $ G $ tiene un vértice aislado, que es $ 1 $. Por lo tanto, no es posible que el vértice $ 4 $ sea universal en el grafo completo $ G $, aunque sí lo es en $ G - \\{1\\} $, que es el subgrafo resultante al eliminar el vértice aislado.\n",
    "\n",
    "**Resumen:**  \n",
    "- Un **vértice aislado** no tiene conexiones: $ N(v) = \\emptyset $, $ d(v) = 0 $.\n",
    "- Un **vértice universal** está conectado a todos los demás vértices: $ N(v) = V(G) - \\{v\\} $, $ d(v) = n-1 $.\n",
    "- En el grafo $ G $, el vértice $ 1 $ es aislado, y el vértice $ 4 $ es universal en $ G - \\{1\\} $.\n",
    "- Un grafo no trivial con un vértice aislado **no** puede tener un vértice universal.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b04728f",
   "metadata": {},
   "source": [
    "### **Grafo Regular**  \n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos27.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "Un **grafo regular** es un tipo especial de grafo en el que **todos los vértices** tienen el mismo número de conexiones, es decir, todos los vértices tienen el **mismo grado**. En un grafo regular, si el grado de cada vértice es \\( k \\), se dice que el grafo es **k-regular**. Esto significa que cada vértice está conectado a exactamente \\( k \\) vértices en el grafo.\n",
    "\n",
    "Por ejemplo, si en un grafo todos los vértices tienen grado 2, decimos que el grafo es **2-regular**. Si todos los vértices tienen grado 4, el grafo es **4-regular**, y así sucesivamente.\n",
    " \n",
    "**Ejemplo:**  \n",
    "Imagina un grafo con 5 vértices, y cada vértice está conectado a exactamente 2 otros vértices. Este sería un ejemplo de un **grafo 2-regular**.\n",
    "\n",
    "### **Grafo Cúbico**  \n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos28.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "Un **grafo cúbico** es un caso particular de grafo regular, donde todos los vértices tienen **grado 3**. En un grafo cúbico, cada vértice está conectado a exactamente 3 vértices. Esto significa que todos los vértices tienen 3 aristas que los conectan a otros vértices. Los grafos cúbicos son un ejemplo específico de **grafos 3-regulares**.\n",
    "\n",
    "**Ejemplo:**  \n",
    "Imagina un grafo con 6 vértices, y cada vértice está conectado a exactamente 3 otros vértices. Este sería un ejemplo de un **grafo cúbico**, ya que el grado de cada vértice es 3.\n",
    "\n",
    "### **Diferencias clave:**\n",
    "\n",
    "- Un **grafo regular** es un grafo en el que todos los vértices tienen el mismo grado, pero el valor del grado puede ser cualquiera (2, 3, 4, etc.).\n",
    "- Un **grafo cúbico** es un tipo de grafo regular en el que **todos los vértices tienen exactamente grado 3**.\n",
    "\n",
    "Este tipo de grafos es útil en aplicaciones que requieren una distribución uniforme de conexiones entre nodos, como redes de comunicación o ciertos modelos en física."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "814eae88",
   "metadata": {},
   "source": [
    "## **Suma de Grados en un Grafo**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7386f8c",
   "metadata": {},
   "source": [
    "En un grafo, cada vértice tiene un grado, que representa cuántas aristas lo conectan con otros vértices. Un resultado fundamental en teoría de grafos establece que *la **suma de los grados de todos los vértices** de un grafo es siempre **igual al doble del número de aristas** del grafo*. Este resultado se puede expresar de la siguiente manera:\n",
    "\n",
    "$$\n",
    "\\sum_{v \\in V(G)} d(v) = 2m\n",
    "$$\n",
    "\n",
    "Donde:\n",
    "- $ \\sum_{v \\in V(G)} d(v) $ es la suma de los grados de todos los vértices $ v $ en el grafo $ G $,\n",
    "- $ m $ es el número total de aristas en el grafo.\n",
    "\n",
    "Este teorema refleja una propiedad importante: **cada arista del grafo se cuenta dos veces** cuando sumamos los grados de los vértices. Esto es porque cada arista conecta dos vértices, lo que incrementa el grado de ambos vértices en 1. Así, al sumar el grado de todos los vértices, estamos contabilizando cada arista una vez por cada vértice en sus extremos, resultando en un total que es el doble del número de aristas.\n",
    "\n",
    "**Ejemplo:**  \n",
    "Consideremos un grafo simple con 4 vértices y 3 aristas. Supongamos que el grafo tiene las siguientes conexiones:\n",
    "- $ V(G) = \\{1, 2, 3, 4\\} $\n",
    "- Aristas: $ E(G) = \\{(1,2), (2,3), (3,4)\\} $\n",
    "\n",
    "Los grados de los vértices serían:\n",
    "- $ d(1) = 1 $ (el vértice 1 está conectado solo a 1 vértice),\n",
    "- $ d(2) = 2 $ (el vértice 2 está conectado a 2 vértices),\n",
    "- $ d(3) = 2 $ (el vértice 3 está conectado a 2 vértices),\n",
    "- $ d(4) = 1 $ (el vértice 4 está conectado solo a 1 vértice).\n",
    "\n",
    "La suma de los grados es:\n",
    "$$\n",
    "d(1) + d(2) + d(3) + d(4) = 1 + 2 + 2 + 1 = 6\n",
    "$$\n",
    "El número de aristas $ m $ es 3, y según el teorema:\n",
    "$$\n",
    "2m = 2 \\times 3 = 6\n",
    "$$\n",
    "Esto confirma que la suma de los grados de los vértices es igual al doble del número de aristas en el grafo.\n",
    "\n",
    "**Interpretación Intuitiva**  \n",
    "Este teorema es una forma eficiente de contar el número total de conexiones en un grafo. Como cada arista conecta dos vértices, su contribución se cuenta dos veces cuando sumamos los grados de todos los vértices. Esta relación es una herramienta útil en la teoría de grafos, ya que permite verificar rápidamente la consistencia de los grados y el número de aristas en un grafo.\n",
    "\n",
    "Es importante recordar que esta propiedad aplica tanto para grafos dirigidos como no dirigidos, aunque en los grafos dirigidos se toman en cuenta por separado el **grado de entrada** y el **grado de salida** de cada vértice.\n",
    "\n",
    "Este teorema es una de las muchas propiedades que hacen que los grafos sean estructuras matemáticas tan interesantes y útiles para modelar una amplia variedad de problemas en campos como las redes sociales, el análisis de rutas, y la biología.\n",
    "\n",
    "#### **Corolario**  \n",
    "\n",
    "*Todo grafo cúbico tiene un número par de vértices.*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f92ea70b",
   "metadata": {},
   "source": [
    "## **Complemento de un Grafo**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e13a962",
   "metadata": {},
   "source": [
    "\n",
    "El **complemento de un grafo** $ G $, denotado como $ \\bar{G} $, es un grafo que contiene los mismos vértices que el grafo original $ G $, pero con una diferencia clave en sus conexiones (aristas). En el grafo complementario $ \\bar{G} $, dos vértices están conectados por una arista **si y solo si no están conectados en el grafo original** $ G $. Es decir, $ \\bar{G} $ contiene todas las aristas que **faltan** en $ G $, y no contiene ninguna de las aristas que sí están presentes en $ G $.\n",
    "\n",
    "En resumen:\n",
    "- $ G $ y $ \\bar{G} $ tienen el mismo conjunto de vértices.\n",
    "- Si dos vértices están conectados en $ G $, entonces **no están conectados** en $ \\bar{G} $, y viceversa.\n",
    "\n",
    "**Ejemplo**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos29.PNG?raw=true\" width=\"750\" />\n",
    "</p>\n",
    "\n",
    "En la imagen, vemos dos grafos, a la izquierda tenemos el grafo original $ G $ y a la derecha está su complemento $ \\bar{G} $.\n",
    "\n",
    "- $ G $ tiene 7 vértices, y algunos de ellos están conectados por aristas. Por ejemplo, los vértices 2 y 4 están conectados, pero los vértices 1 y 5 no lo están.\n",
    "- El complemento $ \\bar{G} $ tiene los mismos 7 vértices que $ G $, pero ahora las aristas aparecen donde no existían en $ G $, y desaparecen donde sí existían en $ G $. Por ejemplo:\n",
    "  - Los vértices 1 y 5, que no estaban conectados en $ G $, ahora **sí están conectados** en $ \\bar{G} $.\n",
    "  - Los vértices 2 y 4, que estaban conectados en $ G $, **no están conectados** en $ \\bar{G} $.\n",
    "\n",
    "El concepto de complemento de un grafo es útil para analizar la estructura de un grafo desde una perspectiva opuesta. Mientras que en $ G $ estudiamos las conexiones existentes, en $ \\bar{G} $ nos enfocamos en las conexiones **faltantes**. Este tipo de análisis tiene aplicaciones en diversas áreas, como la teoría de redes y la optimización, donde a veces es importante identificar qué conexiones podrían mejorar la eficiencia de un sistema si fueran añadidas.\n",
    "\n",
    "En resumen, el complemento $ \\bar{G} $ nos da una nueva forma de ver la estructura de un grafo, resaltando las relaciones que no existen en el grafo original."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a03042a",
   "metadata": {},
   "source": [
    "## **Subgrafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c3cdae6",
   "metadata": {},
   "source": [
    "Un **subgrafo** es una parte de un grafo más grande, que mantiene ciertas conexiones (aristas) y vértices del grafo original. En términos formales, un grafo $ H $ es un subgrafo de un grafo $ G $ si los **vértices** y **aristas** de $ H $ son subconjuntos de los vértices y aristas de $ G $. Es decir, $ H $ conserva una porción de los vértices y conexiones de $ G $.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos30.PNG?raw=true\" width=\"300\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69bd74e9",
   "metadata": {},
   "source": [
    "### **Subgrafo generador**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11b6386d",
   "metadata": {},
   "source": [
    "Si el conjunto de vértices de $ H $ es exactamente el mismo que el conjunto de vértices de $ G $, es decir, $ V(H) = V(G) $, decimos que $ H $ es un **subgrafo generador** de $ G $. En este caso, $ H $ incluye todos los vértices del grafo original $ G $, pero no necesariamente todas las aristas.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos31.PNG?raw=true\" width=\"300\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e8efe4f",
   "metadata": {},
   "source": [
    "### **Subgrafo inducido**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "772346d8",
   "metadata": {},
   "source": [
    "Dado un subconjunto de vértices $ X \\subseteq V(G) $, el **subgrafo inducido** por $ X $ es el subgrafo que contiene solo los vértices en $ X $ y las aristas entre esos vértices que existían en el grafo original $ G $. En otras palabras, en el subgrafo inducido, conservamos todas las aristas que están entre los vértices del conjunto $ X $, pero no incluimos vértices o aristas que no formen parte de $ X $.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos32.PNG?raw=true\" width=\"300\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f80a8a38",
   "metadata": {},
   "source": [
    "### **Notación: $ G - v $**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "281cc3a8",
   "metadata": {},
   "source": [
    "La notación $ G - v $ denota el **subgrafo** de $ G $ que se obtiene al eliminar un vértice $ v $ y todas las aristas asociadas a ese vértice. El resultado es un grafo con todos los vértices y aristas originales, excepto aquellos conectados a $ v $."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03b837b8",
   "metadata": {},
   "source": [
    "## **Isomorfismo de Grafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4b4f60d",
   "metadata": {},
   "source": [
    "Dos grafos $ G $ y $ H $ son **isomorfos** si, aunque puedan parecer diferentes en su representación visual o en la forma en que están organizados, en realidad tienen la **misma estructura**. Esto significa que hay una **correspondencia uno a uno** entre los vértices de $ G $ y los vértices de $ H $ que **conserva las conexiones** (aristas). En otras palabras, los grafos son equivalentes en términos de sus relaciones entre vértices."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "772eb923",
   "metadata": {},
   "source": [
    "### **Definición formal:**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1eab97e",
   "metadata": {},
   "source": [
    "- Dos grafos $ G $ y $ H $ son **isomorfos** si existe una función $ f $, que toma los vértices de $ G $ y los mapea de manera **biyectiva** (es decir, cada vértice de $ G $ corresponde a exactamente un vértice de $ H $, y viceversa), de modo que las conexiones entre los vértices se preserven. Esto significa que si dos vértices $ v $ y $ w $ están conectados por una arista en $ G $, entonces los vértices correspondientes $ f(v) $ y $ f(w) $ estarán conectados en $ H $.\n",
    "  \n",
    "- En notación, decimos que $ G = H $ si existe una función biyectiva $ f: V(G) \\rightarrow V(H) $ tal que $ (v, w) \\in E(G) $ si y solo si $ (f(v), f(w)) \\in E(H) $.\n",
    "\n",
    "Esto quiere decir que $ G $ y $ H $ tienen la misma estructura, aunque los nombres de los vértices o la disposición visual de los grafos puedan ser diferentes.\n",
    "\n",
    "**Ejemplo:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos33.PNG?raw=true\" width=\"750\" />\n",
    "</p>\n",
    "\n",
    "En la imagen, tenemos dos grafos $ G $ (a la izquierda) y $ H $ (a la derecha). A primera vista, podrían parecer diferentes, pero son **isomorfos**. La función $ f $ que describe el isomorfismo entre $ G $ y $ H $ se da como sigue:\n",
    "\n",
    "$$f(1) = 7, \\quad f(2) = 5, \\quad f(3) = 3, \\quad f(4) = 6, \\quad f(5) = 4, \\quad f(6) = 2, \\quad f(7) = 1$$\n",
    "\n",
    "Esto significa que:\n",
    "- El vértice 1 en $ G $ se corresponde con el vértice 7 en $ H $,\n",
    "- El vértice 2 en $ G $ se corresponde con el vértice 5 en $ H $,\n",
    "- Y así sucesivamente para los otros vértices.\n",
    "\n",
    "**¿Qué significa que la función \"preserva las adyacencias\"?**\n",
    "Decimos que la función $ f $ **preserva las adyacencias** porque si dos vértices están conectados en $ G $, entonces los vértices correspondientes en $ H $ también estarán conectados. Por ejemplo, si en $ G $, el vértice 1 está conectado al vértice 2, en $ H $, el vértice 7 (que corresponde al 1) estará conectado al vértice 5 (que corresponde al 2). Así se asegura que las conexiones entre vértices en ambos grafos son equivalentes.\n",
    "\n",
    "**Resumen:**\n",
    "- El **isomorfismo** entre grafos es una relación que nos dice que dos grafos, aunque puedan parecer distintos, son estructuralmente idénticos.\n",
    "- Dos grafos isomorfos tienen la misma cantidad de vértices y aristas, y las relaciones entre esos vértices son equivalentes.\n",
    "- En este caso, los grafos $ G $ y $ H $ de la imagen son isomorfos porque existe una correspondencia entre sus vértices que conserva las conexiones.\n",
    "\n",
    "Esta propiedad es importante porque, en muchas aplicaciones, lo que importa es la estructura subyacente del grafo, no los nombres específicos de los vértices o su disposición gráfica."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6dc01b3c",
   "metadata": {},
   "source": [
    "## **Grafos Completos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "62f1dc14",
   "metadata": {},
   "source": [
    "Un **grafo completo** $ G $ es un grafo en el que **todos los vértices están conectados entre sí**. Esto significa que, en un grafo completo, cualquier par de vértices distintos son adyacentes, es decir, siempre hay una arista entre ellos. Los grafos completos son una estructura muy densa, ya que incluyen la mayor cantidad posible de aristas para un conjunto dado de vértices.\n",
    "\n",
    "Cuando un grafo completo tiene $ n $ vértices, se denota como $ K_n $. El grafo completo más pequeño es el triángulo, que se llama $ K_3 $, ya que tiene 3 vértices, y todos ellos están conectados entre sí."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a6077b2",
   "metadata": {},
   "source": [
    "#### **Características de un Grafo Completo $ K_n $:**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b6a66e2",
   "metadata": {},
   "source": [
    "- **Número de vértices**: $ n $, es el número total de vértices en el grafo.\n",
    "- **Número de aristas** $ m_{K_n} $: El número total de aristas en un grafo completo con $ n $ vértices está dado por la fórmula:\n",
    "  $$\n",
    "  m_{K_n} = \\frac{n(n-1)}{2}\n",
    "  $$\n",
    "  Esto se debe a que cada vértice se conecta con todos los demás vértices, y no hay aristas repetidas.\n",
    "  \n",
    "- **Grado mínimo $ \\delta(K_n) $** y **grado máximo $ \\Delta(K_n) $**: En un grafo completo, todos los vértices tienen el mismo número de conexiones, que es exactamente $ n-1 $ (porque cada vértice está conectado a los otros $ n-1 $ vértices). Por lo tanto:\n",
    "  $$\n",
    "  \\delta(K_n) = \\Delta(K_n) = n-1\n",
    "  $$\n",
    "  Esto significa que en un grafo completo, el grado de todos los vértices es igual y corresponde al número de vértices restantes en el grafo.\n",
    "\n",
    "**Ejemplo con $ K_7 $:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos34.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "En la imagen, observamos el grafo completo con 7 vértices, denominado $ K_7 $. Este grafo tiene las siguientes propiedades:\n",
    "\n",
    "- **Número de vértices**: $ n = 7 $.\n",
    "- **Número de aristas**:\n",
    "  $$\n",
    "  m_{K_7} = \\frac{7(7-1)}{2} = \\frac{7 \\times 6}{2} = 21\n",
    "  $$\n",
    "  Por lo tanto, el grafo completo $ K_7 $ tiene 21 aristas.\n",
    "  \n",
    "- **Grado de cada vértice**: En $ K_7 $, cada vértice está conectado a otros 6 vértices, por lo que:\n",
    "  $$\n",
    "  \\delta(K_7) = \\Delta(K_7) = 6\n",
    "  $$\n",
    "  Esto significa que todos los vértices en $ K_7 $ tienen grado 6, ya que están conectados a los otros 6 vértices del grafo.\n",
    "\n",
    "En conclusión, un grafo completo es una estructura donde todos los vértices están conectados entre sí. Para $ n $ vértices, el número de aristas en un grafo completo es $ \\frac{n(n-1)}{2} $, y todos los vértices tienen un grado igual a $ n-1 $. Los grafos completos son útiles para modelar situaciones donde existe una conexión entre todos los elementos, como en una red donde todos los nodos están directamente comunicados entre sí."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87e541c7",
   "metadata": {},
   "source": [
    "## **Caminos en Grafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c16f969c",
   "metadata": {},
   "source": [
    "Un **camino** en un grafo $ G $ es una secuencia de vértices distintos $ P = v_1, v_2, \\ldots, v_k $ tales que cada vértice está conectado al siguiente en la secuencia por una arista. Formalmente, cada par consecutivo de vértices $ v_i $ y $ v_{i+1} $ debe estar conectado por una arista $ (v_i, v_{i+1}) \\in E(G) $, donde $ i = 1, \\ldots, k-1 $.\n",
    "\n",
    "En otras palabras, un camino es una lista de vértices a través de los cuales podemos \"viajar\" de uno a otro, siguiendo las conexiones (aristas) en el grafo, sin pasar por el mismo vértice más de una vez.\n",
    "\n",
    "**Cuerda en un Camino:** Una **cuerda** en un camino es una **arista adicional** que conecta dos vértices en el camino que no son consecutivos. En un camino $ P $, si dos vértices $ v_i $ y $ v_j $ están conectados por una arista, pero $ j \\neq i+1 $, entonces esta arista se llama una cuerda. Las cuerdas \"saltan\" vértices en el camino.\n",
    "\n",
    "**Camino Inducido:** Un **camino inducido** es un camino **sin cuerdas**. Esto significa que, además de que los vértices en el camino están conectados en secuencia por aristas, no hay conexiones adicionales entre vértices no consecutivos. Un camino inducido con $ k $ vértices se denota como $ P_k $.\n",
    "\n",
    "**Ejemplo**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos35.PNG?raw=true\" width=\"750\" />\n",
    "</p>\n",
    "\n",
    "En la imagen, observamos dos ejemplos:\n",
    "\n",
    "1. **Primer gráfico (a la izquierda)**: Aquí vemos un **camino inducido** de 4 vértices, lo que se denota como $ P_4 $. Todos los vértices están conectados en secuencia y no hay cuerdas (es decir, no hay aristas que conecten vértices no consecutivos).\n",
    "  \n",
    "2. **Segundo gráfico (a la derecha)**: En este caso, tenemos un camino donde se ha añadido una **cuerda** (la arista resaltada en rojo). Esta cuerda conecta dos vértices no consecutivos, rompiendo la condición de que el camino sea inducido.\n",
    "\n",
    "**Propiedades del Camino $ P_k $**\n",
    "- **Número de aristas** $ m_{P_k} $: En un camino inducido de $ k $ vértices, el número de aristas es $ k-1 $, ya que cada vértice, excepto los extremos, está conectado a dos vértices.\n",
    "  \n",
    "  $$\n",
    "  m_{P_k} = k-1\n",
    "  $$\n",
    "\n",
    "  Para $P_4$, el número de aristas es: \n",
    "\n",
    "  $$m_{P_4}=4-1=3$$\n",
    "\n",
    "- **Grado mínimo $ \\delta(P_k) $**: El grado mínimo de un vértice en un camino inducido es 1, ya que los vértices en los extremos del camino solo tienen una conexión (es decir, están conectados a un solo vértice).\n",
    "  \n",
    "  $$\n",
    "  \\delta(P_4) = 1\n",
    "  $$\n",
    "\n",
    "- **Grado máximo $ \\Delta(P_k) $**: El grado máximo en un camino inducido es 2, ya que los vértices que no son extremos están conectados a exactamente dos vértices.\n",
    "  \n",
    "  $$\n",
    "  \\Delta(P_4) = 2\n",
    "  $$\n",
    "\n",
    "Un **camino** es una secuencia de vértices conectados consecutivamente, y si no tiene cuerdas (aristas entre vértices no consecutivos), se llama un **camino inducido**. El número de aristas en un camino inducido de $ k $ vértices es $ k-1 $, los vértices de los extremos tienen grado 1, y el resto de los vértices tienen grado 2. Las cuerdas, como en el segundo gráfico, añaden aristas entre vértices no consecutivos y hacen que el camino deje de ser inducido.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ce2a028",
   "metadata": {},
   "source": [
    "## **Circuitos y Ciclos en Grafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2dc8f4bb",
   "metadata": {},
   "source": [
    "En la teoría de grafos, los **circuitos** y **ciclos** son tipos especiales de caminos cerrados que se forman cuando podemos empezar en un vértice, recorrer una serie de aristas, y regresar al vértice de inicio.\n",
    "\n",
    "- **Circuito:** Un **circuito** en un grafo $ G $ es una secuencia de vértices $ C = v_1, v_2, \\ldots, v_k $, donde el primer vértice es igual al último, es decir, $ v_1 = v_k $. La secuencia de vértices no tiene que ser necesariamente distinta, lo que significa que se puede pasar más de una vez por un vértice. Además, cada par consecutivo de vértices en el circuito $ (v_i, v_{i+1}) $ está conectado por una arista del grafo.\n",
    "\n",
    "- **Ciclo:** Un **ciclo** es un tipo especial de circuito. Se distingue de un circuito porque en un ciclo todos los vértices $ v_1, v_2, \\ldots, v_{k-1} $ son **distintos**, excepto el vértice de inicio y fin, es decir, $ v_1 = v_k $. Para que una secuencia de vértices sea un ciclo, debe tener al menos 3 vértices ($ k \\geq 3 $) y no repetir ningún vértice dentro de la secuencia, excepto el inicio y el fin.\n",
    "\n",
    "- **Cuerda en un Ciclo:** Una **cuerda** en un ciclo es una arista que conecta dos vértices no consecutivos del ciclo. La única excepción es la arista que conecta el primer y último vértice del ciclo, $ (v_1, v_k) $, que no se considera una cuerda.  \n",
    "\n",
    "- **Ciclo Inducido:** Un **ciclo inducido** es un ciclo que **no tiene cuerdas**. Es decir, los únicos vértices que están conectados son aquellos que son consecutivos en el ciclo, sin aristas adicionales que conecten vértices no adyacentes. El ciclo inducido de $ k $ vértices se denota como $ C_k $.\n",
    "\n",
    "**Ejemplo**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos36.PNG?raw=true\" width=\"750\" />\n",
    "</p>\n",
    "\n",
    "La imagen muestra tres grafos que ilustran circuitos y ciclos:\n",
    "\n",
    "1. **Primer gráfico (izquierda)**: Representa un **circuito**. Podemos observar que los vértices forman una secuencia cerrada, pero no todos los vértices son distintos, lo que lo convierte en un circuito, pero no en un ciclo.\n",
    "  \n",
    "2. **Segundo gráfico (centro)**: Representa un **ciclo inducido** sin cuerdas. Todos los vértices son distintos y están conectados en una secuencia cerrada, lo que lo convierte en un ciclo $ C_k $. No hay cuerdas que conecten vértices no consecutivos.\n",
    "\n",
    "3. **Tercer gráfico (derecha)**: Es un ciclo al que se le ha añadido una **cuerda** (resaltada en rojo). Este ciclo tiene una arista adicional que conecta dos vértices que no son consecutivos en la secuencia del ciclo, lo que rompe la condición de ser un **ciclo inducido**.\n",
    "\n",
    "**Propiedades del Ciclo $ C_k $**\n",
    "- **Número de aristas** $ m_{C_k} $: En un ciclo de $ k $ vértices, el número de aristas es igual a $ k $, ya que para cerrar el ciclo, se necesita una arista adicional que conecte el último vértice al primero.\n",
    "  $$\n",
    "  m_{C_k} = k\n",
    "  $$\n",
    "\n",
    "- **Grado mínimo $ \\delta(C_k) $**: El grado mínimo en un ciclo es siempre 2, ya que cada vértice está conectado a dos vértices, uno en cada lado.\n",
    "  $$\n",
    "  \\delta(C_k) = 2\n",
    "  $$\n",
    "\n",
    "- **Grado máximo $ \\Delta(C_k) $**: El grado máximo en un ciclo es también 2, ya que todos los vértices en un ciclo tienen exactamente dos conexiones.\n",
    "  $$\n",
    "  \\Delta(C_k) = 2\n",
    "  $$\n",
    "\n",
    "Un **circuito** es una secuencia cerrada de vértices, donde $ v_1 = v_k $. Si los vértices son todos distintos (excepto el primero y el último), se trata de un **ciclo**. Un **ciclo inducido** es un ciclo sin cuerdas, es decir, sin aristas adicionales que conecten vértices no consecutivos. En un ciclo $ C_k $, hay $ k $ aristas, y todos los vértices tienen un grado igual a 2."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1594c751",
   "metadata": {},
   "source": [
    "## **Grafos Bipartitos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6f283b0",
   "metadata": {},
   "source": [
    "Un **grafo bipartito** es un grafo en el que los vértices se pueden dividir en dos conjuntos disjuntos, $ V_1 $ y $ V_2 $, de manera que todas las aristas conectan un vértice de $ V_1 $ con un vértice de $ V_2 $. No hay conexiones entre vértices dentro del mismo subconjunto, es decir, no existen aristas entre vértices de $ V_1 $ o entre vértices de $ V_2 $.\n",
    "\n",
    "Cuando el grafo bipartito es **completo**, cada vértice de $ V_1 $ está conectado a **todos los vértices** de $ V_2 $. Este tipo de grafo se denota como $ K_{r,s} $, donde $ r = |V_1| $ (el número de vértices en $ V_1 $) y $ s = |V_2| $ (el número de vértices en $ V_2 $)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9120d9a9",
   "metadata": {},
   "source": [
    "#### **Propiedades de un Grafo Bipartito Completo $ K_{r,s} $:**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7783f05",
   "metadata": {},
   "source": [
    "1. **Número total de vértices** $ n_{K_{r,s}} $:\n",
    "   $$\n",
    "   n_{K_{r,s}} = r + s\n",
    "   $$\n",
    "   Es la suma del número de vértices en $ V_1 $ y $ V_2 $.\n",
    "\n",
    "2. **Número de aristas** $ m_{K_{r,s}} $:\n",
    "   $$\n",
    "   m_{K_{r,s}} = r \\times s\n",
    "   $$\n",
    "   Dado que cada vértice en $ V_1 $ está conectado con todos los vértices de $ V_2 $, el número total de aristas es el producto del número de vértices en los dos subconjuntos.\n",
    "\n",
    "3. **Grado mínimo** $ \\delta(K_{r,s}) $:\n",
    "   $$\n",
    "   \\delta(K_{r,s}) = \\min(r, s)\n",
    "   $$\n",
    "   El grado mínimo es el menor número de conexiones, que corresponde al número de vértices en el subconjunto opuesto más grande. Por ejemplo, los vértices en $ V_1 $ tienen grado $ s $, y los vértices en $ V_2 $ tienen grado $ r $.\n",
    "\n",
    "4. **Grado máximo** $ \\Delta(K_{r,s}) $:\n",
    "   $$\n",
    "   \\Delta(K_{r,s}) = \\max(r, s)\n",
    "   $$\n",
    "   El grado máximo es el mayor número de conexiones, que corresponde al número de vértices en el subconjunto opuesto más pequeño.\n",
    "\n",
    "**Ejemplo:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos37.PNG?raw=true\" width=\"750\" />\n",
    "</p>\n",
    "\n",
    "1. **Primer gráfico (izquierda)**:\n",
    "   Este grafo **no es bipartito completo**. Está compuesto por dos subconjuntos de vértices: $ V_1 $ con **3 vértices** y $ V_2 $ con **4 vértices**. Aunque es bipartito, no todas las conexiones posibles están presentes entre $ V_1 $ y $ V_2 $. Solo algunos vértices de $ V_1 $ están conectados con algunos vértices de $ V_2 $, lo que lo convierte en un grafo bipartito, pero no en uno completo.\n",
    "\n",
    "   - $ V_1 = \\{ \\text{los 3 vértices en la izquierda} \\} $\n",
    "   - $ V_2 = \\{ \\text{los 4 vértices en la derecha} \\} $\n",
    "   - No todas las conexiones posibles entre $ V_1 $ y $ V_2 $ están presentes.\n",
    "\n",
    "2. **Segundo gráfico (derecha)**:\n",
    "   Este es un **grafo bipartito completo** $ K_{3,4} $. Tiene **3 vértices en $ V_1 $** y **4 vértices en $ V_2 $**, y todos los vértices de $ V_1 $ están conectados a todos los vértices de $ V_2 $, lo que lo convierte en un ejemplo claro de un grafo bipartito completo.\n",
    "\n",
    "   - **Número total de vértices**:\n",
    "     $$\n",
    "     n_{K_{3,4}} = 3 + 4 = 7\n",
    "     $$\n",
    "   - **Número de aristas**:\n",
    "     $$\n",
    "     m_{K_{3,4}} = 3 \\times 4 = 12\n",
    "     $$\n",
    "   - **Grado mínimo**:\n",
    "     $$\n",
    "     \\delta(K_{3,4}) = \\min(3, 4) = 3\n",
    "     $$\n",
    "   - **Grado máximo**:\n",
    "     $$\n",
    "     \\Delta(K_{3,4}) = \\max(3, 4) = 4\n",
    "     $$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c845d629",
   "metadata": {},
   "source": [
    "#### **Teorema:** Un grafo $G$ es bipartito $\\Leftrightarrow$ todos sus circuitos son pares."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df8af664",
   "metadata": {},
   "source": [
    "## **Conexión en Grafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "234eda8c",
   "metadata": {},
   "source": [
    "En la teoría de grafos, la **conexión** es una propiedad clave que nos permite identificar qué tan relacionados están los vértices dentro de un grafo. En términos simples, un grafo es **conexo** si existe un camino entre cada par de vértices, lo que significa que todos los vértices están conectados directa o indirectamente por aristas.\n",
    "\n",
    "#### **Componente Conexa**\n",
    "\n",
    "Una **componente conexa** de un grafo es un **subgrafo conexo maximal**. Esto significa que es un conjunto de vértices y aristas donde cualquier par de vértices está conectado por un camino, pero si añadimos más vértices o aristas, el conjunto ya no satisface la propiedad de ser conexo.\n",
    "\n",
    "- Un conjunto es **maximal** con respecto a una propiedad $ P $ si satisface la propiedad $ P $ y no puede expandirse sin perder esa propiedad. En el caso de las componentes conexas, un subgrafo es maximal si es conexo y no se puede añadir ningún otro vértice del grafo sin romper la condición de conexión.\n",
    "\n",
    "**Ejemplos de Componentes Conexas:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos38.PNG?raw=true\" width=\"1000\" />\n",
    "</p>\n",
    "\n",
    "A continuación, identificamos las **componentes conexas** en los distintos grafos que aparecen en la imagen proporcionada.\n",
    "\n",
    "1. **Primer grafo (izquierda)**:\n",
    "   - El grafo tiene **dos componentes conexas**, la componente formada por los vértices $\\{1, 2, 7\\}$ y la formada por los vértices $\\{3, 4, 5\\}$.\n",
    "\n",
    "2. **Segundo grafo (segundo desde la izquierda)**:\n",
    "   - Este grafo tiene **una única componente conexa**. Todos los vértices del $\\{1\\}$ al $\\{7\\}$ están conectados directa o indirectamente por caminos, formando una estructura conexa.\n",
    "\n",
    "**Ejercicio:**\n",
    "\n",
    "Revisa los otros grafos en la figura y analiza cuántas componentes conexas tienen cada uno.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7fdf2ce",
   "metadata": {},
   "source": [
    "### **Componenente Conexa Maximal:**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04de0ebc",
   "metadata": {},
   "source": [
    "Un conjunto $ S $ es **maximal** respecto a una propiedad $ P $ si:\n",
    "- $ S $ satisface la propiedad $ P $, y\n",
    "- No es posible agregar más elementos a $ S $ sin dejar de cumplir $ P $.\n",
    "\n",
    "En el contexto de componentes conexas, una **componente conexa maximal** es un subgrafo en el que todos los vértices están conectados entre sí, y no se puede agregar ningún vértice adicional sin perder esa conexión. Esto significa que la componente contiene el mayor número posible de vértices que están conectados entre sí.\n",
    "\n",
    "**Ejemplos de Maximal:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos39.PNG?raw=true\" width=\"1000\" />\n",
    "</p>\n",
    "\n",
    "1. **Primer gráfico (izquierda)**:\n",
    "   - Aquí vemos **dos componentes conexas maximal**.\n",
    "   - La primera componente maximal es $ \\{1, 2, 7\\} $, resaltada en rojo. Todos estos vértices están conectados entre sí, y no es posible agregar más vértices a esta componente sin perder la conexión.\n",
    "   - La segunda componente maximal es $ \\{3, 4, 5, 6\\} $, resaltada en azul. Estos vértices están conectados entre sí y forman una componente conexa maximal. No se puede agregar, por ejemplo, $ \\{1\\} $ o $ \\{2\\} $, ya que no están conectados con los vértices de esta componente.\n",
    "\n",
    "2. **Segundo gráfico (segundo desde la izquierda)**:\n",
    "   - Este es un **grafo completamente conexo**, lo que significa que todos los vértices $ \\{1, 2, 3, 4, 5, 6, 7\\} $ están conectados entre sí. Por lo tanto, la **componente conexa maximal** aquí es todo el grafo, ya que no es posible añadir más vértices sin perder la propiedad de ser conexo.\n",
    "\n",
    "**Ejercicio:**\n",
    "\n",
    "Revisa los otros grafos en la figura y analiza sus componentes maximal (pueden existir más de una?)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03a7a58a",
   "metadata": {},
   "source": [
    "### **Componenente Conexa Minimal:**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8db10664",
   "metadata": {},
   "source": [
    "Un conjunto $ S $ es **minimal** respecto a una propiedad $ P $ si:\n",
    "- $ S $ satisface la propiedad $ P $, y\n",
    "- No es posible eliminar ningún elemento de $ S $ sin dejar de cumplir $ P $.\n",
    "\n",
    "En el contexto de componentes conexas, un **subgrafo conexo minimal** es el conjunto más pequeño de vértices que aún sigue siendo conexo. Si eliminamos cualquier vértice, el subgrafo ya no será conexo.\n",
    "\n",
    "\n",
    "**Ejemplos de Minimal:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos39.PNG?raw=true\" width=\"1000\" />\n",
    "</p>\n",
    "\n",
    "1. **Primer gráfico (izquierda)**:\n",
    "   - En este grafo, el conjunto $ \\{1, 2, 7\\} $ es **minimal** respecto a la conexión, porque si eliminamos cualquiera de los vértices, el subgrafo ya no será conexo.\n",
    "   - De manera similar, el conjunto $ \\{3, 4, 5, 6\\} $ es minimal porque si quitamos algún vértice, no habrá un camino entre los restantes.\n",
    "\n",
    "2. **Segundo gráfico (segundo desde la izquierda)**:\n",
    "   - Aquí, cualquier conjunto de al menos dos vértices es minimal respecto a la conexión. Por ejemplo, el conjunto $ \\{1, 2\\} $ es minimal, ya que si eliminamos cualquiera de los vértices, no habrá más aristas conectando al otro vértice.\n",
    "\n",
    "**Ejercicio:**\n",
    "\n",
    "Revisa los otros grafos en la figura y analiza sus componentes minimal (pueden existir más de una?)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf2bbfb6",
   "metadata": {},
   "source": [
    "### **Observaciones:**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5393312",
   "metadata": {},
   "source": [
    "1. Todo vértice de un grafo pertenece a alguna componente conexa.\n",
    "2. Un grafo es conexo si y sólo si tiene una sola componente conexa.\n",
    "3. Dos componentes conexas distintas de un grafo son disjuntas."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5019993e",
   "metadata": {},
   "source": [
    "### **Conexión y Puntos de Corte en Grafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ba80acf",
   "metadata": {},
   "source": [
    "En la teoría de grafos, un **punto de corte** (o **vértice de corte**) es un vértice cuya eliminación provoca que el grafo, antes conexo, se divida en más componentes conexas. Es decir, al retirar ese vértice, el grafo se separa en varias partes que antes estaban conectadas. Los puntos de corte son clave para comprender la estructura de un grafo, ya que al ser eliminados, desconectan secciones clave del mismo.\n",
    "\n",
    "- Un vértice $ v $ es un **punto de corte** en un grafo $ G $ si, al eliminar $ v $, el grafo resultante $ G - v $ tiene más componentes conexas que el grafo original $ G $. \n",
    "- Esto significa que al quitar $ v $, algunos vértices que antes estaban conectados entre sí ahora se desconectan y pasan a estar en componentes diferentes.\n",
    "\n",
    "**Identificación de Puntos de Corte en Grafos:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos41.PNG?raw=true\" width=\"1000\" />\n",
    "</p>\n",
    "\n",
    "Veamos cada uno de los grafos en la imagen para identificar sus puntos de corte.\n",
    "\n",
    "1. **Primer gráfico (izquierda)**:\n",
    "   - **Vértice $2$** es un punto de corte. Si quitamos el vértice $2$, los vértices $ 1 $ y $ 7 $ se desconectan, formando dos componentes conexas separadas.\n",
    "   - Si se elimina otro vértice, por ejemplo el **Vértice $4$** los vértices vértices $ 5 $, $3$ y  $ 6 $ permanecerán conectados.\n",
    "   - Por lo tanto, **$2$** es el único punto de corte en este grafo.\n",
    "\n",
    "2. **Segundo gráfico (segundo desde la izquierda)**:\n",
    "   - Este es un **grafo bipartito completo**, lo que significa que todos los vértices están muy interconectados. No hay ningún vértice cuya eliminación aumente el número de componentes conexas, ya que cada vértice tiene múltiples conexiones.\n",
    "   - **No hay puntos de corte** en este grafo.\n",
    "\n",
    "3. **Tercer gráfico (centro)**:\n",
    "   - Este es un **grafo completo**, lo que significa que cada vértice está conectado a todos los demás vértices. Al eliminar cualquier vértice, los demás vértices seguirán conectados entre sí.\n",
    "   - Por lo tanto, **no hay puntos de corte** en este grafo.\n",
    "\n",
    "4. **Cuarto gráfico (segundo desde la derecha)**:\n",
    "   - ¿Qué vértices son puntos de corte en estes grafo?\n",
    "\n",
    "5. **Quinto gráfico (derecha)**:\n",
    "   - ¿Qué vértices son puntos de corte en estes grafo?\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos42.PNG?raw=true\" width=\"1000\" />\n",
    "</p>\n",
    "\n",
    "Un grafo es **biconexo** si es conexo y sin puntos de corte. ¿Cuáles de los grafos anteriores son biconexos?  \n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos43.PNG?raw=true\" width=\"1000\" />\n",
    "</p>\n",
    "\n",
    "Un **bloque** o **componente biconexa** de un grafo es un **subgrafo biconexo maximal**. ¿Cuáles son los bloques en estos grafos?\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos44.PNG?raw=true\" width=\"1000\" />\n",
    "</p>\n",
    "\n",
    "**Observaciones**\n",
    "\n",
    "1. **Un grafo es biconexo si y solo si tiene un solo bloque**:\n",
    "   - Un **bloque** es un subgrafo **maximal biconexo** de un grafo, es decir, es una parte del grafo donde no hay puntos de corte, y cada parte está bien conectada. Un **grafo biconexo** es simplemente un grafo que no tiene ningún punto de corte. \n",
    "   - Esto significa que si un grafo es biconexo, entonces todo el grafo es un único bloque. Si hay más de un bloque, el grafo no es biconexo porque contiene puntos de corte que separan esos bloques.\n",
    "\n",
    "2. **Dos bloques de un grafo comparten a lo sumo un vértice. En particular, cada arista pertenece a un único bloque**:\n",
    "   - Si un grafo tiene más de un bloque (es decir, no es biconexo), entonces dos bloques distintos solo pueden compartir un vértice en común. Ese vértice compartido es un **punto de corte**. \n",
    "   - Además, cada **arista** (conexión entre dos vértices) solo puede pertenecer a un único bloque. Esto significa que un bloque es una unidad indivisible en cuanto a su estructura de conexión.\n",
    "\n",
    "### **Teorema**\n",
    "\n",
    "Dado un grafo conexo $ G $, si tenemos un vértice $ v $, las siguientes tres afirmaciones son equivalentes, lo que significa que si una es cierta, las otras dos también lo son:\n",
    "\n",
    "1. **El vértice $ v $ es un punto de corte de $ G $**:\n",
    "   - Un **punto de corte** es un vértice que, al ser eliminado, desconecta el grafo en más componentes. Es un vértice crucial que conecta diferentes partes del grafo. \n",
    "\n",
    "2. **Existen vértices $ u $ y $ w $, distintos de $ v $, tales que $ v $ está en todo camino entre $ u $ y $ w $**:\n",
    "   - Esta afirmación significa que $ v $ es la única forma de conectar a los vértices $ u $ y $ w $. En otras palabras, no hay otro camino entre $ u $ y $ w $ sin pasar por $ v $. Esto implica que si quitamos el vértice $ v $, los vértices $ u $ y $ w $ se desconectarán.\n",
    "\n",
    "3. **Existe una partición de $ V-v $ en conjuntos $ U $ y $ W $ tales que para todo $ u \\in U $ y $ w \\in W $, el punto $ v $ está en todo camino entre $ u $ y $ w $**:\n",
    "   - Esta afirmación es similar a la segunda, pero habla de una partición más general de los vértices que quedan si eliminamos $ v $. Los conjuntos $ U $ y $ W $ representan dos grupos de vértices, y cualquier camino entre un vértice de $ U $ y un vértice de $ W $ tiene que pasar por $ v $. Esto significa que $ v $ actúa como un **punto de corte** que mantiene conectadas esas dos partes del grafo.\n",
    "\n",
    "**Ejemplo con la imagen:**\n",
    "\n",
    "En los grafos donde vemos puntos de corte (vértices rojos), esos vértices son cruciales porque cumplen las condiciones del teorema. Por ejemplo, en el primer grafo de la izquierda:\n",
    "- El vértice $ 2 $ es un punto de corte porque si lo eliminamos, los vértices $ 1 $ y $ 4 $ se desconectan, cumpliendo la condición del teorema. En este caso, $ U $ podría ser el conjunto de vértices $ \\{1\\} $, y $ W $ podría ser el conjunto $ \\{4, 5, 6, 7\\} $.\n",
    "\n",
    "Por otro lado, en un grafo biconexo como el tercer grafo (el grafo completo), no hay puntos de corte, lo que significa que **no hay un vértice que desconecte el grafo** si lo eliminamos, y todo el grafo es un único bloque.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9929a640",
   "metadata": {},
   "source": [
    "### **Conexión en grafos: Puentes**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b67c2183",
   "metadata": {},
   "source": [
    "Un **puente** de un grafo $ G $ es una **arista** $ e $ tal que si eliminamos esa arista del grafo, el número de componentes conexas aumenta. En otras palabras, la eliminación de un puente **desconecta** parte del grafo.\n",
    "  \n",
    "Por ejemplo, si tienes un grafo y eliminas una arista que es un puente, el grafo puede dividirse en dos o más partes que ya no están conectadas entre sí.\n",
    "\n",
    "Algunas preguntas que resultand de lo anterior podrían ser:\n",
    "\n",
    "1. **¿Puede ser que $ G - v $ (es decir, $ G $ sin el vértice $ v $) tenga más de dos componentes conexas si $ v $ es un punto de corte?**\n",
    "   - Sí, esto puede suceder. Si $ v $ es un **punto de corte**, eliminarlo puede desconectar el grafo en varias partes. En un caso extremo, como en un árbol, eliminar un solo vértice puede crear múltiples componentes. Por ejemplo, si el vértice $ v $ conecta varias ramas del grafo, su eliminación podría desconectar varias partes del grafo.\n",
    "\n",
    "2. **¿Puede ser que $ G - e $ (es decir, $ G $ sin la arista $ e $) tenga más de dos componentes conexas si $ e $ es un puente?**\n",
    "   - No. Si $ e $ es un **puente**, eliminarlo siempre divide el grafo en exactamente **dos** componentes conexas. Esto es porque el puente conecta dos partes del grafo, y al eliminarlo, esas dos partes se desconectan, pero no se generan más de dos componentes.\n",
    "\n",
    "3. **¿Existe algún grafo biconexo que tenga un puente?**\n",
    "   - **No, excepto por el grafo formado por una única arista.**\n",
    "   - Si un grafo es **biconexo**, por definición no tiene puntos de corte. Un **puente** introduce puntos de corte, ya que elimina la conexión entre dos partes del grafo. La única excepción es un grafo muy simple formado por dos vértices y una sola arista entre ellos. Este grafo es biconexo porque no tiene puntos de corte, pero su única arista es también un puente, ya que eliminarla desconectaría el grafo.\n",
    "\n",
    "### **Teorema:**\n",
    "\n",
    "Dado un grafo $ G $ conexo y una arista $ e = (i, j) $, las siguientes tres afirmaciones son **equivalentes**, lo que significa que si una es verdadera, las otras dos también lo son:\n",
    "\n",
    "1. **La arista $ e $ es un puente de $ G $**:\n",
    "   - Esto significa que si eliminamos la arista $ e $, el grafo se desconecta, creando dos componentes conexas.\n",
    "\n",
    "2. **La arista $ e $ no está en ningún ciclo de $ G $**:\n",
    "   - Esta afirmación nos dice que si $ e $ es un puente, no puede formar parte de un ciclo. Si $ e $ formara parte de un ciclo, podríamos eliminarla y aún así habría otro camino para conectar los vértices del ciclo. Por lo tanto, si $ e $ es un puente, **no puede** haber un ciclo que la incluya.\n",
    "\n",
    "3. **Existen vértices $ u $ y $ v $ tales que $ e $ está en todo camino entre $ u $ y $ v $**:\n",
    "   - Esta afirmación significa que la arista $ e $ es crucial para conectar los vértices $ u $ y $ v $. Si eliminamos $ e $, ya no existe ningún camino entre $ u $ y $ v $, lo que implica que $ e $ es un puente.\n",
    "\n",
    "En resumen:\n",
    "\n",
    "- Un **puente** es una arista que, al eliminarla, desconecta el grafo. Esto ocurre porque esa arista no está en ningún ciclo y conecta partes del grafo que, sin ella, quedan separadas.\n",
    "\n",
    "- Un **grafo biconexo**, por definición, no tiene puentes, ya que un puente implica la existencia de un punto de corte, y los grafos biconexos no tienen puntos de corte. La única excepción es un grafo formado por dos vértices y una única arista, donde la arista es un puente, pero no hay puntos de corte."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bdb515e",
   "metadata": {},
   "source": [
    "## **Distancia en Grafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5da61e5d",
   "metadata": {},
   "source": [
    "En los grafos, la **distancia** entre dos vértices se refiere al número de aristas que hay en el **camino más corto** que los conecta. Este concepto nos ayuda a medir la proximidad entre dos vértices dentro del grafo.\n",
    "\n",
    "- **Longitud de un camino**: La longitud de un camino es simplemente el número de aristas que lo componen. Por ejemplo, si caminas desde un vértice $ v $ hasta otro vértice $ w $ y pasas por tres aristas, la longitud de ese camino es $3$.\n",
    "  \n",
    "- **Distancia entre dos vértices**: La **distancia** entre dos vértices $ v $ y $ w $ en un grafo $ G $, denotada como $ d_G(v, w) $, es la longitud del **camino más corto** entre $ v $ y $ w $. Si el contexto no es ambiguo, podemos simplemente escribir $ d(v, w) $.\n",
    "\n",
    "**Ejemplo de la Distancia entre 1 y 5:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos40.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "En el grafo de la imagen, queremos calcular la distancia entre los vértices **1** y **5**.\n",
    "\n",
    "- Podemos observar que para ir del vértice **1** al vértice **5**, hay varios caminos posibles:\n",
    "  - Camino 1: $ 1 \\to 2 \\to 4 \\to 5 $ con una longitud de 3 aristas.\n",
    "  - Camino 2: $ 1 \\to 2 \\to 4 \\to 6 \\to 5 $ con una longitud de 4 aristas.\n",
    "  - Camino 3: $ 1 \\to 2 \\to 7 \\to 4 \\to 5 $ con una longitud de 4 aristas. \n",
    "  - Camino 4: $ 1 \\to 2 \\to 7 \\to 6 \\to 5 $ con una longitud de 4 aristas.\n",
    "  - Camino 5: $ 1 \\to 2 \\to 7 \\to 6 \\to 3 \\to 5 $ con una longitud de 5 \n",
    "\n",
    "El **camino más corto** es el primero, que tiene una longitud de 3 aristas. Por lo tanto, la distancia entre los vértices $ 1 $ y $ 5 $ es:\n",
    "\n",
    "$$\n",
    "d(1, 5) = 3\n",
    "$$\n",
    "\n",
    "### **Disco de Radio $ k $ en Grafos**\n",
    "\n",
    "El **disco $ D_k(v) $** de centro $ v $ y radio $ k $ es el conjunto de vértices que están a una distancia menor o igual a $ k $ de $ v $. Es como una \"esfera\" alrededor del vértice $ v $, que incluye a todos los vértices que se pueden alcanzar desde $ v $ con un número de pasos menor o igual a $ k $.\n",
    "\n",
    "**Ejemplo de Discos con Centro en 1:**\n",
    "\n",
    "Consideremos el vértice **1** como el centro y veamos los discos $ D_k(1) $ para diferentes valores de $ k $.\n",
    "\n",
    "- **Disco $ D_0(1) $** (radio 0): Este disco solo incluye al vértice $ 1 $ (el centro), ya que la distancia a sí mismo es 0.\n",
    "  \n",
    "  $$\n",
    "  D_0(1) = \\{ 1 \\}\n",
    "  $$\n",
    "\n",
    "- **Disco $ D_1(1) $** (radio 1): Este disco incluye los vértices que están a una distancia de 1 arista del vértice 1. En este caso, el vértice conectado directamente a 1 es el vértice 2.\n",
    "\n",
    "  $$\n",
    "  D_1(1) = \\{ 1, 2 \\}\n",
    "  $$\n",
    "\n",
    "- **Disco $ D_2(1) $** (radio 2): Aquí incluimos todos los vértices que están a una distancia de 2 aristas o menos de 1. Desde el vértice 1, podemos llegar al vértice 4 a través de 2 aristas (por el camino $ 1 \\to 2 \\to 4 $).\n",
    "\n",
    "  $$\n",
    "  D_2(1) = \\{ 1, 2, 4 \\}\n",
    "  $$\n",
    "\n",
    "- **Disco $ D_3(1) $** (radio 3): A una distancia de 3 aristas desde el vértice 1, podemos llegar a los vértices 5, 6 y 7. Por ejemplo, para llegar al vértice 5, tomamos el camino $ 1 \\to 2 \\to 4 \\to 5 $, que tiene longitud 3.\n",
    "\n",
    "  $$\n",
    "  D_3(1) = \\{ 1, 2, 4, 5, 6, 7 \\}\n",
    "  $$\n",
    "\n",
    "**Resumen:**\n",
    "\n",
    "- La **distancia** entre dos vértices es la longitud del camino más corto que los conecta.\n",
    "- En el grafo, la distancia entre los vértices 1 y 5 es $ d(1, 5) = 3 $.\n",
    "- El **disco $ D_k(v) $** es el conjunto de vértices que están a una distancia menor o igual a $ k $ de $ v $.\n",
    "  - Ejemplo de discos con centro en el vértice 1:\n",
    "    - $ D_0(1) = \\{1\\} $\n",
    "    - $ D_1(1) = \\{1, 2\\} $\n",
    "    - $ D_2(1) = \\{1, 2, 4\\} $\n",
    "    - $ D_3(1) = \\{1, 2, 4, 5, 6, 7\\} $"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3af962d5",
   "metadata": {},
   "source": [
    "## **Árboles en grafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0d71527",
   "metadata": {},
   "source": [
    "### **Árbol**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c483d60",
   "metadata": {},
   "source": [
    "Un **árbol** es un tipo especial de grafo que tiene las siguientes características:\n",
    "\n",
    "1. **Conexidad**: Un árbol es **conexo**, lo que significa que para cualquier par de vértices en el árbol, existe al menos un camino que los conecta. En otras palabras, no hay vértices aislados; todos los vértices están conectados entre sí.\n",
    "\n",
    "2. **Acilicidad**: Un árbol es **acíclico**, lo que significa que no contiene **ciclos**. Un ciclo ocurre cuando puedes empezar en un vértice, recorrer varias aristas, y regresar al mismo vértice sin repetir ninguna arista. En un árbol, esto no es posible: no puedes recorrer el grafo y volver al mismo punto sin repetir caminos, lo que asegura que no hay ciclos.\n",
    "\n",
    "### **Propiedades clave de los árboles:**\n",
    "\n",
    "- Un **árbol con $n$ vértices** siempre tiene exactamente **$n - 1$ aristas**. Esto se debe a que la ausencia de ciclos restringe el número de conexiones posibles, y la conexidad asegura que todos los vértices están conectados.\n",
    "  \n",
    "- Los vértices de **grado 1** (vértices con una sola conexión) se llaman **hojas**. Estos vértices están en los extremos del árbol y no conectan a otros más que a un vértice vecino.\n",
    "\n",
    "**Ejemplo:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos45.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "En la imagen se muestra un grafo que **es un árbol**, porque:\n",
    "- El grafo es **conexo**, lo que significa que podemos encontrar un camino entre cualquier par de vértices.\n",
    "- El grafo es **acíclico**, ya que no existe ningún ciclo (camino cerrado que permita volver al mismo vértice sin repetir aristas)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c6a20a1",
   "metadata": {},
   "source": [
    "### **Bosque en Grafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "120c1493",
   "metadata": {},
   "source": [
    "Un **bosque** es un grafo especial que se caracteriza por ser **acíclico**, lo que significa que no contiene **ciclos**. Además, un bosque es la **unión disjunta** de varios **árboles**, lo que significa que está compuesto por varias estructuras de árboles independientes que no están conectadas entre sí.\n",
    "\n",
    "**Propiedades de un bosque:**\n",
    "1. **Acilicidad**: Un bosque, al igual que un árbol, es un grafo que no contiene ciclos. Esto significa que no es posible empezar en un vértice, seguir varias aristas, y regresar al mismo vértice sin repetir ninguna arista.\n",
    "   \n",
    "2. **Unión disjunta de árboles**: Un bosque puede estar formado por varios **árboles** que no están conectados entre sí. Cada componente del bosque es un árbol individual. Un solo árbol también puede considerarse un bosque con una única componente.\n",
    "\n",
    "3. **Conexión parcial**: Mientras que un árbol es completamente conexo, un bosque no necesariamente lo es. Puede haber múltiples componentes, cada una de las cuales es un árbol, pero no todas están conectadas entre sí.\n",
    "\n",
    "**Ejemplo:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos46.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "En la imagen se puede ver un **bosque**:\n",
    "- El grafo se divide en dos partes que no están conectadas entre sí. Cada una de estas partes es un árbol, ya que son acíclicos y conexos dentro de sus componentes.\n",
    "- La primera parte (arriba a la izquierda) es un árbol porque es conexo y no tiene ciclos.\n",
    "- La segunda parte (abajo a la derecha) también es un árbol más pequeño, ya que no tiene ciclos y está completamente conectado dentro de su subgrafo.\n",
    "\n",
    "Dado que estas dos partes no están conectadas entre sí, pero ambas son árboles, el conjunto completo es un **bosque**. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ffeb8f6",
   "metadata": {},
   "source": [
    "### **Hoja en un Grafo**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c85dc26a",
   "metadata": {},
   "source": [
    "En la teoría de grafos, una **hoja** es un vértice especial que tiene grado 1. Esto significa que la hoja está conectada a exactamente un solo vértice mediante una única arista.\n",
    "\n",
    "1. **Grado de un vértice**: El **grado** de un vértice es el número de aristas que inciden en él, es decir, la cantidad de conexiones que tiene con otros vértices.\n",
    "   \n",
    "2. **Hoja**: Si un vértice tiene grado 1, significa que está conectado a exactamente un vértice, lo que lo convierte en una **hoja**. Las hojas son típicamente los vértices más externos de un grafo, ya que solo están conectados a un vértice vecino.\n",
    "\n",
    "**Ejemplo:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos47.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "En la imagen proporcionada, los vértices que están resaltados en **verde** son **hojas** porque cumplen con la condición de tener grado 1. Esto significa que cada uno de estos vértices está conectado a un único vértice vecino.\n",
    "\n",
    "- **Parte superior**: Los vértices en verde tienen solo una conexión, lo que los convierte en hojas. Estos vértices son los extremos de las ramas de esta parte del grafo.\n",
    "- **Parte inferior**: De igual manera, en la parte inferior del grafo, los vértices resaltados en verde son hojas porque están conectados solo a un vértice vecino, formando las hojas de las ramas de este subgrafo.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a858f284",
   "metadata": {},
   "source": [
    "### **Árbol Generador en un Grafo**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a30cf6d",
   "metadata": {},
   "source": [
    "Se define como un **subgrafo generador** de $ G $ que además cumple con las propiedades de ser un **árbol**. \n",
    "\n",
    "1. **Subgrafo generador**: Un subgrafo generador de un grafo $ G $ es un subgrafo que contiene todos los vértices de $ G $. Es decir, el subgrafo tiene el mismo conjunto de vértices que el grafo original, pero puede tener menos aristas.\n",
    "   \n",
    "2. **Árbol**: Un subgrafo es un **árbol** si es **conexo** (es decir, existe un camino entre cualquier par de vértices) y es **acíclico** (no contiene ciclos). En un árbol, no es posible empezar en un vértice, recorrer varias aristas, y regresar al mismo vértice sin repetir aristas.\n",
    "\n",
    "Entonces, un **árbol generador** es un subgrafo que:\n",
    "- Contiene **todos los vértices** del grafo original $ G $.\n",
    "- No tiene ciclos (es un árbol).\n",
    "- Es conexo (todos los vértices están conectados).\n",
    "\n",
    "**Ejemplo:**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos48.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "En la imagen, podemos ver un grafo completo (todas las conexiones están en gris), y sobre este, el **árbol generador** se resalta en **verde**:\n",
    "- El **árbol generador** verde contiene todos los vértices del grafo original.\n",
    "- El subgrafo verde es **acíclico**, ya que no existe ningún ciclo en las aristas resaltadas.\n",
    "- Además, el subgrafo verde es **conexo**, ya que todos los vértices están conectados entre sí a través de las aristas verdes.\n",
    "\n",
    "Este subgrafo verde es un ejemplo claro de un **árbol generador** de $ G $, ya que mantiene todos los vértices, conecta todo el grafo y no tiene ciclos.\n",
    "\n",
    "Un **árbol generador** es una forma especial de representar un grafo $ G $ con la menor cantidad posible de aristas, asegurando que siga siendo conexo y que no tenga ciclos. En el contexto de la imagen, el conjunto de aristas verdes forma un árbol generador, que es una estructura fundamental en algoritmos como el de **Kruskal** o el de **Prim** para encontrar árboles generadores mínimos en grafos ponderados."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "574682fd",
   "metadata": {},
   "source": [
    "### **Árboles Dirigidos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "861abe13",
   "metadata": {},
   "source": [
    "Un **árbol dirigido** es una estructura de grafo con algunas características adicionales que lo hacen diferente de un árbol no dirigido:\n",
    "\n",
    "1. **Raíz**: En un árbol dirigido, hay un vértice especial llamado **raíz**. Este vértice es el origen de todos los caminos en el árbol. Ningún otro vértice está \"por encima\" de la raíz.\n",
    "\n",
    "2. **Dirección de las aristas**: Cada arista en un árbol dirigido tiene una orientación específica. Las aristas apuntan **desde** el vértice más cercano a la raíz **hacia** los vértices más alejados de la raíz. Esto crea una estructura jerárquica clara, donde las relaciones entre los vértices están organizadas en niveles.\n",
    "\n",
    "3. **Padres e hijos**:\n",
    "   - Si existe una arista dirigida $ i \\to j $, decimos que el vértice $ i $ es el **padre** del vértice $ j $, y $ j $ es el **hijo** de $ i $.\n",
    "   - Todos los vértices tienen un único padre, excepto la **raíz**, que no tiene ningún padre.\n",
    "   \n",
    "4. **Hojas**: Los **vértices hoja** son aquellos que no tienen hijos, es decir, no hay aristas que salgan de ellos. Están al final de los caminos en el árbol dirigido.\n",
    "\n",
    "5. **Niveles**: El **nivel** de un vértice en un árbol dirigido se define como la distancia desde la **raíz**. La raíz está en el nivel 0, y cada vez que nos movemos por una arista hacia un vértice más lejano, incrementamos el nivel en 1.\n",
    "\n",
    "**Ejemplo:**\n",
    "\n",
    "En las siguientes imágenes, podemos observar ejemplos de **árboles dirigidos**:\n",
    "\n",
    "- **Raíz**: El vértice marcado en **rojo** es la **raíz** del árbol. A partir de este vértice, todas las aristas apuntan hacia otros vértices más lejanos.\n",
    "  \n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos49.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- **Padres e hijos**: En cada imagen, podemos identificar relaciones de padre e hijo. Por ejemplo, si existe una arista de un vértice $ i $ a un vértice $ j $, $ i $ es el padre de $ j $, y $ j $ es el hijo de $ i $.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos49.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- **Hojas**: Los vértices en los extremos de los caminos, que no tienen hijos (no tienen aristas saliendo de ellos), son las **hojas** del árbol.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos50.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- **Niveles**: Los vértices más cercanos a la raíz están en niveles bajos, y a medida que nos alejamos de la raíz, el nivel aumenta. La distancia desde la raíz se mide por la cantidad de aristas recorridas.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos51.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "Los **árboles dirigidos** son estructuras jerárquicas que se encuentran en muchas aplicaciones, como en las estructuras de directorios en sistemas operativos, genealogías, y en muchos algoritmos informáticos. Las relaciones de padre e hijo y los niveles son fundamentales para entender cómo los elementos del árbol están organizados y cómo se distribuyen las conexiones desde la raíz hasta las hojas."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7bb62d4e",
   "metadata": {},
   "source": [
    "### **Lemas**\n",
    "- Si $m > n − 1$ entonces $G$ tiene un ciclo. (Intenta demostrarlo)\n",
    "- Si $G$ es conexo, entonces $m \\geq n − 1$.\n",
    "\n",
    "### **Teorema**\n",
    "\n",
    "- Son equivalentes:\n",
    "  1. $G$ es un árbol.\n",
    "  2. Todo par de vértices de $G$ está unido por un único camino.\n",
    "  3. $G$ es conexo y $m = n − 1$.\n",
    "  4. $G$ es acíclico y $m = n − 1$.\n",
    "\n",
    "\n",
    "### **Teorema**\n",
    "- Todo árbol no trivial tiene al menos dos hojas.\n",
    "\n",
    "### **Teorema**\n",
    "1. **Toda arista de un árbol es un puente:** Si quitamos una arista, el árbol se separa en dos partes desconectadas. Esto ocurre porque en un árbol siempre hay un único camino entre cada par de vértices. Si eliminamos la arista que forma parte de ese camino, ya no hay forma de conectar esos vértices.\n",
    "2. Un vértice de un árbol no trivial es un punto de corte $sii$ no es una hoja.\n",
    "\n",
    "### **Teorema**\n",
    "- Un grafo es conexo $sii$ admite un árbol generador.\n",
    "\n",
    "- **Corolario:** Todo grafo conexo no trivial tiene al menos dos vértices tales que al sacar alguno de ellos, sigue siendo conexo.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de20547d",
   "metadata": {},
   "source": [
    "## **Árbol generador mínimo**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4e94d93",
   "metadata": {},
   "source": [
    "- Un **grafo pesado** es un grafo en el que cada arista tiene asociado un número, llamado **peso**, que representa algún costo, longitud, o cualquier medida relevante para el problema que se esté resolviendo. En el grafo negro de la imagen, cada arista tiene un número que indica su peso.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos52.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- El **peso de un subgrafo** es la suma de los pesos de todas las aristas que lo componen. En la imagen, el grafo verde es un subgrafo del grafo original y su peso es la suma de los valores que están en las aristas verdes.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos53.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- Un **árbol generador mínimo** en un grafo pesado es un subgrafo que conecta todos los vértices del grafo original (un **árbol generador**), pero con la **suma de pesos** de sus aristas lo más baja posible. Esto significa que se eligen las aristas necesarias para conectar todos los vértices, evitando ciclos, y de manera que el costo total sea el mínimo.\n",
    "\n",
    "En la imagen, se resalta en verde el **peso del árbol generador mínimo**:\n",
    "\n",
    "$$\n",
    "3 + 1 + 1 + 5 + 2 + 4 = 16\n",
    "$$\n",
    "\n",
    "Esto indica que hemos seleccionado las aristas con los valores de peso más bajos para formar el árbol que conecta todos los vértices del grafo original."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f142cbef",
   "metadata": {},
   "source": [
    "### **Ejemplo de aplicación:**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86a604ea",
   "metadata": {},
   "source": [
    "Se tiene qué construir caminos entre ciertos pares de ciudades en una región (o país), de modo que toda la región/país quede conectado. ¿cómo se puede hacer minimizando la longitud total de camino construído?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48c437d5",
   "metadata": {},
   "source": [
    "## **Algoritmo de Kruskal para Árbol Generador Mínimo (AGM)**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d03df050",
   "metadata": {},
   "source": [
    "El **[algoritmo de Kruskal](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm)** es una técnica para encontrar el **árbol generador mínimo** (AGM) de un grafo pesado. El proceso sigue estos pasos:\n",
    "\n",
    "1. **Partida**: Comenzamos con un subgrafo vacío (es decir, sin aristas).\n",
    "2. **Selección de aristas**: En cada paso, seleccionamos la arista de menor peso que no forme un ciclo con las aristas ya elegidas.\n",
    "3. **Finalización**: Continuamos agregando aristas hasta tener exactamente $ n-1 $ aristas, donde $ n $ es el número de vértices del grafo. Cuando tenemos $ n-1 $ aristas, el resultado es un árbol generador.\n",
    "\n",
    "El algoritmo de Kruskal garantiza que el resultado final sea un **árbol generador mínimo** debido a su proceso de selección de aristas:\n",
    "\n",
    "1. **Árbol Generador**: En cada paso, el conjunto de aristas seleccionado, llamémoslo $ B $, es acíclico y conecta partes del grafo. Esto asegura que $ B $ sea un árbol parcial. Mientras no hayamos agregado $ n-1 $ aristas, el subgrafo es un bosque, lo que significa que todavía no es conexo.\n",
    "   \n",
    "2. **Conectividad**: Cuando el algoritmo termina, hemos seleccionado $ n-1 $ aristas, lo que conecta todos los vértices sin formar ciclos, cumpliendo las propiedades de un árbol generador.\n",
    "\n",
    "3. **Minimización del Peso**: Si comparamos el árbol generado por Kruskal ($ T_K $) con cualquier otro árbol generador $ T $, siempre podemos demostrar que el proceso de Kruskal selecciona aristas de menor o igual peso que cualquier otra combinación posible. Si $ T_K $ no fuera el árbol mínimo, podríamos reemplazar alguna arista de $ T $ por una arista seleccionada por Kruskal y obtener un árbol de menor peso, lo que sería un absurdo.\n",
    "\n",
    "Por lo tanto, el **árbol generador mínimo** que construye Kruskal es efectivamente el de menor peso posible.\n",
    "\n",
    "para el grafo de la imagen:\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos55.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- Seleccionamos las aristas de menor peso: \n",
    "  - Arista (3-5) con peso 1\n",
    "  - Arista (3-2) con peso 1\n",
    "  - Arista (6-7) con peso 2\n",
    "  - Arista (1-2) con peso 3\n",
    "  - Arista (4-6) con peso 4\n",
    "  - Arista (3-4) con peso 5\n",
    "\n",
    "obteniendo un AGM:$1 + 1 + 2 + 3 + 4 + 5 = 16$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b67b6cbf",
   "metadata": {},
   "source": [
    "## **Algoritmo de Prim para Árbol Generador Mínimo (AGM)**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df4930ed",
   "metadata": {},
   "source": [
    "El **[algoritmo de Prim](https://en.wikipedia.org/wiki/Prim%27s_algorithm)** funciona comenzando con un vértice inicial y agregando aristas de menor peso una por una. Siempre se conecta un nuevo vértice al conjunto de vértices ya visitados, asegurándose de no formar ciclos. El proceso se repite hasta que todos los vértices del grafo estén conectados.\n",
    "\n",
    "La clave del algoritmo de Prim es que en cada paso estamos agregando la arista más barata posible que conecte un vértice nuevo a los que ya tenemos en el árbol. Al agregar una arista en cada paso, nos aseguramos de que no se formen ciclos, ya que siempre estamos uniendo vértices no conectados. Continuamos este proceso hasta haber agregado \\(n - 1\\) aristas, que es lo que se necesita para formar un árbol con \\(n\\) vértices.\n",
    "\n",
    "El árbol resultante será un **Árbol Generador Mínimo** porque nunca escogemos una arista más costosa si hay una opción más barata disponible. Como el grafo es conexo, siempre existirá una arista que conecte los vértices no visitados con los que ya hemos conectado. Por lo tanto, el algoritmo de Prim termina creando un árbol que incluye todos los vértices y tiene el menor costo total posible.\n",
    "\n",
    "En resumen, Prim garantiza que en cada paso estamos eligiendo la arista de menor peso que nos conecta a un vértice nuevo, lo que asegura que al final tendremos el Árbol Generador Mínimo.\n",
    "\n",
    "para el grafo de la imagen:\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos55.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- Seleccionamos las aristas de menor peso: \n",
    "  - Arista (3-5) con peso 1\n",
    "  - Arista (3-2) con peso 1\n",
    "  - Arista (1-2) con peso 3\n",
    "  - Arista (3-4) con peso 5\n",
    "  - Arista (4-6) con peso 4\n",
    "  - Arista (6-7) con peso 2\n",
    "\n",
    "obteniendo un AGM:$1 + 1 + 3 + 5 + 4 + 2 = 16$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aeb0e6ea",
   "metadata": {},
   "source": [
    "### **Diferencias clave entre los algoritmos de Kruskal y Prim:**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf111758",
   "metadata": {},
   "source": [
    "1. **Estrategia de selección de aristas**:\n",
    "   - **Kruskal**: Selecciona aristas de forma **global**, eligiendo las más baratas en todo el grafo. No depende de un vértice inicial, y el enfoque está en las aristas del grafo completo.\n",
    "   - **Prim**: Selecciona aristas de forma **local**, comenzando en un vértice específico y expandiendo el árbol con la arista más barata que conecta un vértice dentro del árbol a uno fuera del árbol.\n",
    "\n",
    "2. **Construcción del árbol**:\n",
    "   - **Kruskal**: Puede trabajar con varias componentes al mismo tiempo, es decir, va conectando **subárboles** hasta formar el AGM final.\n",
    "   - **Prim**: Siempre construye a partir de un solo **subárbol** que va expandiéndose continuamente desde un vértice inicial.\n",
    "\n",
    "3. **Estructuras de datos utilizadas**:\n",
    "   - **Kruskal**: Utiliza una estructura de **[Union-Find](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)** o conjuntos disjuntos para asegurar que las aristas seleccionadas no formen ciclos.\n",
    "   - **Prim**: Utiliza una **cola de prioridad** o **[heap](https://en.wikipedia.org/wiki/Heap_(data_structure))** para elegir la siguiente arista de menor costo que expande el árbol actual.\n",
    "\n",
    "4. **Aplicabilidad**:\n",
    "   - **Kruskal**: Es más eficiente en **grafos dispersos** con pocas aristas, ya que selecciona aristas sin importar cuántos vértices están involucrados inicialmente.\n",
    "   - **Prim**: Funciona mejor en **grafos densos**, ya que extiende el árbol desde un vértice y se beneficia de tener muchas aristas que conectan vértices cercanos.\n",
    "\n",
    "5. **Orden de ejecución**:\n",
    "   - **Kruskal**: Necesita **ordenar** todas las aristas antes de empezar el proceso, lo que añade un coste de tiempo inicial considerable.\n",
    "   - **Prim**: No necesita ordenar todas las aristas al principio, ya que selecciona la arista de menor peso en cada paso usando la estructura de datos.\n",
    "\n",
    "6. **Uso típico**:\n",
    "   - **Kruskal**: Suele utilizarse en grafos **dispersos** o no conexos, donde se deben conectar múltiples componentes.\n",
    "   - **Prim**: Es más común en **grafos densos** o cuando el grafo ya es conexo y se necesita optimizar la expansión del árbol desde un vértice inicial.\n",
    "\n",
    "7. **Aplicaciones prácticas**:\n",
    "   - **Kruskal**: Diseño de redes de telecomunicaciones, Sistemas de distribución eléctrica, Reducción de rutas de transporte, Compresión de imágenes y gráficos, Diseño de redes de ditribución de gas y agua.\n",
    "   - **Prim**: Desarrollo de cirtuitos integrados, Expansión de redes de comunicación, Optimización de rutas de entrega, Desarrollo de mapas y gráficos, Gestión de redes de sensores.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "415cdee0",
   "metadata": {},
   "source": [
    "## **Caminos y Circuitos Eulerianos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9736c82c",
   "metadata": {},
   "source": [
    "- **camino Euleriano** en un grafo es un recorrido que pasa por **cada arista exactamente una vez**. Es decir, un camino que no deja ninguna arista sin recorrer ni la recorre más de una vez. Sin embargo, este camino **no necesariamente tiene que volver al punto de partida**.\n",
    "\n",
    "- **Circuito Euleriano**: Un **circuito Euleriano** es similar al camino Euleriano, pero tiene una diferencia importante: además de recorrer cada arista una sola vez, **debe comenzar y terminar en el mismo vértice**. Es decir, es un ciclo que cubre todas las aristas del grafo una vez.\n",
    "\n",
    "- **Grafo Euleriano**: Un grafo o multigrafo se llama **Euleriano** si posee un **circuito Euleriano**, es decir, si existe un ciclo que recorre todas sus aristas exactamente una vez y termina en el vértice donde comenzó.\n",
    "\n",
    "Un grafo que tiene **más de una componente conexa no trivial** no puede tener un camino ni un circuito Euleriano. Esto es porque un camino Euleriano requiere que todas las aristas sean recorridas, y si hay más de una componente desconectada, no se podría llegar a todas las aristas sin abandonar una de las componentes. Para que un grafo sea **Euleriano** y tenga un **circuito Euleriano**, debe ser conexo (es decir, no puede tener partes desconectadas) y satisfacer algunas condiciones adicionales relacionadas con los grados de los vértices.\n",
    "\n",
    "**Ejemplo**\n",
    "\n",
    "Imagina una ciudad con calles conectando varios puntos importantes (representados como vértices) y el objetivo es diseñar una ruta para un camión de limpieza que recorra cada calle (arista) **exactamente una vez**, regresando al punto de partida. Si esta ruta existe, la red de calles puede considerarse un **grafo Euleriano**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cd2c5539",
   "metadata": {},
   "source": [
    "### **Teorema de Euler**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0200f456",
   "metadata": {},
   "source": [
    "El **Teorema de Euler** es uno de los resultados fundamentales en la teoría de grafos y nos ayuda a identificar cuándo un grafo tiene un **circuito euleriano**, es decir, un camino cerrado que recorre todas las aristas del grafo exactamente una vez.\n",
    "\n",
    "**Teorema:** Para un grafo $G$ conexo (es decir, que tiene un solo componente conexo), las siguientes tres condiciones son equivalentes:\n",
    "1. **$G$ es Euleriano:** Esto significa que existe un **circuito euleriano** en el grafo, es decir, un camino cerrado que pasa por todas las aristas del grafo exactamente una vez.\n",
    "2. **Todo vértice de $G$ tiene grado par:** Esto quiere decir que, en un grafo euleriano, cada vértice tiene un número par de aristas conectadas a él. Esto es esencial para que el recorrido pueda entrar y salir del vértice el mismo número de veces.\n",
    "3. **Las aristas de $G$ pueden particionarse en circuitos:** Esto significa que las aristas del grafo pueden organizarse en grupos de caminos cerrados (circuitos), donde cada uno de estos circuitos pasa por todas las aristas exactamente una vez, y al final se pueden unir para formar un solo gran circuito (el circuito euleriano).\n",
    "\n",
    "Si se cumple cualquiera de estas tres condiciones, automáticamente se cumplen las otras dos. Es decir, si un grafo tiene todas sus aristas conectadas a vértices de grado par, entonces podemos estar seguros de que es posible recorrer todas las aristas en un solo circuito euleriano. Además, las aristas pueden agruparse en circuitos individuales si es necesario, lo que nos proporciona una estructura clara del grafo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "672665d0",
   "metadata": {},
   "source": [
    "### **Teorema sobre el Camino Euleriano**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bdcce028",
   "metadata": {},
   "source": [
    "Un grafo conexo tiene un **camino euleriano** si, y solo si, todos sus vértices tienen grado par, excepto dos que tienen grado impar.\n",
    "\n",
    "Este teorema establece la condición necesaria y suficiente para que un grafo conexo contenga un camino euleriano. Esto significa que, si el grafo posee tal camino, el recorrido comenzará en uno de los vértices de grado impar y finalizará en el otro, recorriendo todas las aristas exactamente una vez. Los vértices de grado par permiten que se entre y salga de ellos sin dificultad, mientras que los vértices de grado impar marcan el inicio y el final del recorrido.\n",
    "\n",
    "Además, el teorema sugiere que **si un grafo tiene exactamente dos vértices de grado impar, entonces posee un camino euleriano**. Por el contrario, si hay más de dos vértices de grado impar, no será posible encontrar un recorrido que pase por todas las aristas exactamente una vez.\n",
    "\n",
    "Ambos teoremas ofrecen criterios claros para determinar si un grafo tiene un **camino** o un **circuito euleriano**:\n",
    "- Si **todos los vértices tienen grado par**, el grafo tiene un circuito euleriano.\n",
    "- Si **exactamente dos vértices tienen grado impar**, el grafo tiene un camino euleriano.\n",
    "- Si hay más de dos vértices de grado impar, no es posible encontrar ni un camino ni un circuito euleriano.\n",
    "\n",
    "**Ejercicios**\n",
    "\n",
    "Examina los grafos mostrados en las figuras y determina si cada uno tiene un camino euleriano o un circuito euleriano, o si no poseen ninguno de estos.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos58.PNG?raw=true\" width=\"750\" />\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0a2ba12",
   "metadata": {},
   "source": [
    "## **El juego de Hamilton**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1429bb5",
   "metadata": {},
   "source": [
    "\n",
    "En 1859 Hamilton inventó un juego que consistía en encontrar un recorrido de todos los vértices de un dodecaedro sin repetir vértices y volviendo al original.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos59.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "- Un **camino Hamiltoniano** en un grafo $ G $ es un camino que pasa por cada uno de los vértices del grafo **una sola vez**. Esto significa que se visitan todos los vértices, pero sin repetir ningún vértice durante el recorrido. Sin embargo, este camino no necesariamente vuelve al vértice de inicio; solo se asegura de visitar cada vértice exactamente una vez.\n",
    "\n",
    "- Un **circuito Hamiltoniano**, en cambio, es similar al camino Hamiltoniano, pero con una diferencia clave: además de visitar cada vértice del grafo una única vez, el recorrido regresa al vértice de partida, formando así un circuito cerrado.\n",
    "\n",
    "- Un **grafo es Hamiltoniano** si contiene un circuito Hamiltoniano, es decir, si existe un recorrido que pase por todos los vértices una sola vez y vuelva al vértice inicial.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos60.PNG?raw=true\" width=\"300\" />\n",
    "</p>\n",
    "\n",
    "Si un grafo no es **conexo** (es decir, si hay partes del grafo que no están conectadas entre sí), entonces es imposible que tenga un camino o circuito Hamiltoniano. Esto se debe a que, en un grafo no conexo, no hay manera de viajar de un conjunto de vértices a otro sin \"saltar\" de una componente a otra, lo que impide recorrer todos los vértices."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf222b83",
   "metadata": {},
   "source": [
    "## **El Problema del Viajante (TSP)**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af57f07f",
   "metadata": {},
   "source": [
    "El **Problema del Viajante de Comercio ([Travelling Salesman Problem, TSP](https://en.wikipedia.org/wiki/Travelling_salesman_problem), por sus siglas en inglés)** es un problema clásico de optimización en el que un viajante debe recorrer una serie de ciudades, visitando cada una de ellas exactamente una vez, y finalmente regresar a la ciudad de origen. El objetivo es encontrar la ruta más corta posible que permita cumplir con esta tarea, minimizando la distancia total recorrida o el costo asociado al trayecto.\n",
    "\n",
    "**Interpretación en términos de grafos:**\n",
    "\n",
    "En el contexto de la teoría de grafos, el problema se puede representar de la siguiente manera:\n",
    "- **Ciudades**: Cada ciudad es un **vértice** en un grafo.\n",
    "- **Caminos entre ciudades**: Los caminos entre las ciudades son las **aristas** que conectan los vértices.\n",
    "- **Costos de viaje**: A cada arista se le asigna un valor que representa la **distancia**, **tiempo**, o **costo** asociado con viajar de una ciudad a otra.\n",
    "\n",
    "Dado que el viajante debe visitar todas las ciudades, el grafo en cuestión es un **grafo completo**, lo que significa que cada vértice está conectado con todos los demás. El objetivo es encontrar un **circuito Hamiltoniano**, es decir, un recorrido que pase por todos los vértices exactamente una vez y regrese al punto de partida, con la longitud total más corta posible.\n",
    "\n",
    "**Versión de decisión del TSP:**\n",
    "\n",
    "El **TSP** tiene una versión más sencilla conocida como **versión de decisión**. En esta versión, la entrada incluye:\n",
    "- Un grafo completo $G$ con longitudes (o costos) asociadas a las aristas.\n",
    "- Un número $ k $.\n",
    "\n",
    "La pregunta a resolver es: **\"¿Existe un circuito Hamiltoniano en $ G $ cuya longitud total sea menor o igual a $ k $?\"**. Esta formulación transforma el problema en una cuestión de sí o no, en lugar de requerir la ruta óptima exacta.\n",
    "\n",
    "**Importancia y dificultad:**\n",
    "\n",
    "El **Problema del Viajante de Comercio** es uno de los problemas más estudiados en la teoría de la computación y está clasificado como un problema **[NP-completo](https://en.wikipedia.org/wiki/NP-completeness)**, lo que significa que no se conoce un algoritmo eficiente para resolverlo en todos los casos. A pesar de ello, tiene aplicaciones prácticas importantes en áreas como la logística, la planificación de rutas, y la optimización de circuitos, entre otros."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2088c7e",
   "metadata": {},
   "source": [
    "### **Recorrido en $n$ vértices**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e0344dc",
   "metadata": {},
   "source": [
    "- **Recorrido con cuatro vértices**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos61.PNG?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- **Recorrido con cinco vértices**\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos62.PNG?raw=true\" width=\"500\" />\n",
    "</p>\n",
    "\n",
    "- **Recorridos con más de cinco vértices**\n",
    "  - ¿Cuántos recorridos tengo en un caso con 10 vértices? $181440$\n",
    "\n",
    "  - ¿Cuántos recorridos tengo en un caso con 50 vértices? $304140932017133780436126081660647688443776415689605120000000000$  \n",
    "\n",
    "  - ¿Cuántos recorridos tengo en un caso con 100 vértices? $466631077219720763408496194281333502453579841321908107342964819476087999966149578044707319880782591431268489604136118791255926054584320000000000000000000000$  \n",
    "\n",
    "  - ¿Cuántos recorridos tengo en un caso con $n$ vértices?\n",
    "\n",
    "$$\n",
    "\\frac{(n-1)!}{2}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "046958c0",
   "metadata": {},
   "source": [
    "## **Problemas de camino mínimo**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f011dd32",
   "metadata": {},
   "source": [
    "Dado un grafo orientado $G=(V, E)$ con longitudes asociadas a sus aristas ( $\\ell: E \\rightarrow \\mathbb{R}$ ), la longitud (o peso o costo) de un camino es la suma de las longitudes de sus aristas.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos63.PNG?raw=true\" width=\"350\" />\n",
    "</p>\n",
    "\n",
    "En el digrafo de la figura, la longitud del camino mínimo de $6$ a $2$ es $7$.\n",
    "\n",
    "El problema del camino mínimo consiste en encontrar el camino de menor longitud...\n",
    "- de un vértice a otro\n",
    "- de un vértice a todos los demás\n",
    "- entre todos los pares de vértices.\n",
    "\n",
    "La distancia de $v$ a $w, d(v, w)$, es la longitud de un camino mínimo entre $v$ y $w,+\\infty$ si no existe ningún camino de $v$ a $w, \\mathrm{y}-\\infty$ si existen caminos de $v$ a $w$ pero no uno mínimo.\n",
    "\n",
    "- Observemos que en un grafo orientado no siempre vale $d(v, w)=d(w, v)$.\n",
    "\n",
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Grafos64.PNG?raw=true\" width=\"350\" />\n",
    "</p>\n",
    "\n",
    "\n",
    "En el digrafo de la figura, $d(6,7)=7$ y $d(7,6)=3$.\n",
    "\n",
    "- Si $G$ tiene un ciclo orientado de longitud negativa, no va a existir camino mínimo entre algunos pares de vértices, es decir, va a haber vértices a distancia $-\\infty$.\n",
    "- Si $G$ no tiene ciclos orientados de longitud negativa (aunque pueda tener aristas de longitud negativa), para todo camino $P$ existe $P^{\\prime}$ simple con $\\ell\\left(P^{\\prime}\\right) \\leq \\ell(P)$. Como la cantidad de caminos simples en un grafo finito es finita, si existe un camino entre $v$ y $w$, existe uno mínimo.\n",
    "- Si $G$ es no orientado, el problema de camino mínimo en $G$ va a ser el mismo que en el digrafo que se obtiene reemplazando cada arista por dos orientadas una para cada lado y con la misma longitud que la original. En ese caso, aristas de longitud negativa implicarían ciclos negativos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7210c67c",
   "metadata": {},
   "source": [
    "### **Principio de optimalidad**\n",
    "\n",
    "Todo subcamino de un camino mínimo es un camino mínimo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0bc98336",
   "metadata": {},
   "source": [
    "### **Propiedad - Árbol de caminos mínimos**\n",
    "Si $G$ no tiene aristas de costo negativo y $s$ es un vértice de $G$ tal que para todo $v \\in V(G)$ existe un camino de $s$ a $v$, entonces existe un árbol orientado $T$ con raíz $s$ tal que para todo $v \\in V(G)$, el camino de $s$ a $v$ en $T$ es un camino mínimo de $s$ a $v$ en $G$.\n",
    "\n",
    "- La propiedad vale igual para grafos con aristas negativas pero sin ciclos negativos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "263dbc4f",
   "metadata": {},
   "source": [
    "## **Optimización de recorridos en grafos**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f008359a-ee0c-4c1e-8433-e71c575a8f34",
   "metadata": {},
   "source": [
    "<p float=\"center\">\n",
    "  <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/ShortestPath01.png?raw=true\" width=\"350\" />\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cba410d",
   "metadata": {},
   "source": [
    "### Exploración del Problema del Camino Más Corto en Grafos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d6580b4",
   "metadata": {},
   "source": [
    "El problema del [camino más corto](https://en.wikipedia.org/wiki/Shortest_path_problem) (*Shortest path problem*) se concentra en identificar la ruta óptima entre dos puntos en un grafo. Este problema es aplicable en contextos como sistemas de transporte y redes de comunicación, donde se busca minimizar costos, distancias o tiempos. En grafos ponderados, el desafío es hallar el camino que acumula el menor peso total, abarcando dos variantes principales: la búsqueda del camino más corto entre un nodo origen y un destino específico, y la determinación de las rutas más cortas desde un origen a todos los demás nodos.\n",
    "\n",
    "Varios algoritmos han sido desarrollados para abordar este problema, adaptándose a características particulares de los grafos, como la presencia o ausencia de pesos negativos y la naturaleza dirigida o no dirigida de estos. Entre ellos, el [Algoritmo de Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) es conocido por su eficiencia en grafos ponderados sin pesos negativos. Sin embargo, otras alternativas como [Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) y [Floyd-Warshall](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) también son relevantes, cada una ofreciendo distintas ventajas en contextos específicos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da23dfc7",
   "metadata": {},
   "source": [
    "### Introducción al Problema del Camino Más Corto"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a9e4fb8",
   "metadata": {},
   "source": [
    "El problema del camino más corto es una interrogante central en la teoría de grafos y un pilar fundamental en las ciencias de la computación. Este problema no solo tiene aplicaciones teóricas, sino que también es crucial en una variedad de aplicaciones prácticas, como en el diseño de redes de transporte, la optimización de rutas en logística, y en sistemas de comunicaciones. El objetivo de este problema es encontrar la ruta más eficiente entre dos puntos en un grafo, una estructura de datos compuesta por nodos (o vértices) interconectados por aristas (o bordes)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "448e41fa",
   "metadata": {},
   "source": [
    "### Exploración Detallada del Problema"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4aabbe1b",
   "metadata": {},
   "source": [
    "En su esencia, el problema del camino más corto busca determinar la ruta de menor costo o distancia entre dos nodos en un grafo. Este grafo puede ser no dirigido, donde las aristas no tienen una dirección específica, o dirigido, donde cada arista tiene una dirección definida. Además, el grafo puede ser ponderado, es decir, cada arista tiene un peso o costo asociado, o no ponderado, donde todas las aristas tienen el mismo peso implícito.\n",
    "\n",
    "La complejidad del problema del camino más corto varía según la naturaleza del grafo. En un grafo ponderado, los pesos pueden representar distintas métricas como distancia, tiempo, costo, o incluso probabilidades. Por lo tanto, encontrar el camino más corto implica calcular la ruta que acumula el menor peso total de las aristas entre el punto de inicio y el punto de destino.\n",
    "\n",
    "El problema del camino más corto se presenta en dos variantes principales:\n",
    "\n",
    "1. **Camino más corto desde un origen a un destino específico**: Aquí, el objetivo es encontrar la ruta más corta entre un par de nodos específicos. Este problema es fundamental en situaciones donde se requiere optimizar un trayecto entre dos puntos determinados.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "2. **Camino más corto desde un origen a todos los destinos (problema de ruta mínima)**: En este caso, se busca determinar el camino más corto desde un nodo de origen a todos los demás nodos en el grafo. Esta variante es especialmente relevante en el contexto de redes, donde se busca conocer las rutas óptimas desde un punto central a múltiples destinos.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "89210614",
   "metadata": {},
   "source": [
    "### Algoritmos y Métodos de Solución"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f556bae8",
   "metadata": {},
   "source": [
    "Diversos algoritmos han sido desarrollados para abordar el problema del camino más corto, cada uno con sus peculiaridades dependiendo de las características del grafo en cuestión. Entre los más prominentes se encuentran:\n",
    "\n",
    "- **[Algoritmo de Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)**: Eficaz en grafos con pesos no negativos, busca el camino más corto expandiéndose iterativamente desde el nodo de origen y actualizando las distancias más cortas.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **[Algoritmo de Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm)**: A diferencia del de *Dijkstra*, este algoritmo puede manejar grafos con pesos negativos y es capaz de detectar ciclos de peso negativo.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **[Algoritmo de Floyd-Warshall](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)**: Utilizado para encontrar las distancias más cortas entre todos los pares de nodos en un grafo ponderado, es particularmente útil en la evaluación de rutas en redes densas.\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "- **[Algoritmo A*](https://en.wikipedia.org/wiki/A*_search_algorithm)**: Este algoritmo, basado en búsqueda heurística, es útil en grafos de búsqueda y en situaciones donde se necesita una solución óptima eficiente.\n",
    "\n",
    "Cada uno de estos algoritmos tiene aplicaciones específicas y es seleccionado en función del tipo de grafo, la presencia de pesos negativos, y el requisito de optimización de recursos computacionales."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53177fd5",
   "metadata": {},
   "source": [
    "### Algoritmo de Dijkstra"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9002c3bd",
   "metadata": {},
   "source": [
    "#### Introducción"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f25e1432",
   "metadata": {},
   "source": [
    "El *algoritmo de Dijkstra*, nombrado en honor a su creador [Edsger W. Dijkstra](https://en.wikipedia.org/wiki/Edsger_W._Dijkstra), es un método para encontrar el camino más corto en un grafo ponderado dirigido o no dirigido, siempre y cuando los pesos de las aristas sean no negativos. Propuesto en 1956, este algoritmo es un ejemplo clásico en el campo de la teoría de grafos y la ciencia de la computación, especialmente en aplicaciones relacionadas con la planificación de rutas y la optimización de redes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32ab0f56",
   "metadata": {},
   "source": [
    "#### Funcionamiento y Uso del Algoritmo"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "433f752e",
   "metadata": {},
   "source": [
    "El *algoritmo de Dijkstra* funciona seleccionando primero un punto de partida fijo, denominado el vértice fuente, y luego calculando la distancia más corta de todos los demás vértices desde el vértice fuente.\n",
    "\n",
    "El algoritmo asume que todos los pesos son positivos porque presupone que la distancia de `X` a `Y` y luego a `Z` siempre es mayor que la distancia directa de `X` a `Y`. Esto siempre será cierto para las distancias. Si se tiene un grafo con pesos negativos o cero, el algoritmo de *Dijkstra* no puede utilizarse.\n",
    "\n",
    "El algoritmo también supone que el grafo está conectado (es decir, es posible encontrar un camino entre cualquier par de vértices `X` e `Y`), que el grafo es no dirigido (la distancia de `X` a `Y` siempre es la misma que de `Y` a `X`), y que no es un multigrafo (no puede haber más de una conexión directa entre cualquier `X` e `Y`), y no contiene bucles (`X` no está conectado consigo mismo).\n",
    "\n",
    "El resultado será un árbol que muestra la ruta más corta entre el vértice fuente y todos los demás vértices. Un árbol es un grafo que no contiene ciclos, en otras palabras, existe un único camino entre cualquier par de vértices `X` e `Y`. Aquí está la solución para el grafo mencionado anteriormente, asumiendo que el vértice fuente es `A`:\n",
    "\n",
    "***Usos del Algoritmo:***\n",
    "- **Planificación de Rutas**: En redes de transporte y logística, para encontrar el camino más eficiente entre ubicaciones.\n",
    "- **Redes de Comunicación**: Optimiza la transmisión de datos al encontrar la ruta de menor latencia en redes.\n",
    "- **Sistemas de Navegación GPS**: Calcula rutas óptimas para la navegación vehicular o peatonal.\n",
    "\n",
    "***Capacidad del Algoritmo:***\n",
    "- El algoritmo es eficiente para grafos con pesos no negativos, donde proporciona una solución precisa y rápida para el camino más corto.\n",
    "- Es altamente eficaz en la exploración de grafos con numerosos nodos, mostrando una capacidad notable para gestionar complejas redes de nodos y aristas.\n",
    "\n",
    "***Dificultades y Limitaciones:***\n",
    "- **Pesos Negativos**: El algoritmo no es adecuado para grafos que contienen aristas con pesos negativos. En tales casos, el algoritmo puede fallar en proporcionar el camino más corto.\n",
    "- **Rendimiento en Grandes Redes**: Aunque eficiente, su rendimiento puede ser superado por algoritmos más avanzados o especializados en ciertas situaciones, especialmente en redes extensas con estructuras complejas.\n",
    "- **Actualizaciones Dinámicas**: El algoritmo de Dijkstra no se adapta bien a situaciones donde el grafo se actualiza frecuentemente, como en redes de tráfico en tiempo real, ya que cada cambio requiere una nueva ejecución completa del algoritmo.\n",
    "\n",
    "***Pros:***\n",
    "- **Simplicidad y Claridad**: El algoritmo es conceptualmente sencillo y fácil de entender, lo que facilita su enseñanza y comprensión.\n",
    "- **Precisión**: Para grafos con pesos no negativos, garantiza encontrar el camino más corto.\n",
    "- **Flexibilidad**: Aplicable a una variedad de problemas prácticos en diferentes dominios.\n",
    "\n",
    "***Contras:***\n",
    "- **Ineficacia con Pesos Negativos**: Incapacidad para manejar grafos con aristas de peso negativo.\n",
    "- **Demanda Computacional en Redes Extensas**: Puede ser menos eficiente en términos de tiempo y espacio en comparación con otros algoritmos en ciertos contextos.\n",
    "- **Rigidez ante Cambios en el Grafo**: No es ideal para situaciones donde el grafo cambia dinámicamente.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39408765",
   "metadata": {},
   "source": [
    "### Implementación del Algoritmo de Dijkstra"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d10541b7",
   "metadata": {},
   "source": [
    "El *algoritmo de Dijkstra*, utilizando una Matriz de Adyacencia, tiene como objetivo generar un árbol de caminos más cortos (*SPT*, por sus siglas en inglés) con un origen dado. Se mantiene una Matriz de Adyacencia con dos conjuntos: \n",
    "- Un conjunto contiene los vértices ya incluidos en el árbol de camino más corto.\n",
    "- El otro conjunto contiene los vértices que aún no han sido incluidos en dicho árbol. \n",
    "En cada paso del algoritmo, se busca un vértice que esté en el segundo conjunto y que tenga la distancia mínima desde el origen.\n",
    "\n",
    "```pseudocode\n",
    "1. Inicializar una lista o conjunto (por ejemplo, 'unvisited') con todos los nodos en el grafo.\n",
    "2. Asignar a cada nodo una distancia tentativa: establecerla en cero para el nodo inicial y en infinito para todos los demás nodos.\n",
    "3. Establecer el nodo inicial como nodo actual.\n",
    "4. Para el nodo actual, considerar todos sus vecinos no visitados y calcular su distancia tentativa. Si la distancia calculada es menor que la asignada actualmente, actualizar la distancia.\n",
    "5. Después de considerar todos los vecinos del nodo actual, marcar el nodo como visitado y eliminarlo del conjunto 'unvisited'. Un nodo visitado no será verificado de nuevo.\n",
    "6. Si el nodo destino ha sido marcado visitado (cuando se planifica una ruta entre dos puntos específicos) o si la distancia más pequeña entre los nodos no visitados es infinita (cuando se están calculando rutas más cortas a todos los nodos), entonces el algoritmo ha terminado.\n",
    "7. De lo contrario, seleccionar el nodo no visitado que está marcado con la distancia más pequeña, establecerlo como el nuevo \"nodo actual\" y volver al paso 4.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f24a5a9",
   "metadata": {},
   "source": [
    "### Ejemplo - Algoritmo Dijkstra (usando matriz de adjacencia)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6333a90",
   "metadata": {},
   "source": [
    "Dado un grafo ponderado y un vértice de origen en dicho grafo, el objetivo es encontrar las rutas más cortas desde este vértice origen hacia todos los demás vértices presentes en el grafo.\n",
    "\n",
    "***Nota:*** Es importante señalar que el grafo en cuestión no incluye aristas con pesos negativos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f99e6b04",
   "metadata": {},
   "source": [
    "**Paso 0 (Inicialización):**\n",
    "Todos los nodos tienen distancias infinitas excepto el nodo origen (`0`) que tiene distancia cero.\n",
    "\n",
    "<table id=\"mytable\" border=0>\n",
    "<tr>\n",
    "<td rowspan='2'> <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Dijkstra01.PNG?raw=true\" width=\"350\"/></td>\n",
    "<td style=\"height:50%\"> \n",
    "<table border=\"1\">\n",
    "    <thead>\n",
    "        <tr>\n",
    "            <th>Vértice</th>\n",
    "            <th>Vis</th>\n",
    "            <th>Dist</th>\n",
    "            <th>Prev</th>\n",
    "        </tr>\n",
    "    </thead>\n",
    "    <tbody>\n",
    "        <tr>\n",
    "            <td>0</td>\n",
    "            <td>No</td>\n",
    "            <td>0</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>1</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>2</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>3</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>4</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>5</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>6</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>7</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>8</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "    </tbody>\n",
    "</table>\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a01ce71",
   "metadata": {},
   "source": [
    "**Paso 1 (Visita del nodo `0`):**\n",
    "Visitamos el nodo `0` y actualizamos las distancias a los nodos `1` y `7`.\n",
    "\n",
    "<table id=\"mytable\" border=0>\n",
    "<tr>\n",
    "<td rowspan='2'> <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Dijkstra02.PNG?raw=true\" width=\"150\"/></td>\n",
    "<td style=\"height:50%\"> \n",
    "<table border=\"1\">\n",
    "    <thead>\n",
    "        <tr>\n",
    "            <th>Vértice</th>\n",
    "            <th>Vis</th>\n",
    "            <th>Dist</th>\n",
    "            <th>Prev</th>\n",
    "        </tr>\n",
    "    </thead>\n",
    "    <tbody>\n",
    "        <tr>\n",
    "            <td>0</td>\n",
    "            <td>Sí</td>\n",
    "            <td>0</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>1</td>\n",
    "            <td>No</td>\n",
    "            <td>4</td>\n",
    "            <td>0</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>2</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>3</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>4</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>5</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>6</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>7</td>\n",
    "            <td>No</td>\n",
    "            <td>8</td>\n",
    "            <td>0</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>8</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "    </tbody>\n",
    "</table>\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07ab751c",
   "metadata": {},
   "source": [
    "**Paso 2 (Visita del nodo `1`):**\n",
    "El nodo `1` es el siguiente más cercano a `0`, así que lo visitamos y actualizamos las distancias a `2` y `7`.\n",
    "\n",
    "<table id=\"mytable\" border=0>\n",
    "<tr>\n",
    "<td rowspan='2'> <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Dijkstra03.PNG?raw=true\" width=\"250\"/></td>\n",
    "<td style=\"height:50%\"> \n",
    "<table border=\"1\">\n",
    "    <thead>\n",
    "        <tr>\n",
    "            <th>Vértice</th>\n",
    "            <th>Vis</th>\n",
    "            <th>Dist</th>\n",
    "            <th>Prev</th>\n",
    "        </tr>\n",
    "    </thead>\n",
    "    <tbody>\n",
    "        <tr>\n",
    "            <td>0</td>\n",
    "            <td>Sí</td>\n",
    "            <td>0</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>1</td>\n",
    "            <td>Sí</td>\n",
    "            <td>4</td>\n",
    "            <td>0</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>2</td>\n",
    "            <td>No</td>\n",
    "            <td>12</td>\n",
    "            <td>1</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>3</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>4</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>5</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>6</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>7</td>\n",
    "            <td>No</td>\n",
    "            <td>8</td>\n",
    "            <td>0</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>8</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "    </tbody>\n",
    "</table>\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "</table>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4fb40a74",
   "metadata": {},
   "source": [
    "**Paso 3 (Visita del nodo `7`):**\n",
    "Seleccionamos `7` como el más cercano a `0` y actualizamos las distancias para `6` y `8`.\n",
    "\n",
    "<table id=\"mytable\" border=0>\n",
    "<tr>\n",
    "<td rowspan='2'> <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Dijkstra04.PNG?raw=true\" width=\"250\"/></td>\n",
    "<td style=\"height:50%\"> \n",
    "<table border=\"1\">\n",
    "    <thead>\n",
    "        <tr>\n",
    "            <th>Vértice</th>\n",
    "            <th>Vis</th>\n",
    "            <th>Dist</th>\n",
    "            <th>Prev</th>\n",
    "        </tr>\n",
    "    </thead>\n",
    "    <tbody>\n",
    "        <tr>\n",
    "            <td>0</td>\n",
    "            <td>Sí</td>\n",
    "            <td>0</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>1</td>\n",
    "            <td>Sí</td>\n",
    "            <td>4</td>\n",
    "            <td>0</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>2</td>\n",
    "            <td>No</td>\n",
    "            <td>12</td>\n",
    "            <td>1</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>3</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>4</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>5</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>6</td>\n",
    "            <td>No</td>\n",
    "            <td>9</td>\n",
    "            <td>7</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>7</td>\n",
    "            <td>Sí</td>\n",
    "            <td>8</td>\n",
    "            <td>0</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>8</td>\n",
    "            <td>No</td>\n",
    "            <td>15</td>\n",
    "            <td>7</td>\n",
    "        </tr>\n",
    "    </tbody>\n",
    "</table>\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e180951",
   "metadata": {},
   "source": [
    "**Paso 4 (Visita del nodo `6`):**\n",
    "Ahora, el nodo `6` tiene la distancia más corta. Lo visitamos y actualizamos las distancias a `5` y `8`.\n",
    "\n",
    "<table id=\"mytable\" border=0>\n",
    "<tr>\n",
    "<td rowspan='2'> <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Dijkstra05.PNG?raw=true\" width=\"250\"/></td>\n",
    "<td style=\"height:50%\"> \n",
    "<table border=\"1\">\n",
    "    <thead>\n",
    "        <tr>\n",
    "            <th>Vértice</th>\n",
    "            <th>Vis</th>\n",
    "            <th>Dist</th>\n",
    "            <th>Prev</th>\n",
    "        </tr>\n",
    "    </thead>\n",
    "    <tbody>\n",
    "        <tr>\n",
    "            <td>0</td>\n",
    "            <td>Sí</td>\n",
    "            <td>0</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>1</td>\n",
    "            <td>Sí</td>\n",
    "            <td>4</td>\n",
    "            <td>0</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>2</td>\n",
    "            <td>No</td>\n",
    "            <td>12</td>\n",
    "            <td>1</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>3</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>4</td>\n",
    "            <td>No</td>\n",
    "            <td>INF</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>5</td>\n",
    "            <td>No</td>\n",
    "            <td>11</td>\n",
    "            <td>6</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>6</td>\n",
    "            <td>Sí</td>\n",
    "            <td>9</td>\n",
    "            <td>7</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>7</td>\n",
    "            <td>Sí</td>\n",
    "            <td>8</td>\n",
    "            <td>0</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>8</td>\n",
    "            <td>No</td>\n",
    "            <td>15</td>\n",
    "            <td>7</td>\n",
    "        </tr>\n",
    "    </tbody>\n",
    "</table>\n",
    "\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5f7ca14",
   "metadata": {},
   "source": [
    "Resumiremos los pasos intermedios, hasta llegar al último paso:\n",
    "\n",
    "**Paso 5 (Visita del nodo `5`):**\n",
    "El nodo `5` es el siguiente. Visitamos y actualizamos las distancias para `3` y `4`.\n",
    "\n",
    "\n",
    "|Vértice | Vis | Dist | Prev|\n",
    "|:------:|:---:|:----:|:---:|\n",
    "|0       | Sí  | 0    | -|\n",
    "|1       | Sí  | 4    | 0|\n",
    "|2       | No  | 12   | 1|\n",
    "|3       | No  | 25   | 5|\n",
    "|4       | No  | 21   | 5|\n",
    "|5       | Sí  | 11   | 6|\n",
    "|6       | Sí  | 9    | 7|\n",
    "|7       | Sí  | 8    | 0|\n",
    "|8       | No  | 15   | 7|\n",
    "\n",
    "\n",
    "**Paso 6 (Visita del nodo `2`):**\n",
    "Seleccionamos `2` y actualizamos las distancias para `3` y `8`.\n",
    "\n",
    "|Vértice | Vis | Dist | Prev|\n",
    "|:------:|:---:|:----:|:---:|\n",
    "|0       | Sí  | 0    | -|\n",
    "|1       | Sí  | 4    | 0|\n",
    "|2       | Sí  | 12   | 1|\n",
    "|3       | No  | 19   | 2|\n",
    "|4       | No  | 21   | 5|\n",
    "|5       | Sí  | 11   | 6|\n",
    "|6       | Sí  | 9    | 7|\n",
    "|7       | Sí  | 8    | 0|\n",
    "|8       | No  | 14   | 2|\n",
    "\n",
    "**Paso 7 (Visita del nodo `8`):**\n",
    "Visitamos `8`, aunque no hay actualizaciones para `8`  ya que todos sus vecinos han sido visitados o tienen distancias más cortas.\n",
    "\n",
    "|Vértice | Vis | Dist | Prev|\n",
    "|:------:|:---:|:----:|:---:|\n",
    "|0       | Sí  | 0    | -|\n",
    "|1       | Sí  | 4    | 0|\n",
    "|2       | Sí  | 12   | 1|\n",
    "|3       | No  | 19   | 2|\n",
    "|4       | No  | 21   | 5|\n",
    "|5       | Sí  | 11   | 6|\n",
    "|6       | Sí  | 9    | 7|\n",
    "|7       | Sí  | 8    | 0|\n",
    "|8       | Sí  | 14   | 2|\n",
    "\n",
    "**Paso 8 (Visita del nodo `3`):**\n",
    "El nodo `3` es visitado y actualizamos la distancia para `4`.\n",
    "\n",
    "|Vértice | Vis | Dist | Prev|\n",
    "|:------:|:---:|:----:|:---:|\n",
    "|0       | Sí  | 0    | -|\n",
    "|1       | Sí  | 4    | 0|\n",
    "|2       | Sí  | 12   | 1|\n",
    "|3       | Sí  | 19   | 2|\n",
    "|4       | No  | 21   | 5|\n",
    "|5       | Sí  | 11   | 6|\n",
    "|6       | Sí  | 9    | 7|\n",
    "|7       | Sí  | 8    | 0|\n",
    "|8       | Sí  | 14   | 2|\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0e33cf8",
   "metadata": {},
   "source": [
    "Repetimos los pasos anteriores hasta que se incluyan todos los vértices del grafo dado. Finalmente, obtenemos el siguiente *Árbol de Camino Más Corto* (*SPT*, por sus siglas en inglés).\n",
    "\n",
    "Finalmente, el **Paso 9 (Visita del nodo `4`):**\n",
    "El nodo `4` es el último nodo que visitamos y finalizamos el algoritmo.\n",
    "\n",
    "<table id=\"mytable\" border=0>\n",
    "<tr>\n",
    "<td rowspan='2'> <img src=\"https://github.com/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/Images/Dijkstra06.PNG?raw=true\" width=\"350\"/></td>\n",
    "<td style=\"height:50%\"> \n",
    "<table border=\"1\">\n",
    "    <thead>\n",
    "        <tr>\n",
    "            <th>Vértice</th>\n",
    "            <th>Vis</th>\n",
    "            <th>Dist</th>\n",
    "            <th>Prev</th>\n",
    "        </tr>\n",
    "    </thead>\n",
    "    <tbody>\n",
    "        <tr>\n",
    "            <td>0</td>\n",
    "            <td>Sí</td>\n",
    "            <td>0</td>\n",
    "            <td>-</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>1</td>\n",
    "            <td>Sí</td>\n",
    "            <td>4</td>\n",
    "            <td>0</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>2</td>\n",
    "            <td>Sí</td>\n",
    "            <td>12</td>\n",
    "            <td>1</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>3</td>\n",
    "            <td>Sí</td>\n",
    "            <td>19</td>\n",
    "            <td>2</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>4</td>\n",
    "            <td>Sí</td>\n",
    "            <td>21</td>\n",
    "            <td>5</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>5</td>\n",
    "            <td>Sí</td>\n",
    "            <td>11</td>\n",
    "            <td>6</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>6</td>\n",
    "            <td>Sí</td>\n",
    "            <td>9</td>\n",
    "            <td>7</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>7</td>\n",
    "            <td>Sí</td>\n",
    "            <td>8</td>\n",
    "            <td>0</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>8</td>\n",
    "            <td>Sí</td>\n",
    "            <td>14</td>\n",
    "            <td>2</td>\n",
    "        </tr>\n",
    "    </tbody>\n",
    "</table>\n",
    "\n",
    "\n",
    "</td>\n",
    "</tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c840bcd",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "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.12.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "256px"
   },
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}