Gráficos en Python - Teoría e implementación - Teoría de grafos y algoritmos relacionados con grafos

Los gráficos son una estructura de datos extremadamente versátil. ¡Más de lo que la mayoría de la gente cree! Los gráficos se pueden usar para modelar prácticamente cualquier cosa, dada su naturaleza de modo...

Los gráficos son una estructura de datos extremadamente versátil. ¡Más de lo que la mayoría de la gente cree! Los gráficos se pueden usar para modelar prácticamente cualquier cosa, dada su naturaleza de relaciones y jerarquías de modelado.

La naturaleza y las creaciones humanas son extremadamente jerárquicas.

Las palabras en una oración y las oraciones en un libro pueden ser gráficos, representados como una cuadrícula. Los píxeles de una imagen también pueden ser un gráfico. Un gráfico puede representar una secuencia de pasos que desea realizar o una secuencia de operaciones que ejecuta un algoritmo. ¡Un gráfico puede representar una molécula, sus arreglos, hasta humanos y sus relaciones, hasta calles e intersecciones, hasta ciudades, países, planetas!

Desde una escala atómica hasta una escala universal: los gráficos se pueden usar para modelar cualquier tipo de relación o jerarquía.

Muchos problemas comunes en el mundo se pueden representar en gráficos. ¿Dónde abrir restaurantes para cubrir un área con tiempos de entrega garantizados, con la mínima inversión? ¿Dónde enrutar a un conductor para evitar la congestión y llegar a un lugar de destino lo antes posible? ¿Cómo organizar el flujo de energía eléctrica en las redes de una ciudad? No faltan los problemas inherentemente basados ​​en gráficos.

Los gráficos han sido un modelo computacional importante en el pasado, y todavía lo son hoy. No es que tu universidad solo quiera que los aprendas, son realmente una de las estructuras de datos más útiles que existen. Recientemente, los gráficos también se han explorado en contextos más nuevos. Por ejemplo, Gráfico Redes de Atención describe un nuevo tipo de redes neuronales artificiales que operan en gráficos, escrito por Petar Veličković et al. en 2018 ha sido citado más de 7300 veces. Ha encontrado una gran aplicación en los campos de la química computacional y el descubrimiento de fármacos, y la idea se implementa en prácticamente todos los marcos que tratan con el modelado de moléculas como gráficos.

Comenzar con los gráficos puede ser desalentador. La literatura puede estar dispersa y la búsqueda en línea generalmente implica varias implementaciones diferentes y una falta de continuidad entre el material que está leyendo.

Por esa razón, estamos compilando un curso de introducción a Gráficos en Python, en un intento de estandarizar los fundamentos para ayudarlo a formar una base sólida en la teoría de gráficos. El curso está destinado a expandirse a través del tiempo, con la adición de nuevos algoritmos.

Gráficos simplificados

Los gráficos pueden ser más complicados de lo justificado. Fundamentalmente, son bastante simples, pero dado el uso interdisciplinario de ellos, la terminología puede volverse confusa, ya que se superpone y ciertos sinónimos de repente ya no se refieren a lo mismo. Por lo general, encontrará personas que no están de acuerdo en términos de terminología en el campo, y especialmente en línea. Si el inglés no es su idioma nativo y ha estudiado teoría de grafos en un idioma diferente, la libertad del traductor y la pérdida de contexto entre traducciones pueden hacer que sea aún más confuso.

¿Qué es verdad?

Como con la mayoría de las cosas, es difícil saberlo. No puede referirse a la "fuente original" ya que los campos científicos cambian con el tiempo, y el estándar de "verdad" cambia con ellos. Lo mejor que puede hacer es aceptar que hay varias definiciones y terminologías (ligeramente diferentes) y abstenerse de argumentos semánticos. El punto es bastante sencillo.

Cada gráfico consta de nodos (también llamados vértices) y bordes, también conocidos como arcos. ¡Aquí es donde se puede plantear el primer argumento semántico! Los informáticos los llaman más comúnmente nodos y bordes. Los matemáticos suelen utilizar los términos vértice y arista, pero también arco, y distinguen entre una arista (no dirigida) y un arco (dirigida). Además, no todos los combinatorialistas y geometristas están de acuerdo aquí tampoco. La literatura oficial de las universidades también difiere aquí. Algunos no atribuyen una diferencia entre bordes y arcos, mientras que otros sí lo hacen.

{.icon aria-hidden=“true”}

Nota: A lo largo del curso, usaremos la notación informática de nodo y borde por motivos de coherencia.

El punto es: podemos ver los nodos/vértices como "fragmentos de datos" y los bordes/arcos como "relaciones entre esos fragmentos de datos".

A menudo también verás esta notación:

$$
G = (V, E)
$$

O:

$$
G = (N, E)
$$

Un grafo (G), consta de vértices/nodos (V/N) y aristas (E). ¿Puedes adivinar qué fórmula fue escrita por un matemático y cuál por un informático?

Si queremos señalar que dos fragmentos de datos están relacionados entre sí de alguna manera, los conectaríamos con un borde. Los nodos generalmente se representan como círculos con una marca de identificación en ellos, para que podamos distinguir entre nodos, y los bordes se representan mediante líneas (o flechas, como veremos más adelante) que conectan dos nodos. Esto es solo una abstracción interpretable por humanos.

Una forma de la estructura de datos del gráfico se usa a menudo al hacer mapas para las líneas de autobús o metro de una ciudad. Por ejemplo, si alguna vez has estado en una estación de metro/autobús, verás un mapa simplificado de la ciudad, con un montón de estaciones. Cada estación es un nodo en un gráfico, y las líneas que sigue un metro/autobús son bordes de ese gráfico:

Este gráfico muestra qué diferentes paradas de autobús tenemos y cómo están conectadas. Por ejemplo, podemos ver que, usando esta línea de autobús, para ir de la Parada de autobús A a la Parada de autobús C tendríamos que pasar por la Parada de autobús B - no podemos llegar a ninguna otra camino.

Gráficos ponderados

Digamos que quisiéramos agregar información sobre cuánto tiempo tomó en promedio (en minutos) ir de una parada de autobús a otra. Agregaríamos "pesos" a nuestros bordes:

Los pesos pueden representar cualquier medida arbitraria. En el caso de un mapa representado como un gráfico, podría ser el tiempo que lleva atravesar ese borde. O - podría ser la congestión actual. En el caso de una molécula, el peso podría ser la fuerza de la conexión entre los átomos. En el caso de una red eléctrica, podría ser la resistencia del cable o la pérdida de energía al transferir electricidad. Esto depende en gran medida del problema específico que está modelando con un gráfico y el dominio de ese problema.

¡Volvamos a las paradas de autobús! Ahora nuestro gráfico muestra aún más información que antes, vemos cuánto se tarda en llegar de una parada a otra. Podemos deducir que ir de la Parada de autobús A a la Parada de autobús C tardaría 23 minutos, ya que tendríamos que "atravesar" el borde que conecta la Parada de autobús A y la Parada de autobús B que tiene una peso de 15 y el borde (Parada de autobús B -> Parada de autobús C), que tiene un peso de 8.

Gráficos dirigidos y no dirigidos {#gráficos dirigidos y no dirigidos}

Ahora veremos otro concepto de gráfico: gráficos dirigidos y no dirigidos. Digamos que nuestra línea de autobús no tenía las mismas paradas en ambos sentidos.

Más precisamente, cuando nuestro autobús parte de la Parada de autobús A, pasa por B, C y termina en D; sin embargo, en la otra dirección no pasa por C sino por una parada de autobús completamente diferente E, antes de pasar por B. Podríamos hacer algo como esto:

Como sugiere el spoiler en la imagen, este enfoque no es correcto. Con solo mirar este gráfico, no podemos entender por qué parada de autobús pasa el autobús en qué dirección, ya que nada nos impide ir de B a E, aunque solo deberíamos poder llegar desde * E* a B.

Aquí es donde entran en juego los gráficos dirigidos. Los bordes en los gráficos dirigidos se representan mediante flechas en lugar de líneas, una flecha que apunta de A a B significa que "podemos ir de A a B pero no al revés". Si quisiéramos decir que podemos ir tanto de A a B como de B a A, usaríamos una flecha de dos lados.

Ahora, el ciclo ya no es ambiguo:

Ahora está claro que no podemos pasar de B a E o de D a C, etc. Está claro que podemos hacer gráficos tan simples o tan complejos como queramos. querer. Podríamos ir un paso más allá en nuestro ejemplo, si por alguna razón el tiempo de viaje entre algunas paradas de autobús fuera diferente dependiendo de la dirección en la que vamos.

Gráficos conectados y desconectados {#gráficos conectados y desconectados}

Un gráfico también puede estar conectado y desconectado. Un grafo es conexo si hay un camino (que consiste en uno o más bordes) entre cada par de nodos. Por otro lado, un gráfico está desconectado si hay un par de nodos que no pueden estar conectados por un camino de aristas.

{.icon aria-hidden=“true”}

Nota: Un concepto erróneo frecuente es que los gráficos deben estar conectados, o al menos que cada nodo debe estar conectado a otro de alguna manera. Esto no es cierto. Un gráfico puede consistir fácilmente en cualquier número de nodos sin un solo borde entre ellos. Sin embargo, muchos algoritmos transversales requieren que los gráficos estén conectados para funcionar correctamente.

Aplicaciones de los gráficos

Aquí hay algunos ejemplos de datos que pueden almacenarse/representarse convenientemente mediante gráficos, teniendo en cuenta que esto es solo un grano de arena en la playa:

  • Modelado de la naturaleza: Como se indicó anteriormente, muchas cosas en la naturaleza se modelan naturalmente como un gráfico, desde moléculas hasta galaxias.
  • Un conjunto de personas y sus afiliaciones: Esto se puede hacer usando un gráfico no dirigido, ya que asumimos que si la persona A conoce a la persona B, lo mismo es cierto y viceversa (con suerte). Las diferentes personas estarían representadas por nodos, y si la persona A conoce a la persona B, habrá un borde que conecte los dos nodos.
  • La estructura de un sitio web: Las diferentes páginas de un sitio web son nodos, y hay un borde dirigido entre la página A y la página B si existe un enlace a la página B en la página A. Por ejemplo, la página de inicio a menudo tiene enlaces a una página Acerca de nosotros y Contacto.
  • Tareas mutuamente dependientes: Podemos representar qué tareas deben completarse antes de la tarea A y qué tareas no pueden completarse antes de que A se haya completado de la siguiente manera: si hay un borde dirigido desde *B * a A, entonces A no se puede completar antes de que se complete B; si hay un borde dirigido de A a C, entonces C no se puede completar antes de que se complete A:

Aquí podemos ver que podemos ponernos gafas, calcetines, pantalones y una camiseta independientemente de la otra ropa. Pero no podemos ponernos los zapatos antes de ponernos los pantalones y los calcetines. Y no podemos salir antes de hacer todo lo demás, excepto ponernos las gafas, ya que pueden no ser necesarias. Estos tipos de gráficos se clasifican fácilmente y podemos ver un orden factible de ejecución de tareas usando Clasificación topológica.

Gráficos comparados con árboles

Si está familiarizado con los árboles, los gráficos son fáciles de entender: los árboles son un tipo especial de gráfico, es decir, gráficos con ciertas restricciones. Todo árbol es un gráfico, pero no todo gráfico es un árbol.

Por definición, los árboles son grafos no dirigidos que:

  • Son acíclicos, es decir, no podemos volver a ningún nodo inicial que elijamos sin retroceder
  • Se crea un ciclo agregando cualquier borde al árbol existente
  • La ruta entre dos nodos cualesquiera es única.
  • Hay un nodo raíz distinto
  • El gráfico está conectado (hay un camino entre cada dos nodos)

O en términos muy simplificados: los árboles son gráficos conectados sin ciclos. Para los gráficos, simplemente nos deshacemos de todas estas restricciones y mantenemos el concepto de nodos y bordes. Volveremos a los árboles más adelante, cuando comencemos a cubrir los algoritmos que están destinados a operar en árboles específicamente.

Gráficos como término matemático

Los gráficos se originaron a partir de las matemáticas, por lo que vale la pena dedicar al menos un par de párrafos para definir una definición más formal. Un gráfico es un par ordenado G = (N, E), donde N es un conjunto de nodos y E es el conjunto de aristas.

Gráficas no dirigidas: E ⊆ {{x, y} | (x, y) ∈ N^2}. A veces se agrega una condición adicional si queremos evitar bordes que tengan el mismo punto inicial y final (es decir, x ≠ y).

Gráficas dirigidas: E ⊆ {(x, y) | (x, y) ∈ N^2}, aquí también podemos agregar la condición x ≠ y si queremos evitar aristas que comiencen y terminen en el mismo nodo.

Como podemos ver en las definiciones anteriores del conjunto de aristas E, la única diferencia es que en el caso de grafos dirigidos (x,y) es un par ordenado, mientras que en grafos no dirigidos el par {x, y} está desordenado. Esto significa que en un gráfico no dirigido, lo que importa es que x e y estén conectados, no en "en qué orden". Así que podríamos haber escrito {y,x} en lugar de {x,y} mientras que no podríamos haber escrito (y,x) en lugar de (x,y) para un gráfico dirigido.

En las siguientes lecciones, nos sumergiremos en las representaciones gráficas en el código (listas de bordes, matrices de adyacencia y listas de adyacencia, así como sus implementaciones). Luego, cubriremos algunos de los algoritmos más importantes y ampliamente utilizados para el recorrido de gráficos y la búsqueda de gráficos, comenzando con los más simples e intuitivos, y avanzando desde allí:

  • Búsqueda primero en amplitud y búsqueda primero en profundidad
  • Algoritmo de Dijkstra
  • A*
  • Algoritmo de Prim
  • Algoritmo de Boruvka
  • Algoritmo de Kruskal
Licensed under CC BY-NC-SA 4.0