algoritmia_grafos_1.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# <center>Grafos</center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Formalmente, un grafo es un par ordenado, $G=(V,E)$ de dos conjuntos representando los nodos o vértices del grafo y las aristas del grafo. Una arista especifica cuáles nodos tienen una conexión entre ellos.\n",
        "\n",
        "Ambos, el conjunto de vértices y aristas deben ser finitos y cualquiera puede ser vacío. Si el conjunto de vértices está vacío, naturalmente el conjunto de aristas debe ser también vacío.\n",
        "\n",
        "### Ejemplo\n",
        "\n",
        "El siguiente conjunto de vértices, $V$ y conjunto de aristas $E$ definen un grafo que tiene cinco vértices, con etiquetas $A$ hasta $E$ y cuatro aristas.\n",
        "\n",
        "$V = \\{A, B, C, D, E\\}$\n",
        "\n",
        "$E = \\{\\{A, B\\}, \\{A, D\\}, \\{C, E\\}, \\{D, E\\}\\}$\n",
        "\n",
        "Cada arista es un conjunto de dos vértices. Hay una arista entra $A$ y $B$ (la arista $\\{A, B\\}$), entre $A$ y $D$, entre $C$ y $E$ y entre $D$ y $E$."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Aplicaciones\n",
        "\n",
        "Los grafos son sencillos de definir: sólo se toma una colección de cosas y se unen por aristas.\n",
        "\n",
        "* __Redes de transporte.__ El mapa de rutas atendido por un servicio de transporte aéreo forma naturalmente un grafo: Los nodos son los aeropuertos y hay una arista de $u$ hacia $v$ si hay un vuelo sin escalas que despega de $u$ y llega a $v$.\n",
        "\n",
        "* __Redes de comunicación.__ Una colección de computadoras conectadas a través de una red de comunicación puede ser modelada naturalmente como un grafo. Se podría tener un nodo para cada computadora y una arista uniendo $u$ y $v$ si existe una conexión física directa entre ellas.\n",
        "\n",
        "* __Redes de información.__ La World Wide Web pude ser vista como un grafo dirigido en el cual los nodos corresponden a páginas Web y hay una arista desde $u$ hacia $v$ si $u$ tiene un hipervínculo hacia $v$.\n",
        "\n",
        "* __Redes sociales.__ Dada una colección de personas que interactúan se puede definir una red cuyos nodos son personas, con una arista uniendo $u$ y $v$ si existe algún tipo de relación entre ambos.\n",
        "\n",
        "* __Redes de dependencia.__ Es natural definir grafos dirigidos que capturen las interdependencias entre una colección de objetos. Por ejemplo, dada una lista de cursos ofrecidos por un colegio o universidad, se podría tener un nodo por cada curso y una arista desde $u$ hacia $v$ si $u$ es un prerrequisito para $v$."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Representación Visual de Grafos\n",
        "\n",
        "Visualmente se representan los vértices como puntos o círculos etiquetados y las aristas como líneas uniendo los vértices.\n",
        "\n",
        "Hay muchas formas de dibujar un grafo dado. El acomodo físico de los vértices e incluso su etiquetado no son relevantes.\n",
        "\n",
        "<center><img src=\"media/grafos_1.png\" width=50%/></center>\n",
        "\n",
        "\n",
        "**Ejemplo** : Dos representaciones del mismo grafo\n",
        "\n",
        "<center><img src=\"media/grafos_2.png\" width=50%/></center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Grafos Dirigidos y Grafos No Dirigidos\n",
        "\n",
        "Las aristas de un grafo son **dirigidas** si la existencia de una arista de $A$ a $B$ no necesariamente garantiza que haya un camino en ambas direcciones. Un grafo que contiene aristas dirigidas es conocido como un **grafo dirigido**, y un grafo que contiene aristas no dirigidas es conocido como **grafo no dirigido** o simplemente grafo.\n",
        "\n",
        "\n",
        "**Ejemplo**\n",
        "\n",
        "<center><img src=\"media/grafo_dirigido.png\" width=50%/></center>\n",
        "\n",
        "$$E = \\{(A,B),(B,A),(B,E),(D,A),(E,A),(E,C),(E,D)\\}$$\n",
        "\n",
        "Cada arista en la lista de aristas para el grafo dirigido es un par ordenado de vértices, en lugar de un conjunto como en un grafo no dirigido. La arista $(A, B)$ es una arista que va desde $A$ (origen) a $B$ (destino).\n",
        "\n"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Las aristas en un grafo pueden tener valores asociados con ellas, conocidos como sus **pesos**. Un grafo con aristas pesadas es conocido como un grafo pesado. En una ilustración de un **grafo pesado**, los pesos se muestren junto a las aristas.\n",
        "\n",
        "<center><img src=\"media/grafo_pesado.png\" width=50%/></center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Caminos y Ciclos\n",
        "\n",
        "Una razón por la que se estudian los grafos en para encontrar caminos entre vértices. Se utilizan las siguientes definiciones para describir caminos entre vértices.\n",
        "\n",
        "* Un vértice es **adyacente** a otro vértice si hay una arista desde el primero hacia el segundo.\n",
        "\n",
        "* Un **camino** es una secuencia de vértices en el cual cada vértice sucesivo es adyacente a su predecesor.\n",
        "\n",
        "* En un **camino simple** los vértices y aristas son distintos, excepto por el primer y último vértice que pueden ser el mismo.\n",
        "\n",
        "* Un **ciclo** es un camino sencillo en el cual sólo el primer y último vértice son el mismo. Para un grafo no dirigido, un ciclo debe contener al menos tres vértices distintos."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Ejemplos**\n",
        "\n",
        "<center><img src=\"media/camino_simple.png\" width=50%/></center>\n",
        "\n",
        "\n",
        "<center><img src=\"media/camino_no_simple.png\" width=50%/></center>\n",
        "\n",
        "\n",
        "<center><img src=\"media/ciclo.png\" width=50%/></center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "* Un grafo no dirigido es llamado un grafo **conectado** si hay un camino desde cada vértice hacia todos los demás vértices.\n",
        "\n",
        "* Si un grafo no está conectado, puede consistir de componentes conectados. Un **componente conectado** es un subconjunto de vértices y las aristas conectadas a esos vértices en los cuáles hay un camino entre cada par de vértices en el componente.\n",
        "\n",
        "<center><img src=\"media/grafo_no_conectado.png\" width=50%/></center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Ejercicio práctico opcional\n",
        "\n",
        "Dibuja el siguiente grafo: $G = (\\{1, 2, 3, 4, 5, 6\\}, \\{\\{1,2\\}, \\{1, 3\\}, \\{2,3\\}, \\{2,5\\}, \\{2,6\\}, \\{3,5\\}, \\{3,6\\}, \\{4,2\\}, \\{5,1\\}, \\{5,4\\}, \\{6,1\\}, \\{6,5\\}\\})$.\n",
        "\n",
        "Dibuja el siguiente grafo dirigido: $G = (\\{1, 2, 3, 4, 5\\}, \\{(1,2), (1,4), (1,5), (2,1), (2,3), (2,4), (3,2), (3,5), (4,3), (4,5), (5,1), (5,2), (5,4)\\})$."
      ],
      "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.28.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}