Grado de un vértice y lema del apretón de manos

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. El grado de un vértice

El grado de un vértice es el número de aristas que inciden en él. En un grafo simple coincide con el número de sus vecinos. Es el número más local que tiene un grafo: puedes leerlo en un solo vértice sin mirar nada más. Sin embargo, una cantidad sorprendente de estructura global la deciden solo los grados, y de eso trata este artículo.

La notación es breve. deg(v) es el grado de v, δ(G) es el grado mínimo sobre todos los vértices y Δ(G) el grado máximo. Un vértice de grado 0 está aislado, un vértice de grado 1 es una hoja o vértice colgante, y un grafo en el que todos los vértices tienen el mismo grado r es r-regular. El vocabulario básico, incluido por qué un lazo suma 2 al grado, se expone en la guía de vértices y aristas; este artículo lo toma como punto de partida y se pregunta qué pueden decirte los grados.

Una pequeña red de amistades recorre todo el artículo. Ocho personas, de A a H, y doce amistades:

E = {AB, AC, AD, BC, BD, CD, AE, DE, AF, EF, FG, AH}       12 aristas

grado: A 6   B 3   C 3   D 4   E 3   F 3   G 1   H 1
δ = 1 (G y H)        Δ = 6 (A)      grado medio = 24 / 8 = 3

2. El lema del apretón de manos

Suma los grados del ejemplo y obtienes 24, exactamente el doble de sus 12 aristas. No es una casualidad de este grafo.

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

La prueba es un doble conteo. Cuenta los pares (vértice, extremo de arista en ese vértice). Contando por vértices se obtiene la suma de los grados. Contando por aristas se obtiene 2 por cada arista, porque cada arista tiene exactamente dos extremos, y eso incluye un lazo, cuyos dos extremos están en el mismo vértice. Ambos conteos describen el mismo conjunto de pares, así que son iguales. La observación se remonta al artículo de Euler de 1736 sobre los puentes de Königsberg, donde aparece en el lenguaje de puentes y regiones de tierra; el nombre «lema del apretón de manos» es moderno y viene de la imagen de una fiesta en la que cada apretón de manos implica dos manos.

La consecuencia más útil del lema es inmediata. La suma de todos los grados es par, así que los grados impares deben ir por parejas:

Todo grafo tiene un número par de vértices de grado impar.

En el ejemplo, los vértices de grado impar son B, C, E, F, G y H: seis, un número par, como se prometía.

3. Calcular grados a partir de un grafo almacenado

Lo barato que resulta leer un grado depende de cómo se almacena el grafo, el compromiso que explica la guía de representación de grafos. Con una lista de adyacencia, el grado de v es la longitud de su lista, disponible en O(1) si la longitud está almacenada. Con una matriz de adyacencia es la suma de la fila v, lo que cuesta O(n). Con una simple lista de aristas tienes que recorrer las m aristas, así que lo habitual es calcular todos los grados en una sola pasada y guardar el resultado. El programa de abajo hace eso, comprueba el lema del apretón de manos y calcula también los dos promedios en los que se basa la sección 9.

from collections import Counter

edges = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'AE', 'DE', 'AF', 'EF', 'FG', 'AH']
adj = {v: set() for v in 'ABCDEFGH'}
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)

deg = {v: len(adj[v]) for v in adj}
print(deg)
# {'A': 6, 'B': 3, 'C': 3, 'D': 4, 'E': 3, 'F': 3, 'G': 1, 'H': 1}

print(sum(deg.values()), 2 * len(edges))     # el lema del apretón de manos
# 24 24
print(sorted(v for v in deg if deg[v] % 2))   # siempre hay un número par de ellos
# ['B', 'C', 'E', 'F', 'G', 'H']

# La paradoja de la amistad: grado medio frente al grado medio de un amigo.
mean_degree = sum(deg.values()) / len(deg)
mean_friend = sum(deg[v] ** 2 for v in deg) / sum(deg.values())
print(mean_degree, mean_friend)
# 3.0 3.75

# ¿Cuántas personas tienen menos amigos que la media de sus amigos?
fewer = [v for v in adj if deg[v] < sum(deg[w] for w in adj[v]) / deg[v]]
print(sorted(fewer))
# ['B', 'C', 'E', 'F', 'G', 'H']
print(Counter(deg.values()).most_common(1))  # siempre se repite algún grado
# [(3, 4)]

Dos líneas de la salida merecen atención ya. La comprobación del apretón de manos imprime 24 24. Y la última línea informa de que el grado 3 aparece cuatro veces. Siempre hay algún grado que se repite, por una razón que explica la sección 4.

4. Acertijos que el lema resuelve al instante

El lema del apretón de manos convierte varias preguntas que parecen requerir una búsqueda en una sola línea de aritmética.

• ¿Pueden siete personas dar la mano cada una a exactamente otras tres? No. Haría falta una suma de grados de 7 × 3 = 21, que es impar, pero toda suma de grados es el doble de un número entero de apretones de manos.
• ¿Existe un grafo 3-regular con 9 vértices? No, por la misma razón. Un grafo r-regular con n vértices tiene nr / 2 aristas, así que cuando r es impar, n debe ser par.
• ¿Cuántas aristas tiene un grafo con 10 vértices y grado medio 3? Exactamente 15, porque el grado medio es 2m / n.
• ¿Puede un paseo usar cada arista exactamente una vez y empezar y terminar en lugares distintos, con un solo vértice de grado impar? La pregunta nunca llega a plantearse: un grafo no puede tener exactamente un vértice impar. La guía de caminos eulerianos explica que el criterio de Euler pide cero o dos, y el lema descarta cualquier cantidad impar.

Otro clásico usa en cambio el principio del palomar:

En todo grafo simple con al menos dos vértices, hay dos vértices con el mismo grado.

Con n vértices, los grados posibles son 0, 1, …, n − 1, es decir, n valores para n vértices, así que si todos fueran distintos se usaría cada valor una vez. Pero 0 y n − 1 no pueden darse a la vez: un vértice de grado n − 1 es adyacente a todos, así que nadie tiene grado 0. Eso deja como mucho n − 1 valores utilizables para n vértices, y dos deben compartir uno. Dicho de forma cotidiana: en cualquier fiesta hay dos personas con el mismo número de amigos allí. El enunciado necesita que el grafo sea simple; con aristas paralelas falla. Se comprobó por fuerza bruta en todos los grafos simples de hasta siete vértices.

5. Sucesiones de grados: ¿qué listas pueden ser grafos?

Ordena los grados de mayor a menor y obtienes la sucesión de grados, (6, 4, 3, 3, 3, 3, 1, 1) en el ejemplo. Una sucesión que algún grafo simple tiene realmente se llama gráfica. Una suma par es necesaria, por el lema del apretón de manos, pero está lejos de ser suficiente: (4, 4, 4, 1, 1) tiene suma par y ningún grafo. Tres vértices de grado 4 entre cinco serían adyacentes cada uno a todos los demás, lo que daría a los dos últimos vértices grado al menos 3.

Dos pruebas clásicas deciden la cuestión con exactitud. La guía de vértices y aristas las recorre a mano; aquí están como código. El método de Havel–Hakimi (Havel, 1955; Hakimi, 1962) une repetidamente el vértice de mayor grado restante con los siguientes de la fila, y o bien construye un grafo o se atasca. El teorema de Erdős–Gallai (1960) es una prueba de forma cerrada: una sucesión no creciente con suma par es gráfica exactamente cuando, para cada k, los k mayores grados suman como mucho k(k − 1) más la suma de min(di, k) sobre el resto.

import heapq

def havel_hakimi(seq):
    """Devuelve las aristas de un grafo simple con estos grados, o None si no existe ninguno."""
    if sum(seq) % 2:
        return None                           # un total impar contradice el lema del apretón de manos
    heap = [(-d, i) for i, d in enumerate(seq) if d > 0]
    heapq.heapify(heap)
    edges = []
    while heap:
        d, v = heapq.heappop(heap)
        d = -d
        if d > len(heap):
            return None                       # no quedan suficientes vértices a los que unirlo
        taken = [heapq.heappop(heap) for _ in range(d)]
        for dw, w in taken:                   # une v con los d vértices de mayor grado
            edges.append((v, w))
            if dw + 1 < 0:
                heapq.heappush(heap, (dw + 1, w))
    return edges

def erdos_gallai(seq):
    """True exactamente cuando la sucesión es gráfica (Erdős y Gallai, 1960)."""
    d = sorted(seq, reverse=True)
    if sum(d) % 2:
        return False
    for k in range(1, len(d) + 1):
        if sum(d[:k]) > k * (k - 1) + sum(min(x, k) for x in d[k:]):
            return False
    return True

print(len(havel_hakimi([6, 4, 3, 3, 3, 3, 1, 1])))
# 12
print(havel_hakimi([4, 4, 4, 1, 1]), erdos_gallai([4, 4, 4, 1, 1]))
# None False
print(havel_hakimi([3, 3, 3, 3, 3]), erdos_gallai([3, 3, 3, 3, 3]))
# None False

Para (4, 4, 4, 1, 1) la desigualdad de Erdős–Gallai falla en k = 3: los tres mayores grados suman 12, pero la cota es 3 × 2 + 1 + 1 = 8. Ambas funciones se comprobaron por fuerza bruta en cada una de las 2353 sucesiones no crecientes de longitud n ≤ 7 con términos no mayores que n − 1, y también se comprobó que la función de Havel–Hakimi devuelve un auténtico grafo simple con exactamente los grados pedidos. Una sucesión gráfica suele tener muchas realizaciones distintas, así que una sucesión de grados describe una familia de grafos, no un solo grafo.

6. Qué garantiza un grado mínimo grande

Obligar a que cada vértice tenga muchos vecinos obliga a que haya estructura. Los argumentos detrás de los tres primeros hechos son variaciones de una misma idea: camina tan lejos como puedas y mira dónde están los vecinos del último vértice.

• δ ≥ 2 obliga a que haya un ciclo. Toma un camino de longitud máxima. Su último vértice tiene al menos dos vecinos, y todos están en el camino, porque si no el camino podría alargarse. Uno de ellos no es su predecesor, y esa arista cierra un ciclo.
• δ ≥ k obliga a que haya un camino con al menos k aristas. El mismo camino de longitud máxima debe contener a los δ vecinos de su último vértice, así que tiene al menos δ + 1 vértices.
• δ ≥ (n − 1) / 2 obliga a que el grafo sea conexo. Dos vértices en componentes distintas necesitarían cada uno al menos (n − 1) / 2 vecinos dentro de su propia componente, y entre las dos componentes tendrían más de n vértices.

El resultado más famoso de este tipo trata de los ciclos hamiltonianos, ciclos que pasan una vez por cada vértice. Decidir si existe uno es NP-completo en general, pero un grado mínimo grande lo resuelve.

Teorema de Dirac (1952). Todo grafo simple con n ≥ 3 vértices y grado mínimo al menos n / 2 tiene un ciclo hamiltoniano.

Ore lo reforzó en 1960: basta con que cada dos vértices no adyacentes tengan grados que sumen al menos n. El umbral n / 2 no se puede rebajar. El grafo bipartito completo K2,3 tiene cinco vértices y grado mínimo 2, justo por debajo de 5 / 2, y no tiene ciclo hamiltoniano, porque un ciclo por los cinco vértices tendría que alternar entre los dos lados, y los lados tienen tamaños distintos.

La red del ejemplo tiene δ = 1, muy por debajo de 8 / 2, y no tiene ciclo hamiltoniano: un ciclo nunca puede pasar por una hoja como G, que solo tiene una arista. La condición de Dirac es suficiente, no necesaria, así que no cumplirla no demuestra nada por sí solo; aquí la verdadera razón son las hojas.

7. Qué acota el grado máximo

El grado máximo controla la coloración. Colorea los vértices de uno en uno en cualquier orden, dando a cada uno el menor color que no usen sus vecinos ya coloreados. Un vértice tiene como mucho Δ vecinos, así que como mucho Δ colores quedan bloqueados y uno de los primeros Δ + 1 siempre está libre.

Todo grafo puede colorearse propiamente con a lo sumo Δ + 1 colores, y el algoritmo voraz lo consigue con cualquier orden de vértices.

Brooks demostró en 1941 que basta un color menos, con exactamente dos tipos de excepción: un grafo conexo necesita Δ + 1 colores solo si es un grafo completo o un ciclo impar. Un ciclo impar tiene Δ = 2 y necesita 3 colores, y Kn tiene Δ = n − 1 y necesita n. Para la coloración de aristas la respuesta es aún más ajustada: Vizing demostró en 1964 que las aristas de todo grafo simple pueden colorearse con Δ o Δ + 1 colores.

En el ejemplo Δ = 6, así que la coloración voraz tiene garantizado usar como mucho 7 colores y el teorema de Brooks rebaja la cota a 6. La verdad es 4, porque el ejemplo contiene el grafo completo sobre A, B, C y D, que necesita 4, y 4 bastan. El grado máximo es una cota burda cuando un vértice está mucho más ocupado que el resto. La heurística de Welsh y Powell de 1967, que colorea los vértices en orden de grado decreciente, es una respuesta; la siguiente sección da otra más afinada.

8. Degeneración y k-núcleos

El nodo central A infla Δ sin hacer que el grafo sea difícil de colorear. Una medida mejor mira lo disperso que es el grafo en todas partes, no su único vértice más ocupado. Borra repetidamente un vértice de menor grado restante. El mayor grado con el que llegaste a borrar un vértice es la degeneración del grafo. De forma equivalente, el k-núcleo es el mayor subgrafo en el que cada vértice tiene al menos k vecinos dentro de él, una noción introducida por Seidman en 1983, y la degeneración es el mayor k con un k-núcleo no vacío.

El pelado se ejecuta en tiempo lineal si los vértices se guardan en cubetas según su grado actual. Matula y Beck dieron en 1983 una ordenación «smallest-last» de este tipo en tiempo lineal, y el algoritmo de cubetas de Batagelj y Zaveršnik calcula el número de núcleo de cada vértice en O(m):

def core_numbers(adj):
    """Número de núcleo de cada vértice: quita repetidamente un vértice de menor grado restante."""
    deg = {v: len(adj[v]) for v in adj}
    buckets = [set() for _ in range(max(deg.values(), default=0) + 1)]
    for v, d in deg.items():
        buckets[d].add(v)
    core, k = {}, 0
    for _ in range(len(adj)):
        d = next(i for i, b in enumerate(buckets) if b)   # la cubeta no vacía más pequeña
        k = max(k, d)                         # el número de núcleo nunca vuelve a bajar
        v = buckets[d].pop()
        core[v] = k
        for w in adj[v]:
            if w not in core:                 # w pierde un vecino: bájalo una cubeta
                buckets[deg[w]].remove(w)
                deg[w] -= 1
                buckets[deg[w]].add(w)
    return core

edges = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'AE', 'DE', 'AF', 'EF', 'FG', 'AH']
adj = {v: set() for v in 'ABCDEFGH'}
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)

core = core_numbers(adj)
print(dict(sorted(core.items())))
# {'A': 3, 'B': 3, 'C': 3, 'D': 3, 'E': 2, 'F': 2, 'G': 1, 'H': 1}
print(max(core.values()))                     # la degeneración del grafo
# 3

La degeneración del ejemplo es 3, muy por debajo de su Δ de 6. Eso importa para la coloración, porque colorear de forma voraz en el orden inverso al del pelado deja a cada vértice como mucho degeneración vecinos ya coloreados, así que usa como mucho degeneración + 1 colores: 4 aquí, que es óptimo. La degeneración también acota el trabajo de enumerar cliques, donde procesar los vértices en orden de degeneración es la aceleración estándar, y los k-núcleos son una primera mirada habitual a las redes grandes: los núcleos internos son el centro densamente tejido; las capas externas, la periferia.

9. La paradoja de la amistad

En 1991 el sociólogo Scott Feld señaló algo que suena a insulto: de media, tus amigos tienen más amigos que tú. No es un hecho sobre las personas sino sobre los grados, y el programa de la sección 3 ya lo calculó para el ejemplo. El grado medio es 3, pero el grado medio de un amigo es 3,75.

La razón es un sesgo de muestreo. Cuando promedias sobre personas, cada una cuenta una vez. Cuando promedias sobre amigos, recorres cada amistad y miras a la persona del otro extremo, así que una persona con d amigos se cuenta d veces. Las personas populares están sobrerrepresentadas en las listas de amigos de los demás precisamente porque son populares. En fórmulas, el grado medio es ∑ d / n, mientras que el grado medio de un amigo es ∑ d² / ∑ d, y la desigualdad de Cauchy–Schwarz muestra que el segundo nunca es menor que el primero, con igualdad solo cuando todos los vértices tienen el mismo grado.

La figura muestra una versión relacionada, persona a persona: seis de las ocho personas tienen menos amigos que la media de sus propios amigos, y solo A y D salen ganando. El caso extremo es una estrella: en una estrella con nueve hojas el grado medio es 1,8, pero el grado medio de un amigo es 5, y cada hoja tiene menos amigos que su único amigo. Pero cuidado con la versión persona a persona. La desigualdad de arriba trata de medias y no garantiza nada sobre cuántos individuos quedan por debajo. Aun así, en las redes reales el efecto es fuerte: en el estudio de 2011 de Ugander y sus colegas sobre el grafo de Facebook, el 92,7 % de los usuarios tenía menos amigos que la media de amigos de sus amigos.

La paradoja tiene usos prácticos. Un amigo de una persona elegida al azar es una forma mejor que el azar de encontrar a alguien bien conectado; por eso se ha propuesto muestrear amigos de personas al azar para detectar pronto una epidemia, y por eso vacunar a conocidos puede proteger a más personas que vacunar al azar.

10. Distribuciones de grados en redes reales

Para una red grande la lista de grados es demasiado larga para leerla, así que se resume con la distribución de grados: la fracción de vértices con grado k, para cada k. Su forma dice mucho sobre cómo se formó la red.

• Los grafos aleatorios del modelo de Erdős–Rényi, donde cada par se une de forma independiente, tienen grados muy concentrados en torno a la media, sin casi ningún vértice lejos de ella.
• Muchas redes reales tienen un aspecto muy distinto: la mayoría de los vértices tienen grado pequeño y unos pocos nodos centrales tienen un grado enorme. Barabási y Albert propusieron en 1999 que el enlace preferencial, por el que los vértices nuevos se enlazan preferentemente con los ya populares, produce una distribución de ley de potencias, y de ahí se difundió el término «red libre de escala».
• Cuán comunes son las verdaderas leyes de potencias es objeto de debate. Broido y Clauset analizaron 927 conjuntos de datos de redes en 2019 y hallaron pruebas sólidas de estructura libre de escala solo en una pequeña minoría de ellos. Las distribuciones de grados de cola pesada son comunes; una ley de potencias limpia no lo es.

Dos medidas basadas en el grado aparecen constantemente en el análisis de redes. La centralidad de grado ordena los vértices simplemente por su grado, la respuesta más barata a «quién es importante». Y la asortatividad, introducida por Newman en 2002, mide si los vértices de grado alto tienden a enlazarse con otros vértices de grado alto. Newman halló que las redes sociales son asortativas y que muchas redes tecnológicas y biológicas son disasortativas, con nodos centrales enlazados sobre todo a vértices de grado bajo. La red del ejemplo también es disasortativa: su nodo central A es el único amigo de las dos hojas.

11. Grafos dirigidos: grado de entrada y grado de salida

En un grafo dirigido cada arco tiene una cola y una cabeza, así que un vértice tiene un grado de entrada, el número de arcos que llegan, y un grado de salida, el número de los que salen. El lema del apretón de manos se divide en consecuencia: cada arco aporta uno a algún grado de salida y uno a algún grado de entrada, así que

∑ in-deg(v)  =  ∑ out-deg(v)  =  m          el número de arcos

Fíjate en que falta el factor 2, un desliz habitual al pasar de grafos no dirigidos a grafos dirigidos. Los grados dirigidos tienen sus propios significados. Un vértice de grado de entrada 0 es una fuente y uno de grado de salida 0, un sumidero; la ordenación topológica con el algoritmo de Kahn parte de las fuentes y avanza reduciendo grados de entrada. Un digrafo conexo tiene un circuito que usa cada arco exactamente una vez exactamente cuando cada vértice tiene el grado de entrada igual al de salida. Y en un grafo de la web, el grado de entrada es una primera medida de popularidad, la cantidad que PageRank refina ponderando cada enlace entrante por la importancia de su origen.

12. Errores comunes

13. Glosario

15. Referencias

Las definiciones, teoremas y atribuciones anteriores proceden de estas fuentes, ordenadas cronológicamente.

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (publicado en 1741), 128 a 140. La observación en la que se basa el lema del apretón de manos, enunciada para puentes y regiones de tierra.
2. Brooks, R. L. (1941). "On Colouring the Nodes of a Network." Proceedings of the Cambridge Philosophical Society 37(2), 194 a 197.
3. Dirac, G. A. (1952). "Some Theorems on Abstract Graphs." Proceedings of the London Mathematical Society s3-2(1), 69 a 81.
4. Havel, V. (1955). "Poznámka o existenci konečných grafů." Časopis pro pěstování matematiky 80(4), 477 a 480. Una observación sobre la existencia de grafos finitos.
5. Erdős, P. y Gallai, T. (1960). "Gráfok előírt fokszámú pontokkal." Matematikai Lapok 11, 264 a 274. Grafos con grados de vértices prescritos.
6. Ore, O. (1960). "Note on Hamilton Circuits." American Mathematical Monthly 67(1), 55.
7. Hakimi, S. L. (1962). "On the 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. Vizing, V. G. (1964). "On an Estimate of the Chromatic Class of a p-Graph." Diskretnyi Analiz 3, 25 a 30.
9. Welsh, D. J. A. y Powell, M. B. (1967). "An Upper Bound for the Chromatic Number of a Graph and Its Application to Timetabling Problems." The Computer Journal 10(1), 85 a 86.
10. Matula, D. W. y Beck, L. L. (1983). "Smallest-Last Ordering and Clustering and Graph Coloring Algorithms." Journal of the ACM 30(3), 417 a 427.
11. Seidman, S. B. (1983). "Network Structure and Minimum Degree." Social Networks 5(3), 269 a 287. El k-núcleo.
12. Feld, S. L. (1991). "Why Your Friends Have More Friends Than You Do." American Journal of Sociology 96(6), 1464 a 1477.
13. Barabási, A.-L. y Albert, R. (1999). "Emergence of Scaling in Random Networks." Science 286(5439), 509 a 512.
14. Newman, M. E. J. (2002). "Assortative Mixing in Networks." Physical Review Letters 89(20), 208701.
15. Ugander, J., Karrer, B., Backstrom, L. y Marlow, C. (2011). "The Anatomy of the Facebook Social Graph." arXiv:1111.4503.
16. Batagelj, V. y Zaveršnik, M. (2011). "Fast Algorithms for Determining (Generalized) Core Groups in Social Networks." Advances in Data Analysis and Classification 5(2), 129 a 145. Circuló por primera vez en 2003 como "An O(m) Algorithm for Cores Decomposition of Networks."
17. Broido, A. D. y Clauset, A. (2019). "Scale-Free Networks Are Rare." Nature Communications 10, 1017.
18. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer.