Vértices y Aristas Explicados

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. La definición formal de grafo

Casi todas las introducciones dicen que un grafo son «puntos unidos por líneas». Esa imagen es útil y también es la razón por la que tanta gente se atasca más adelante: los puntos y las líneas no son el objeto matemático. El objeto es un par de conjuntos.

El libro de Diestel Graph Theory, la referencia estándar de posgrado, empieza con la definición en su forma más limpia:

Un grafo es un par G = (V, E) de conjuntos tal que E ⊆ [V]², donde [V]² denota el conjunto de todos los subconjuntos de 2 elementos de V.

Desglósalo y todo lo demás de este artículo se deduce de ahí:

• V es un conjunto de objetos llamados vértices. No se supone nada sobre ellos. Pueden ser ciudades, personas, páginas web, átomos químicos o números enteros. La teoría nunca mira dentro de ellos; solo le importa cuáles se pueden distinguir.
• E es un conjunto de subconjuntos de 2 elementos de V. Una arista es literalmente el conjunto {u, v}, no una flecha ni una curva. No registra nada salvo el par que une.
• Como E es un conjunto, una arista está presente o ausente. No puede aparecer dos veces.
• Como cada elemento de E tiene exactamente dos miembros distintos, una arista no puede unir un vértice consigo mismo.

Esas dos últimas consecuencias no son restricciones que alguien añadiera después. Se desprenden directamente de la teoría de conjuntos, y un grafo que las cumple se llama simple. Permitir aristas repetidas o bucles implica cambiar la propia definición, que es el tema de la sección 4.

Hay dos notaciones estándar más que encontrarás por todas partes. Cuando hay varios grafos en juego, se escribe V(G) y E(G) para indicar a qué grafo te refieres. Y las dos medidas de tamaño tienen nombre: el número de vértices es el orden del grafo, y el número de aristas es su tamaño. La mayoría de los textos de algoritmos los abrevian como n = |V| y m = |E|, y esa es la convención que se usa en todo este sitio.

Este grafo es el ejemplo recurrente del resto del artículo. Su conjunto de vértices es V = {A, B, C, D, E, F}, así que el orden es n = 6, y su conjunto de aristas es

E = { {A,B}, {A,C}, {B,C}, {B,D}, {C,D}, {D,E}, {E,F} }        así que  m = 7

2. Vértices: qué son y qué no son

Un vértice no tiene estructura propia. En el objeto formal es un elemento anónimo de un conjunto, y todo lo que se puede decir de él procede de las aristas que lo tocan. Merece la pena insistir en ello, porque es exactamente lo que hace transferible la teoría de grafos: un teorema demostrado sobre vértices es a la vez un teorema sobre aeropuertos, transistores, proteínas y commits de Git.

Tres consecuencias que hacen tropezar en la práctica:

• Los vértices se distinguen entre sí, pero por lo demás son intercambiables. Dos grafos que solo difieren en cómo se llaman sus vértices son isomorfos, y la teoría de grafos los trata como el mismo grafo. Cuando etiquetas vértices en código estás añadiendo contabilidad, no matemáticas.
• Un vértice aislado sigue siendo un vértice. Un vértice sin ninguna arista es perfectamente legal y se llama aislado. Los principiantes suelen construir un grafo a partir de una lista de aristas y pierden en silencio todos los vértices aislados, lo que cambia el orden del grafo y rompe sin avisar cualquier cosa que divida por n.
• El grafo vacío existe, y también los infinitos. Nada en la definición prohíbe V = ∅, y nada en ella prohíbe que V sea infinito, que es el tema de la guía sobre grafos finitos e infinitos. La mayoría de los textos lo permiten y unos pocos lo excluyen por decreto; lo importante es saber qué convención usa tu fuente antes de fiarte de un caso límite.

La nota histórica merece una línea, porque el vocabulario no es estable a lo largo de un siglo de literatura. El texto clásico de Harary de 1969 los llama puntos y líneas. Los físicos y muchos artículos aplicados dicen nodos y enlaces. Los químicos, siguiendo la nota de Sylvester de 1878 en Nature que dio a la materia la palabra «grafo», hablaban de átomos y enlaces. Los cuatro vocabularios describen el mismo par de conjuntos.

3. Aristas, adyacencia e incidencia

Una arista une exactamente dos vértices, y esos dos son sus extremos o puntas. De esa única relación obtienen su significado preciso las dos palabras que los principiantes intercambian con más frecuencia:

• La adyacencia es una relación entre dos vértices. Los vértices u y v son adyacentes, lo que se escribe u ~ v, cuando {u, v} ∈ E. Los vértices adyacentes también se llaman vecinos, y el conjunto de todos los vecinos de v es su vecindad, que se escribe N(v).
• La incidencia es una relación entre un vértice y una arista. La arista {u, v} es incidente a u e incidente a v, y a ningún otro vértice.

La distinción parece pedante hasta que te encuentras con una frase como «dos aristas adyacentes». Es correcta y significa dos aristas que comparten un extremo. Los vértices son adyacentes a través de una arista; las aristas son adyacentes a través de un vértice. Mantener separadas las dos relaciones es lo que permite leer sin ambigüedad una definición como la de coloración propia («los vértices adyacentes reciben colores distintos»).

En el ejemplo recurrente, N(B) = {A, C, D}, así que B tiene tres vecinos. La arista {B, D} es incidente a B y a D. Las aristas {B, D} y {C, D} son adyacentes entre sí, ya que ambas son incidentes a D.

4. Bucles y aristas paralelas: donde la definición tiene que cambiar

Los sistemas reales producen dos cosas que la definición de conjuntos no puede expresar. Una carretera que sale de una rotonda y vuelve a ella es una arista de un vértice a sí mismo. Dos vuelos distintos entre el mismo par de aeropuertos son dos aristas distintas que unen el mismo par. Con E ⊆ [V]2 no existe ninguna de las dos: {A, A} es un conjunto de un solo elemento, y un conjunto no puede contener el mismo elemento dos veces.

La solución no es una nota a pie de página, es otra definición. El libro de Bondy y Murty Graph Theory incorpora una función de incidencia explícita junto a los dos conjuntos:

G = (V, E, ψ)      donde  ψ: E → pares no ordenados de vértices (no necesariamente distintos)

Ahora una arista es un objeto con identidad propia, y ψ indica qué par une. Dos aristas distintas pueden corresponder al mismo par, lo que da aristas paralelas, también llamadas aristas múltiples. Una arista puede corresponder a un par cuyos dos elementos coinciden, lo que da un bucle. El libro de West Introduction to Graph Theory sigue el mismo camino y define un grafo como un conjunto de vértices, un conjunto de aristas y una relación que asocia a cada arista sus extremos.

El vocabulario resultante:

Dos advertencias prácticas. Primera, «multigrafo» no se usa de forma coherente: algunos autores incluyen los bucles y otros no, así que comprueba la fuente antes de citar un teorema. Segunda, un bucle aporta 2 al grado de su vértice, no 1, porque sus dos extremos se conectan allí. Esa convención no es arbitraria, y la siguiente sección explica exactamente por qué tiene que ser así.

Salvo que un texto diga lo contrario, «grafo» significa «grafo simple». Todos los resultados del resto de este artículo lo suponen, y la guía complementaria sobre grafos simples frente a multigrafos explica exactamente qué cambian esas dos concesiones y qué cotas estándar dejan de cumplirse sin ellas.

5. El grado y el primer teorema de la teoría de grafos

El grado de un vértice v, que se escribe deg(v) o d(v), es el número de aristas incidentes a él. De forma equivalente, y más útil, es el número de extremos de arista que se encuentran en v. En un grafo simple es igual al tamaño de la vecindad, deg(v) = |N(v)|.

Dos magnitudes relacionadas aparecen constantemente en cotas y demostraciones: el grado mínimo δ(G) y el grado máximo Δ(G). Un grafo en el que todos los vértices tienen el mismo grado k es k-regular.

Y ahora el teorema más antiguo de la materia, que procede del artículo de Euler de 1736 sobre los puentes de Königsberg, el artículo que fundó la teoría de grafos:

Lema del apretón de manos. En todo grafo finito, la suma de los grados de todos los vértices es igual al doble del número de aristas: ∑v∈V deg(v) = 2m.

La demostración es una línea de doble conteo. Cuenta los pares (vértice, extremo de arista que llega a él). Sumando por vértices se obtiene ∑ deg(v). Sumando por aristas se obtiene 2m, ya que cada arista tiene exactamente dos extremos. Ambos cuentan el mismo conjunto finito, así que son iguales. Observa que este argumento es también lo que obliga a contar un bucle dos veces: un bucle sigue teniendo dos extremos, y ambos caen en el mismo vértice.

Compruébalo en el ejemplo recurrente: los grados son 2, 3, 3, 3, 2, 1, que suman 14, y el grafo tiene 7 aristas. El lema tiene un corolario inmediato y muy útil.

Corolario. En cualquier grafo, el número de vértices de grado impar es par.

Divide la suma entre vértices de grado impar y de grado par. El total es par y la parte de grado par es par, así que la parte de grado impar también debe ser par, lo que obliga a que el número de sumandos impares sea par. Por eso en una fiesta nunca puede haber exactamente tres personas que hayan estrechado cada una la mano un número impar de veces, y es el mismo argumento de paridad que decide si existe un camino euleriano .

6. Sucesiones de grados: qué listas de números son grafos

Escribe los grados en orden no creciente y obtienes la sucesión de grados. Para el ejemplo recurrente es (3, 3, 3, 2, 2, 1). La pregunta natural va en sentido contrario: dada una lista de números, ¿existe un grafo con exactamente esos grados? Una lista para la que existe se llama gráfica.

El lema del apretón de manos ya descarta la mitad de los candidatos: ninguna sucesión de suma impar es gráfica. Pero esa prueba está lejos de ser suficiente. Considera (3, 3, 1, 1). La suma es 8, que es par, y ningún vértice pide más de los 3 vecinos disponibles. Aun así, ningún grafo simple la realiza: los dos vértices de grado 3 deben unirse cada uno a los otros tres vértices, lo que obliga a que ambos vértices de grado 1 tengan grado 2.

Dos resultados clásicos zanjan la cuestión por completo:

• El teorema de Erdős–Gallai (1960) da un criterio exacto: una sucesión no creciente de suma par es gráfica si y solo si, para cada k, la suma de los primeros k términos es como mucho k(k-1) más la suma, sobre los términos restantes, de min(di, k). Es una prueba en forma cerrada, comprobable en tiempo lineal tras ordenar.
• El algoritmo de Havel–Hakimi, de Havel (1955) y, de forma independiente, Hakimi (1962), es la versión constructiva: elimina el grado mayor d, resta 1 a las siguientes d entradas, reordena y repite. La sucesión original es gráfica exactamente cuando esta reducción termina en todo ceros, y los pasos sirven además como receta para construir un grafo que la realice.

Ejecuta Havel–Hakimi sobre el ejemplo que falla para verlo funcionar:

(3, 3, 1, 1)   elimina el 3, resta 1 a las tres entradas siguientes
(2, 0, 0)      reordenado
               elimina el 2, resta 1 a las dos entradas siguientes
(-1, -1)       negativo, así que la sucesión NO es gráfica

Y sobre el ejemplo recurrente, donde sí funciona:

(3, 3, 3, 2, 2, 1)  →  (2, 2, 1, 2, 1)  → ordenado (2, 2, 2, 1, 1)
(2, 2, 2, 1, 1)     →  (1, 1, 1, 1)     → ordenado (1, 1, 1, 1)
(1, 1, 1, 1)        →  (0, 1, 1)        → ordenado (1, 1, 0)
(1, 1, 0)           →  (0, 0)           → todo ceros, así que la sucesión SÍ es gráfica

Una advertencia que pilla desprevenido a mucha gente: una sucesión gráfica puede realizarse mediante varios grafos no isomorfos. Conocer todos los grados no determina el grafo.

7. Aristas dirigidas: arcos, grado de entrada y grado de salida

Sustituye el par no ordenado por un par ordenado y obtienes un grafo dirigido, o dígrafo:

D = (V, A)      con  A ⊆ V × V

Un elemento (u, v) de A es un arco o arista dirigida, que va de su cola u a su cabeza v. Como el par está ordenado, (u, v) y (v, u) son arcos distintos y ambos pueden estar presentes. El libro de Bang-Jensen y Gutin Digraphs es la referencia estándar para la terminología, y reserva «arco» para el objeto dirigido precisamente para evitar la ambigüedad de llamar aristas a ambas cosas.

El grado se divide en dos:

• Grado de salida d+(v), el número de arcos cuya cola es v.
• Grado de entrada d-(v), el número de arcos cuya cabeza es v.

El lema del apretón de manos se divide con él. Cada arco tiene exactamente una cola y exactamente una cabeza, así que contar por separado las colas y las cabezas da

∑v∈V d+(v)  =  ∑v∈V d-(v)  =  |A|

Fíjate en el factor 2 que falta: en el caso no dirigido cada arista aportaba dos extremos a una suma; aquí cada arco aporta un extremo a cada una de dos sumas. La comparación completa, incluidas las orientaciones, los tres tipos de conectividad y qué algoritmos sobreviven, está en la guía sobre grafos dirigidos frente a no dirigidos. Los vértices con grado de entrada 0 son fuentes y los de grado de salida 0 son sumideros, que es exactamente el vocabulario sobre el que se construyen el orden topológico y el flujo en redes .

8. Aristas ponderadas, y por qué los pesos quedan fuera del grafo

Los problemas de caminos más cortos necesitan distancias, los de flujo necesitan capacidades y los de planificación necesitan duraciones. Nada de eso está en G = (V, E), y no debe estarlo. Un grafo ponderado es un grafo más una función:

w: E → ℝ        asigna un número real a cada arista

Mantener los pesos en una función aparte, en lugar de dentro de las aristas, es lo que permite que un mismo grafo lleve varios modelos de coste a la vez. La misma red de carreteras es un grafo con tres funciones de peso: kilómetros, minutos y combustible. La guía complementaria sobre grafos ponderados frente a no ponderados sigue esa idea a través de la elección de algoritmo, los pesos negativos y la fuerza de un vértice. Cambiar la función cambia todos los caminos más cortos sin tocar un solo vértice ni una sola arista.

También explica por qué los algoritmos vienen con condiciones sobre w y no sobre el grafo. El algoritmo de Dijkstra exige w(e) ≥ 0 para toda arista; Bellman-Ford tolera pesos negativos pero no ciclos negativos. Esas son restricciones sobre la función, y al par de conjuntos subyacente le son indiferentes.

9. ¿Cuántas aristas puede tener un grafo?

En un grafo simple con n vértices, una arista es una elección de 2 vértices distintos entre n, así que el máximo es el coeficiente binomial

mmax = C(n, 2) = n(n - 1) / 2

El grafo que lo alcanza, en el que todo par de vértices es adyacente, es el grafo completo Kn. Para el ejemplo recurrente, n = 6 da un techo de 15 aristas, y el grafo usa 7 de ellas. La razón 2m / (n(n-1)) es la densidad, aquí 0,47.

Esa única cota es la razón de que dos expresiones dominen la literatura de algoritmos:

• Un grafo denso tiene m cerca de su máximo, es decir, m = Θ(n2).
• Un grafo disperso tiene m muy por debajo, normalmente m = O(n) o O(n log n). Casi toda red real grande es dispersa: los mapas de carreteras, los grafos sociales y los grafos web tienen un grado medio de una o dos cifras por muchos vértices que contengan.

La dispersión no es un detalle. Decide qué estructura de datos usar, que es la siguiente sección, y es la razón por la que una complejidad de O(m log n) gana a O(n2) con entradas reales aunque las dos sean idénticas en el peor caso.

10. Almacenar vértices y aristas en código

Hay tres formas estándar de guardar V y E en memoria, y Cormen, Leiserson, Rivest y Stein exponen sus ventajas y desventajas en Introduction to Algorithms. La comparación completa, incluido el formato de fila dispersa comprimida y el umbral de densidad a partir del cual una matriz es la opción más pequeña, está en la guía sobre representación de grafos.

La regla práctica se deduce de la sección 9. Los recorridos como BFS y DFS dedican todo su tiempo de ejecución a recorrer conjuntos de vecinos, así que en un grafo disperso la lista de adyacencia da O(n + m) donde la matriz obligaría a O(n2) solo para escanear filas de ceros. En un grafo denso la matriz gana en espacio y en simplicidad. Una lista de aristas parece primitiva hasta que te encuentras con el algoritmo de Kruskal, que ordena todas las aristas por peso y nunca necesita consultar vecinos.

11. Decidir qué debe ser un vértice

La parte más difícil de aplicar la teoría de grafos no es ningún teorema. Es elegir qué son los vértices, porque esa elección determina todo lo demás y rara vez es única.

Toma una red de carreteras. El modelo obvio hace que las intersecciones sean los vértices y los tramos de carretera las aristas, que es lo que quiere un motor de rutas: un camino en el grafo es una ruta sobre el terreno. Pero las restricciones y los costes de giro viven en las intersecciones, no en las carreteras, y este modelo no tiene dónde ponerlos. La solución estándar invierte la elección: haz que cada tramo de carretera sea un vértice, y une dos de ellos cuando se pueda pasar legalmente de uno al otro. Ahora un giro es una arista y puede llevar un coste.

Esa inversión es una construcción formal, no un apaño. El grafo de líneas L(G) tiene un vértice por cada arista de G, y dos de ellos son adyacentes cuando las aristas correspondientes de G comparten un extremo. Se remonta al artículo de Whitney de 1932 sobre grafos congruentes, y es la razón por la que un problema sobre aristas a menudo puede entregarse a un algoritmo que solo entiende de vértices. Los problemas de emparejamiento, por ejemplo, se convierten en problemas de conjunto independiente sobre el grafo de líneas.

Una lista breve que evita la mayoría de los errores de modelado:

• ¿Pueden dos de tus vértices estar unidos más de una vez? Si es así, necesitas un multigrafo, o necesitas agregar las aristas paralelas en un solo peso.
• ¿Es simétrica la relación? «Es amigo de» suele serlo; «sigue a» y «depende de» no lo son. Si te equivocas en esto, usarás un algoritmo no dirigido en un problema dirigido.
• ¿La relación involucra más de dos cosas a la vez? Una arista une exactamente dos vértices. Un comité de cinco personas, o una reacción química con tres reactivos, es una arista de hipergrafo , y aplastarla en aristas corrientes pierde información.
• ¿Cambia la estructura con el tiempo? Un grafo estándar es una instantánea. Los grafos temporales o dinámicos son modelos aparte, con su propia literatura.

12. Trampas terminológicas entre libros de texto

La teoría de grafos creció en varios campos a la vez, así que el mismo objeto tiene varios nombres y unos cuantos nombres significan cosas distintas para distintos autores. Estos son los que de verdad causan errores:

La costumbre segura es la que sigue todo artículo: enuncia tus convenciones una vez al principio y luego mantenlas. Cuando cites un teorema, cita la definición bajo la que se demostró.

13. Glosario de símbolos

La notación usada en este sitio y en las referencias de abajo.

15. Referencias

Las definiciones, teoremas y atribuciones anteriores proceden de estas fuentes, enumeradas en orden cronológico.

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (publicado en 1741), 128 a 140. El artículo de los puentes de Königsberg y el origen del argumento de los grados.
2. Sylvester, J. J. (1878). "Chemistry and Algebra." Nature 17, 284. La nota que introdujo la palabra «grafo» en su sentido moderno.
3. Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1), 150 a 168. Fuente de la construcción del grafo de líneas.
4. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft. El primer libro dedicado por completo a la teoría de grafos.
5. Havel, V. (1955). "A remark on the existence of finite graphs" (en checo). Časopis pro pěstování matematiky 80, 477 a 480.
6. Erdős, P. y Gallai, T. (1960). "Graphs with prescribed degrees of vertices" (en húngaro). Matematikai Lapok 11, 264 a 274. El criterio exacto para las sucesiones gráficas.
7. Hakimi, S. L. (1962). "On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I." Journal of the Society for Industrial and Applied Mathematics 10(3), 496 a 506.
8. Harary, F. (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley. El clásico que llama a los vértices «puntos» y a las aristas «líneas».
9. Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. New York: Springer.
10. West, D. B. (2001). Introduction to Graph Theory, 2.ª edición. Upper Saddle River: Prentice Hall. Define un grafo mediante un conjunto de vértices, uno de aristas y una relación de extremos.
11. Bondy, J. A. y Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres: Springer. Fuente de la formulación con función de incidencia usada en la sección 4.
12. Bang-Jensen, J. y Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2.ª edición. Londres: Springer. Referencia estándar para arcos y grados dirigidos.
13. Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición. Cambridge, Massachusetts: MIT Press. Fuente de los costes de representación de la sección 10.
14. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer. Fuente de la definición citada en la sección 1.