Grado (teoría de grafos)

En Teoría de grafos, el grado o valencia de un vértice es el número de aristas incidentes al vértice. El grado de un vértice x es denotado por grado(x), g(x) o gr(x) (aunque también se usa δ(x), y del inglés d(x) y deg(x)). El grado máximo de un grafo G es denotado por Δ(G) y el grado mínimo de un grafo G es denotado por δ(G).

Un grafo con vértices etiquetados según su grado. El *vértice aislado* se etiqueta con 0, pues no es adyacente a ningún nodo.

Un vértice con grado 0 es un vértice aislado. Un grafo formado exclusivamente por vértices aislados es un grafo vacío. Un grafo donde todos los vértices tienen el mismo grado es un grafo regular, y un grafo no dirigido de n vértices en que todos los vértices tiene grado n-1 es un grafo completo.

Vecindad de un vértice

Artículo principal: Vecindad (teoría de grafos)

Otra forma de definir el grado de un vértice es a través de su vecindad. La vecindad de un vértice x , denotado como $N(x)\,$ está dado por todos los vértices adyacentes a x.

N(x)=\{y\in V_{G}|\{x,y\}\in E_{G}\}

de modo que el grado del vértice x es el número de vecinos que tiene: $g(x)=|N(x)|\,$ .

Lema del apretón de manos

El Lema del apretón de manos determina que la suma de los grados de un grafo simple (es decir, sin bucles) y no dirigido equivale al doble de su número de aristas:

Lema del apretón de manos. Dado un grafo $G(V,E)\,$ :

$\sum _{v\in V}g(v)=2|E|\,$

Euler (1736)^[1]

Su demostración es una prueba del doble conteo: como cada arista tiene dos vértices extremos, es contada dos veces.

Algunas implicaciones del Lema del apretón de manos son:

En un grafo simple no dirigido siempre hay un número par de vértices de grado impar.
En un grafo simple no dirigido no puede existir un grafo r-regular de s vértices si r y s son impares.
En un grafo simple no dirigido el número de aristas de un grafo k-regular es ${\frac {nk}{2}}$ , y por ende, el número de aristas de un grafo completo de n vértices es ${\frac {n(n-1)}{2}}.$

Grado modal medio

Dado un grafo simple no dirigido $G(V,E)$ , el grado promedio^[2] o grado modal medio (que denotaremos ${\bar {g}}$ ) es un estadístico definido como el grado promedio de los nodos:^[3]

{\bar {g}}={\frac {\sum _{v\in V}g(v)}{|V|}}={\frac {2|E|}{|V|}}\,

Varianza de los grados

Dado un grafo simple no dirigido $G(V,E)$ , la varianza de los grados, que denotaremos $S_{D}^{2}$ , mide la variabilidad de los grados de los nodos. Formalmente se define como:^[3]

S_{D}^{2}={\frac {\sum _{v\in V}(g(v)-{\bar {g}})^{2}}{|V|}}\,

Si el grafo es regular, es decir, los grados de todos sus vértices son iguales, entonces $S_{D}^{2}=0$ .^[3]

Grafos dirigidos

Un grafo dirigido con vértices

i

etiquetados como

(g^{-}(i),g^{+}(i))

.

En el caso de los grafos dirigidos o dígrafos, se suele distinguir entre grado de entrada $g^{-}(x)\,$ , como el número de aristas que tiene al vértice x como vértice final, y grado de salida $g^{+}(x)\,$ , como el número de aristas que tiene al vértice x como vértice inicial, de forma que $g(x)=g^{+}(x)+g^{-}(x)\,$ .^[3]

El Lema del apretón de manos también es cierto en los grafos dirigidos. Para ello hay que distinguir para cada nodo entre grados de entrada y de salida. Por lo tanto, el Lema se expresa del siguiente modo:^[3]

\sum _{v\in V}g^{+}(v)=\sum _{v\in V}g^{-}(v)=|E|\,

Por lo tanto, en este caso el grado de entrada promedio ${\bar {g}}^{-}$ y el grado de salida promedio ${\bar {g}}^{+}$ coinciden, y se definen como:^[3]

{\bar {g}}^{-}={\frac {\sum _{v\in V}g^{-}(v)}{|V|}}={\bar {g}}^{+}={\frac {\sum _{v\in V}g^{+}(v)}{|V|}}={\frac {|E|}{|V|}}\,

Por otra parte, la varianza de los grados de entrada ( $S_{D^{-}}^{2}$ ) y de salida ( $S_{D^{+}}^{2}$ ) no necesariamente van a coincidir, quedando como sigue:

S_{D^{-}}^{2}={\frac {\sum _{v\in V}(g^{-}(v)-{\bar {g}}^{-})^{2}}{|V|}}\,

S_{D^{+}}^{2}={\frac {\sum _{v\in V}(g^{+}(v)-{\bar {g}}^{+})^{2}}{|V|}}\,

Ambas varianzas miden la variabilidad de grados entre los actores de la red.^[3]

Secuencia de grados

Artículo principal: Secuencia de grados

Una secuencia de grados o lista de grados de un grafo no dirigido es una secuencia de números, los cuales son grados de los vértices de algún grafo. Para el grafo de la primera imagen su secuencia de enteros es (3, 3, 3, 2, 2, 1, 0). La lista de grados es un invariante (topológica) de un grafo, aunque dos grafos con igual lista de grados no son necesariamente isomorfos.

Un problema interesante es determinar si una secuencia de enteros no negativos cualquiera es o no gráfica, es decir, es una secuencia de grados de un grafo (simple). Erdős y Gallai^[4] (1960) resuelven el problema con su teorema de existencia, mientras que Havel^[5] (1955) y Hakimi^[6] (1962) nos entregan un teorema de construcción que justifica el Algoritmo Havel-Hakimi para construir un grafo a partir de una secuencia de grados.

Teorema de Erdős-Callai. La secuencia de enteros $d_{i}\,$ con $i=1,...,n\,$ es una secuencia de grados de un grafo simple, si y sólo si:

La suma de los enteros de la secuencia es par, y

$\sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)$ para $k\leq n-1$

Teorema de Havel-Hakimi. Una secuencia de enteros $d_{1}\geq d_{2}\geq ...\geq d_{v}\geq 0$ es gráfica sí, y sólo sí también lo es la lista: $d_{2}-1,d_{3}-1,...,d_{d_{1}+1}-1,d_{d_{1}+2},...,d_{v}$ , que resulta de eliminar el primer elemento y restar una unidad a los siguientes $d_{1}$ valores de la lista.

Propiedades

Un grafo simple conexo contiene un camino Euleriano si, y sólo si el grafo contiene 0 o 2 vértices de grado impar. Si el grafo no tiene vértices de grado impar entonces contiene un ciclo Euleriano.
Por el Teorema de Brooks el número cromático de un grafo G que no es un grafo completo ni un ciclo de longitud impar es a lo sumo: $\chi (G)\leq \Delta$ , y por el Teorema de Vizing todo grafo tiene índice cromático a lo más $\Delta +1$
En un árbol, el vértice de grado 1 se llama hoja y forma parte del grupo de los vértices terminales.

Aplicaciones

Análisis de redes sociales

Artículo principal: Centralidad de grado

En análisis de redes sociales, el grado se considera la primera y más sencilla de las medidas de centralidad. En particular, el grado de salida puede considerarse en muchos casos como una medida de «expansividad», y el grado de salida, como una medida de «receptividad» o «popularidad». El hecho que los grados de entrada y salida de los nodos de una red social sean parecidos, puede considerarse a su vez una tendencia hacia la «mutualidad». Además, dependiendo de los grados de un nodo o actor $v$ , este se puede clasificar en:^[3]

Aislado, si $g^{-}(v)=g^{+}(v)=0$ ;
Transmisor, si $g^{-}(v)=0$ y $g^{+}(v)>0$ ;
Receptor, si $g^{-}(v)>0$ y $g^{+}(v)=0$ ;
Portador u ordinario, si $g^{-}(v)>0$ y $g^{+}(v)>0$ .

El grado modal medio es un estadístico que entrega información sobre una red social. La varianza de grados se considera además una medida de centralización de la red.^[2]

Véase también

Distribución de grado

Referencias

↑ Euler, L. (1736). «Solutio problematis ad geometriam situs pertinentis». Commentarii Academiae Scientiarum Imperialis Petropolitanae 8. 128-140.
↑ ^a ^b Wasserman y Faust, 2013, «Centralidad y prestigio», pp. 191-240.
↑ ^a ^b ^c ^d ^e ^f ^g ^h Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
↑ Erdős, P. ; Gallai, T. (1960). «Graphs with prescribed degree of vertices». Mat. Lapok 11. 264–274..
↑ Havel, V. (1955). «A remark on the existence of finite graphs.». Časopis Pest. Mat. 80. 477–480..
↑ Hakimi, S.L. (1962). «On the realizability of a set of integers as degrees of the vertices of a simple graph». J. SIAM Appl. Math 10. 496–506..

Bibliografía

Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053.

Datos: Q383444

[1] Euler, L. (1736). «Solutio problematis ad geometriam situs pertinentis». Commentarii Academiae Scientiarum Imperialis Petropolitanae 8. 128-140.

[WF13.c5-2] Wasserman y Faust, 2013, «Centralidad y prestigio», pp. 191-240.

[WF13.c4-3] ↑ ^a ^b ^c ^d ^e ^f ^g ^h Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.

[4] Erdős, P. ; Gallai, T. (1960). «Graphs with prescribed degree of vertices». Mat. Lapok 11. 264–274..

[5] Havel, V. (1955). «A remark on the existence of finite graphs.». Časopis Pest. Mat. 80. 477–480..

[6] Hakimi, S.L. (1962). «On the realizability of a set of integers as degrees of the vertices of a simple graph». J. SIAM Appl. Math 10. 496–506..

[1]

[2]

[3]

[4]

[5]

[6]