Grado (teoría de grafos)

En teoría de grafos , el grado (o valencia ) de un vértice de un grafo es el número de aristas incidentes al vértice; en un multigrafo , un bucle contribuye con 2 al grado de un vértice, por los dos extremos de la arista. ^{[ 1 ]} El grado de un vértice${\displaystyle v}$se denota${\displaystyle \deg(v)}$o${\displaystyle \deg v}$El grado máximo de un grafo${\displaystyle G}$se denota por${\displaystyle \Delta (G)}$y es el máximo de${\displaystyle G}$grados de los vértices de 's'. El grado mínimo de un grafo se denota por${\displaystyle \delta (G)}$y es el mínimo de${\displaystyle G}$grados de los vértices 's'. En el multigrafo que se muestra a la derecha, el grado máximo es 5 y el grado mínimo es 0.

En un grafo regular , cada vértice tiene el mismo grado, por lo que podemos hablar del grado del grafo. Un grafo completo (denotado${\displaystyle K_{n}}$, dónde${\displaystyle n}$es el número de vértices en el grafo) es un tipo especial de grafo regular donde todos los vértices tienen el grado máximo posible,${\displaystyle n-1}$.

En un grafo con signos , el número de aristas positivas conectadas a un vértice se denomina grado positivo y el número de aristas negativas conectadas se denomina grado negativo . ^{[ 2 ]}

La fórmula de suma de grados establece que, dado un gráfico${\displaystyle G=(V,E)}$,

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

La fórmula implica que en cualquier grafo no dirigido, el número de vértices con grado impar es par. Esta afirmación (así como la fórmula de la suma de grados) se conoce como el lema del apretón de manos . Este último nombre proviene de un problema matemático popular, que consiste en demostrar que en cualquier grupo de personas, el número de personas que han estrechado la mano de un número impar de otras personas del grupo es par. ^{[ 3 ]}

La secuencia de grados de un grafo no dirigido es la secuencia no creciente de los grados de sus vértices; ^{[ 4 ]} para el grafo anterior es (5, 3, 3, 2, 2, 1, 0). La secuencia de grados es un invariante de grafos , por lo que los grafos isomorfos tienen la misma secuencia de grados. Sin embargo, la secuencia de grados no identifica de forma única un grafo; en algunos casos, grafos no isomorfos tienen la misma secuencia de grados. Un grafo que se identifica salvo isomorfismo por su secuencia de grados se denomina unigrafo y la secuencia de grados correspondiente se denomina unigráfica.

El problema de la secuencia de grados consiste en encontrar algunos o todos los grafos cuya secuencia de grados sea una secuencia no creciente de enteros positivos. (Los ceros finales pueden ignorarse, ya que se obtienen fácilmente añadiendo un número adecuado de vértices aislados al grafo). Una secuencia que es la secuencia de grados de algún grafo simple, es decir, para la cual el problema de la secuencia de grados tiene solución, se denomina secuencia gráfica . Como consecuencia de la fórmula de la suma de grados, cualquier secuencia con una suma impar, como (3, 3, 1), no puede ser la secuencia de grados de un grafo. Lo contrario también es cierto: si una secuencia tiene una suma par, es la secuencia de grados de un multigrafo. La construcción de dicho grafo es sencilla: se conectan los vértices con grados impares en pares (formando un grafo de correspondencia ) y se completan los recuentos de grados pares restantes mediante bucles. La cuestión de si una secuencia de grados dada puede ser realizada por un grafo simple es más compleja. Este problema también se denomina problema de realización de grafos y puede resolverse mediante el teorema de Erdős-Gallai o el algoritmo de Havel-Hakimi . El problema de hallar o estimar el número de grafos con una secuencia de grados dada pertenece al campo de la enumeración de grafos .  

De forma más general, la secuencia de grados de un hipergrafo es la secuencia no creciente de los grados de sus vértices. Una secuencia es${\displaystyle k}$-gráfico si se trata de la secuencia de grados de algún simple${\displaystyle k}$Hipergrafo uniforme. En particular, un${\displaystyle 2}$-La secuencia gráfica es gráfica. Decidir si una secuencia dada es${\displaystyle k}$-El gráfico se puede realizar en tiempo polinomial para${\displaystyle k=2}$a través del teorema de Erdős-Gallai , pero es NP-completo para todos${\displaystyle k\geq 3}$. ^{[ 5 ]}

• Un vértice con grado 0 se denomina vértice aislado .
• Un vértice de grado 1 se denomina vértice hoja, vértice terminal o vértice colgante, y la arista incidente a dicho vértice se denomina arista colgante. En el grafo de la derecha, {3,5} es una arista colgante. Esta terminología es común en el estudio de árboles en la teoría de grafos, y especialmente en el estudio de árboles como estructuras de datos .
• Un vértice con grado n − 1 en un grafo de n vértices se denomina vértice dominante .  

• Si cada vértice del grafo tiene el mismo grado k , el grafo se denomina grafo k- regular y se dice que el grafo en sí tiene grado k . De manera similar, un grafo bipartito en el que cada par de vértices que se encuentran en el mismo lado de la bipartición tienen el mismo grado se denomina grafo biregular .  
• Un grafo no dirigido y conexo tiene un camino euleriano si y solo si tiene 0 o 2 vértices de grado impar. Si no tiene vértices de grado impar, el camino euleriano es un circuito euleriano.
• Un grafo dirigido es un pseudobosque dirigido si y solo si cada vértice tiene un grado de salida como máximo  1. Un grafo funcional es un caso especial de pseudobosque en el que cada vértice tiene un grado de salida exactamente  1.
• Según el teorema de Brooks , cualquier grafo G que no sea una camarilla o un ciclo impar tiene un número cromático como máximo  Δ( G ), y según el teorema de Vizing, cualquier grafo tiene un índice cromático como máximo Δ( G )  +  1.
• Un grafo k -degenerado es un grafo en el que cada subgrafo tiene un vértice de grado como máximo k .

• Grado de entrada , grado de salida para digrafos
• Distribución de grados
• Secuencia de grados para grafos bipartitos

• Erdős, P .; Gallai, T. (1960). "Gráfok előírt fokszámú pontokkal" (PDF) . Matematikai Lapok (en húngaro). 11 : 264–274 ..
• Havel, Václav (1955). "Una observación sobre la existencia de gráficos finitos" . Časopis Pro Pěstování Matematiky (en checo). 80 (4): 477– 480. doi : 10.21136/CPM.1955.108220 .
• Hakimi, SL (1962). "Sobre la realizabilidad de un conjunto de enteros como grados de los vértices de un grafo lineal. I". Journal of the Society for Industrial and Applied Mathematics . 10 (3): 496– 506. doi : 10.1137/0110037 . MR 0148049 . .
• Sierksma, Gerard; Hoogeveen, Han (1991). "Siete criterios para que secuencias de números enteros sean gráficas" . Revista de teoría de grafos . 15 (2): 223– 231. doi : 10.1002/jgt.3190150209 . SEÑOR 1106533 . .