Describir grafos

Aquí está una manera de representar una red social:

Una línea entre los nombres de dos personas significa que se conocen. Si no hay líneas entre dos nombres, entonces las personas no se conocen. La relación "se conocen" es bidireccional. Por ejemplo, como Audrey conoce a Gayle, eso significa que Gayle conoce a Audrey.

Esta red social es un grafo. Los nombres son los vértices del grafo. (Si solo hablas acerca de uno de ellos, es un vértice.) Cada línea es una arista, que conecta dos vértices. A una arista que conecta dos vértices $u$‍ y $v$‍ la denotamos por el par $(u,v)$‍. Como la relación "se conocen" es bidireccional, este grafo es no dirigido. Una arista no dirigida $(u,v)$‍ es la misma que $(v,u)$‍. Más adelante veremos grafos dirigidos, en donde las relaciones entre los vértices no necesariamente son bidireccionales. En un grafo no dirigido, una arista entre dos vértices, como el que está entre Audrey y Gayle, es incidente sobre los dos vértices, y decimos que los vértices que están conectados por una arista son adyacentes o vecinos. El número de aristas incidentes sobre un vértice es el grado del vértice.

Audrey y Frank no se conocen. Supón que Frank quisiera que le presentaran a Audrey. ¿Cómo podría lograrlo? Bueno, él conoce a Emily, quien conoce a Bill, quien conoce a Audrey. Decimos que hay un camino de tres aristas entre Frank y Audrey. De hecho, ese es el camino más directo de que a Frank le presenten a Audrey; no hay ningún camino entre ellos con menos de tres aristas. A un camino entre dos vértices con el menor número de aristas lo llamamos un camino más corto. En el siguiente diagrama resaltamos ese camino más corto:

Cuando un camino va de un vértice en particular de regreso a sí mismo, eso es un ciclo. La red social contiene muchos ciclos; uno de ellos va de Audrey a Bill a Emily a Jeff a Harry a Ilana y de regreso a Audrey. A continuación se muestra un ciclo más corto que contiene a Audrey: de Audrey a Bill a Gayle y de regreso a Audrey. ¿Qué otros ciclos puedes encontrar?

Algunas veces ponemos valores numéricos en las aristas. Por ejemplo, en la red social podríamos usar valores para indicar qué tan bien se conocen dos personas. Para usar otro ejemplo, vamos a representar un mapa de caminos como un grafo. Si suponemos que no hay calles de un solo sentido, una mapa de caminos también es un grafo no dirigido con las ciudades como los vértices, los caminos como las aristas y los valores en las aristas que indican la distancia de cada camino. Por ejemplo, aquí está un mapa, no a escala, de algunas carreteras interestatales del noreste de los Estados Unidos, con las distancias junto a las aristas:

El término general que usamos para un número que ponemos sobre una aristas es su peso, y un grafo cuyas aristas tengan pesos es un grafo ponderado. En el caso del mapa de caminos, si quieres encontrar la ruta más corta entre dos ciudades, estás buscando el camino entre dos vértices que tenga un valor mínimo para la suma de los pesos de las aristas sobre todos los caminos entre los dos vértices. Como con los grafos no ponderados, a tal camino lo llamamos un camino más corto. Por ejemplo, el camino más corto de Nueva York a Concord en este grafo va de Nueva York a New Haven a Hartford a Sturbridge a Weston a Reading a Concord, con un total de 289 millas.

La relación entre los vértices no siempre es bidireccional. En un mapa de caminos, por ejemplo, podría haber calles de un solo sentido. O aquí está un grafo que muestra el orden en que podría vestirse un portero de hockey sobre hielo:

Ahora las aristas, mostradas con flechas, están dirigidas, y tenemos un grafo dirigido. Aquí, las direcciones muestran qué partes del equipo deben ponerse antes que otras. Por ejemplo, la arista de la pechera al suéter indica que la pechera se debe poner antes que el suéter. Los números junto a los vértices muestran uno de los posibles órdenes en cómo se podría poner el equipo, de modo que los calzoncillos van primero, luego los calcetines, luego los shorts de compresión, y así sucesivamente, con el bloqueador hasta el final. Puede que hayas notado que este grafo dirigido en particular no tiene ciclos; a un grafo de este tipo lo llamamos grafo acíclico dirigido, o gad. Por supuesto, podemos tener grafos dirigidos ponderados, tal como el mapa de caminos con calles de un solo sentido y distancias de los caminos.

Usamos un terminología diferente con las aristas dirigidas. Decimos que una arista dirigida sale de un vértice y entra en otro. Por ejemplo, una arista dirigida sale del vértice de la pechera y entra en el del suéter. Si una arista dirigida sale del vértice $u$‍ y entra en el vértice $v$‍, la denotamos como $(u,v)$‍, y es importante el orden de los vértices en la pareja. El número de aristas que salen de un vértice es su grado de salida y el número de aristas que entran es el grado de entrada.

Como te podrás imaginar, los grafos (tanto dirigidos como no dirigidos) tienen muchas aplicaciones para modelar relaciones en el mundo real.

Cuando trabajamos con grafos, es útil poder hablar acerca del conjunto de vértices y del de aristas. Usualmente denotamos el conjunto de vértices con $V$‍ y el de aristas con $E$‍. Cuando representamos un grafo o ejecutamos un algoritmo sobre él, a menudo queremos usar el tamaño de los conjuntos de vértices y aristas en notación asintótica. Por ejemplo, supón que queremos hablar acerca de un tiempo de ejecución que es lineal en el número de vértices. Estrictamente hablando, deberíamos decir que es $\mathrm{\Theta }(|V|)$‍, al usar la notación $|\cdot |$‍ para denotar el tamaño del conjunto. Pero usar esta notación del tamaño del conjunto en la notación asintótica es engorroso, así que adoptamos la convención de que en la notación asintótica, y solo en la notación asintótica, eliminamos la notación del tamaño de un conjunto, con el entendimiento de que estamos hablando del tamaño de conjuntos. Así que en lugar de escribir $\mathrm{\Theta }(|V|)$‍, simplemente escribimos $\mathrm{\Theta }(V)$‍. Del mismo modo, en lugar de $\mathrm{\Theta }(\lg |E|)$‍, escribimos $\mathrm{\Theta }(\lg E)$‍.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.