algoritmia_voraces_grafos_2.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# <center>Algoritmos Voraces</center>\n",
        "## <center>Grafos (continuación)</center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Estructuras de Datos para Grafos\n",
        "\n",
        "Hay dos formas en las cuales se puede almacenar la información de un grafo o un grafo dirigido: \n",
        "\n",
        "* Lista de adyacencia.\n",
        "* Matriz de adyacencia."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Lista de Adyacencia**\n",
        "\n",
        "La representación de un grafo en forma de lista de adyacencia utiliza un arreglo de listas. Existe una lista por cada vértice.\n",
        "\n",
        "Para un grafo no dirigido, se requieren entradas simétricas. Por lo tanto si $\\{u,v\\}$ es una arista, entonces $v$ aparecerá en la lista de adyacencia de $u$ y $u$ aparecerá en la lista de adyacencia de $v$.\n",
        "\n",
        "<center><img src=\"media/lista_grafo.png\" width=50%/></center>\n",
        "<br>\n",
        "<center><img src=\"media/lista_grafo_pesado.png\" width=50%/></center>\n",
        "<br>\n",
        "<center><img src=\"media/lista_grafo_dirigido.png\" width=50%/></center>\n",
        "<br>\n",
        "<center><img src=\"media/lista_grafo_dirigido_pesado.png\" width=50%/></center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%html\n",
        "<center><iframe src=\"https://drive.google.com/file/d/1iKu447heBjk_SuecsuMdtkTPR0ifvcDn/preview\" width=\"640\" height=\"480\"></iframe></center>"
      ],
      "outputs": [],
      "execution_count": null,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-11-11T15:53:09.356Z",
          "iopub.execute_input": "2020-11-11T15:53:09.388Z",
          "iopub.status.idle": "2020-11-11T15:53:09.514Z",
          "shell.execute_reply": "2020-11-11T15:53:09.552Z"
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Matriz de Adyacencia**\n",
        "\n",
        "La matriz de adyacencia usa un arreglo bidimensional para representar el grafo. Para un grafo no pesado, las entradas de la matriz pueden ser valores booleanos, en donde  verdadero representa la presencia de una arista y falso la ausencia de la misma. Otro método popular es usar el valor de $1$ para una arista y $0$ para indicar que no son adyecentes los vértices.\n",
        "\n",
        "Para un grafo pesado la matriz contendrá los pesos. En el caso que no exista una arista se considera un valor infinito para representarlo.\n",
        "\n",
        "<center><img src=\"media/matriz_grafo.png\" width=50% /></center>\n",
        "<br>\n",
        "<center><img src=\"media/matriz_grafo_pesado.png\" width=50% /></center>\n",
        "<br>\n",
        "<center><img src=\"media/matriz_grafo_dirigido.png\" width=50% /></center>\n",
        "<br>\n",
        "<center><img src=\"media/matriz_grafo_dirigido_pesado.png\" width=50% /></center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%html\n",
        "<center><iframe src=\"https://drive.google.com/file/d/1HANlHtJkyu1h5bvXAxGfl-CdBbu_kzNx/preview\" width=\"640\" height=\"480\"></iframe></center>"
      ],
      "outputs": [],
      "execution_count": null,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-11-11T15:53:27.357Z",
          "iopub.execute_input": "2020-11-11T15:53:27.390Z",
          "iopub.status.idle": "2020-11-11T15:53:27.681Z",
          "shell.execute_reply": "2020-11-11T15:53:27.718Z"
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Eficiencia de Almacenamiento**\n",
        "\n",
        "En una matriz de adyacencia se reserva almacenamiento para todas las combinaciones de vértices (o almenos la mitad de ellos). Por lo tanto el almacenamiento requerido es proporcional a $|V|²$ siendo $|V|$ la cantidad de nodos en el grafo. Si el grafo es disperso (sin muchas aristas), habrá mucho espacio desperdiciado en la matriz de adyacencia. En una lista de adyacencia, sólo las aristas se almacenan.\n",
        "\n",
        "Por otra parte, en una lista de adyacencia, cada arista es representada por un objeto que contiene datos sobre el origen, el destino y el peso. También hay apuntadores a las aristas siguiente y anterior en la lista. En una representación matricial, sólo el peso asociado con la arista se almacena. Por lo tanto cada elemento en una lista de adyacencia requiere aproximadamente cinco veces el almacenamiento de un elemento en una matriz de adyacencia."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    }
  ],
  "metadata": {
    "kernel_info": {
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.7.3",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "kernelspec": {
      "argv": [
        "python",
        "-m",
        "ipykernel_launcher",
        "-f",
        "{connection_file}"
      ],
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "nteract": {
      "version": "0.26.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}