Grado (teoría de grafos)

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En teoría de grafos, el grado (o valencia) de un vértice de un gráfico es el número de aristas que inciden en el vértice; en un multigrafo, un bucle contribuye 2 al grado de un vértice, para los dos extremos de la arista. El grado de un vértice $v$ se denota $tú(v)$ o $tú v$ . El grado máximo de un grafo $GRAMO$ , denotado por $Delta (G)$ , y el grado mínimo de un grafo, denotado por ${ estilo de visualización delta (G)}$ , son el máximo y el mínimo de los grados de sus vértices. 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, todos los vértices tienen el mismo grado, por lo que podemos hablar del grado del grafo. Un gráfico completo (denotado $K_{n}$ , donde $norte$ es el número de vértices en el gráfico) es un tipo especial de gráfico regular donde todos los vértices tienen el grado máximo posible, $n-1$ .

En un gráfico con signo, el número de aristas positivas conectadas al vértice $v$ se denomina grados positivos $(v)$ y el número de aristas negativas conectadas se denomina grados negativos $(v)$ .

Lema de apretón de manos

La fórmula de la suma de grados establece que, dada una gráfica $G=(V,E)$ , ${displaystyle sum _{vin V}deg(v)=2|E|,}$ .

La fórmula implica que en cualquier gráfico no dirigido, el número de vértices con grado impar es par. Esta declaració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 probar que en cualquier grupo de personas, el número de personas que le han dado la mano a un número impar de otras personas del grupo es par.

Secuencia de grados

La secuencia de grados de un gráfico no dirigido es la secuencia no creciente de sus grados de vértice; para el gráfico anterior es (5, 3, 3, 2, 2, 1, 0). La secuencia de grados es un gráfico invariante, por lo que los gráficos isomorfos tienen la misma secuencia de grados. Sin embargo, la secuencia de grados, en general, no identifica de forma única un gráfico; en algunos casos, los gráficos no isomorfos tienen la misma secuencia de grados.

El problema de la secuencia de grados es el problema de encontrar algunos o todos los gráficos con la secuencia de grados siendo una secuencia dada no creciente de números enteros positivos. (Los ceros a la derecha pueden ignorarse ya que se realizan de manera trivial al agregar un número apropiado de vértices aislados al gráfico). Una secuencia que es la secuencia de grados de algún gráfico, es decir, para la cual el problema de secuencia de grados tiene una solución, se llama gráfico o 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 realizarse como la secuencia de grados de un gráfico. 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 un gráfico de este tipo es sencilla: conecte los vértices con grados impares en pares (formando una coincidencia) y complete los recuentos de grados pares restantes mediante bucles automáticos. La cuestión de si una secuencia de grados dada se puede realizar mediante un gráfico simple es más desafiante. Este problema también se denomina problema de realización de gráficos y puede resolverse mediante el teorema de Erdős-Gallai o el algoritmo de Havel-Hakimi. El problema de encontrar o estimar el número de grafos con una secuencia de grados dada es un problema del campo de la enumeración de grafos.

De manera más general, la secuencia de grados de una hipergrafía es la secuencia no creciente de los grados de sus vértices. Una secuencia es gráfica si es la secuencia de grados de alguna $k$ hipergrafía uniforme. En particular, una $2$ secuencia gráfica es gráfica. Decidir si una secuencia dada es $k$ gráfica es factible en tiempo polinomial a $k=2$ través del teorema de Erdős-Gallai, pero es NP-completo para todos $kge 3$ (Deza et al., 2018).

Valores especiales

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

Propiedades globales

Si cada vértice del gráfico tiene el mismo grado k, el gráfico se llama un gráfico k -regular y se dice que el gráfico mismo tiene grado k. Del mismo modo, un grafo bipartito en el que cada dos vértices del mismo lado de la bipartición tienen el mismo grado se denomina grafo biregular.
Un grafo conexo no dirigido tiene un camino euleriano si y solo si tiene 0 o 2 vértices de grado impar. Si tiene 0 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 un pseudobosque en el que cada vértice tiene un grado de salida exactamente 1.
Por el teorema de Brooks, cualquier gráfico G que no sea una camarilla o un ciclo impar tiene un número cromático como máximo Δ(G), y por el teorema de Vizing cualquier gráfico tiene un índice cromático como máximo Δ(G) + 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.

Contenido relacionado

Más resultados...