Grado de un vértice (teoría de grafos)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de junio de 2021; la verificación requiere 1 edición .

El grado ( valencia ) de un vértice de un gráfico es el número de aristas del gráfico que inciden en el vértice . Al calcular el grado, el bucle de borde se tiene en cuenta dos veces. [una] $GRAMO$ $X$

El grado de un vértice generalmente se denota como o . Los grados máximo y mínimo de los vértices de un gráfico G se denotan por Δ( G ) y δ( G ), respectivamente. En la fig. 1, el grado máximo es 5, el mínimo es 0. En un grafo regular , los grados de todos los vértices son iguales, entonces en este caso podemos hablar del grado del grafo . $d(x)$ $\grado(v)$

El lema del apretón de manos

Por la fórmula de la suma de potencias de un gráfico , $G=(V,E)$

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

es decir, la suma de los grados de los vértices de cualquier gráfico es igual al doble del número de sus aristas. Además, de la fórmula se deduce que en cualquier gráfico el número de vértices de grado impar es par. Esta declaración (y la fórmula en sí) se conoce como el lema del apretón de manos . El nombre proviene de un conocido problema matemático: es necesario probar que en cualquier grupo el número de personas que estrecharon la mano de un número impar de personas es par.

Secuencia de grados de vértices

La secuencia de grados de vértices de un gráfico no dirigido es una secuencia no creciente . [2] Para el gráfico que se muestra en la fig. 1, tiene la forma (5, 3, 3, 2, 2, 1, 0). La secuencia de grados de los vértices es la gráfica invariante , por lo que es lo mismo para las gráficas isomorfas . Sin embargo, la secuencia de grados de vértice no es una característica única de un gráfico: en algunos casos, los gráficos no isomorfos también tienen la misma secuencia.

El problema de la secuencia de grados consiste en encontrar algunos o todos los gráficos con una secuencia no creciente de números naturales dada (los grados cero se pueden ignorar en este caso, ya que su número se cambia agregando o eliminando vértices aislados). Una secuencia que es una secuencia de grados de un gráfico se llama secuencia gráfica . De la fórmula para la suma de grados se deduce que cualquier secuencia con una suma impar (como 3, 3, 1, por ejemplo) no puede ser una secuencia de grados de un gráfico. Lo contrario también es cierto: si una secuencia tiene una suma par, es una secuencia de potencias de un multigrafo . La construcción de dicho gráfico se lleva a cabo de una manera bastante simple: es necesario combinar los vértices de grados impares en pares , se deben agregar bucles a los vértices restantes sin llenar.

Es más difícil implementar un gráfico simple con una secuencia dada. El teorema de Erdős-Gallay establece que una secuencia no creciente d i (para i = 1,…, n ) puede ser una secuencia gráfica simple solo si su suma es par y la desigualdad

\sum _{{i=1}}^{{k}}d_{i}\leq k(k-1)+\sum _{{i=k+1}}^{n}\min(d_{ i},k)\quad\k\in\{1,\dots,n-1\}\,.

Por ejemplo, la secuencia (3, 3, 3, 1) no puede ser una secuencia gráfica simple; satisface la desigualdad de Erdős-Gallai solo para k igual a 1, pero no para k igual a 2 o 3.

Según el criterio de Havel-Hakimi , si una secuencia no creciente ( d 1 , d 2 , …, d n ) es una secuencia de grados de un gráfico simple, entonces ( d 2 − 1, d 3 − 1, …, d d 1 +1 − 1, d d 1 +2 , d d 1 +3 , …, d n ) alguna secuencia de grados de un gráfico simple. Este hecho nos permite construir un algoritmo polinomial para encontrar un gráfico simple con una secuencia realizable dada.

Comparemos la secuencia inicial de números de los vértices del gráfico sin bordes con los grados requeridos. Esta transformación de secuencia define al menos un vértice de gráfico, todos los bordes incidentes en él y un conjunto de vértices con nuevos complementos de grado requeridos. Ordenando los vértices restantes por complementos de grado no crecientes, obtenemos una secuencia no creciente de grados de un grafo simple. Repitiendo la transformación y ordenando no más de n-1 veces, obtenemos el gráfico completo.

El problema de encontrar o estimar el número de grafos en una secuencia dada pertenece al campo de la enumeración de grafos .

Valores privados

Un vértice de grado 0 se llama aislado .
Un vértice de grado 1 se llama terminal ( ing. end vertex ), colgante ( ing. colgante vertex ) o hoja gráfica ( ing. leaf vertex ). Una arista que incide en dicho vértice se denomina colgante ( inglés terminal (pendant) edge, end-edge ). En la fig. 3, el borde colgante es {3,5}. Se utiliza una terminología similar en el estudio de los árboles en general y como estructuras de datos .
Un vértice de grado n-1 en una gráfica de orden n se llama vértice dominante .

Propiedades generales

Si todos los vértices de un gráfico tienen el mismo grado k , el gráfico se llama k -regular o gráfico regular de grado k . En este caso, el gráfico en sí tiene grado k .
Existe un camino de Euler en un grafo conexo no dirigido si y solo si el grafo tiene 0 o 2 vértices de grado impar. Si el gráfico contiene 0 vértices de grado impar, el camino de Euler es un ciclo.
El dígrafo es un pseudobosque.[ término desconocido ] solo si el grado de salida de cada vértice es como máximo 1. Un gráfico funcional es un caso especial de un pseudobosque en el que los grados de salida de todos los vértices son iguales a 1.
Según el teorema de Brooks, el número cromático de cualquier grafo, salvo un clique o un ciclo impar, no supera el grado máximo de sus vértices (Δ). Según el teorema de Vizing, el índice cromático de cualquier gráfico no supera Δ + 1.
Un gráfico k -degenerado es un gráfico en el que cada subgráfico tiene un vértice de grado como máximo k .

Véase también

Grado de entrada y salida de vértices de grafos dirigidos
Distribución de grados

Notas

↑ Distel, página 5
↑ Distel, página 278

Fuentes

Distel, Reinhard (2005), Graph Theory (3.ª ed.), Berlín, Nueva York: Springer-Verlag, ISBN 978-3-540-26183-4 , < http://diestel-graph-theory.com/index. html > .
Erdős, P. & Gallai, T. (1960), Gráfok előírt fokszámú pontokkal , Matematikai Lapok T. 11: 264-274 , < http://www.renyi.hu/~p_erdos/1961-05.pdf > .
Hakimi, S. L. (1962), Sobre la realizabilidad de un conjunto de números enteros como grados de los vértices de un grafo lineal. I, Revista de la Sociedad de Matemáticas Industriales y Aplicadas , volumen 10: 496–506 .
Sirksma, Hirard y Hoohefen, Khan (1991), Siete criterios para que las secuencias enteras sean gráficas , Journal of Graph Theory vol.15 (2): 223–231 , DOI 10.1002/jgt.3190150209 .