En el campo matemático de la teoría de grafos , el término " gráfico nulo " puede referirse al gráfico de orden cero o, alternativamente, a cualquier gráfico sin aristas (este último a veces se denomina "gráfico vacío").
El gráfico de orden cero , K 0 , es el gráfico único que no tiene vértices (por lo tanto, su orden es cero). De ello se deduce que K 0 tampoco tiene aristas . Por tanto, la gráfica nula es una gráfica regular de grado cero. Algunos autores excluyen K 0 de la consideración como gráfico (ya sea por definición o, más simplemente, por conveniencia). La utilidad de incluir K 0 como gráfico válido depende del contexto. En el lado positivo, K 0 se desprende naturalmente de las definiciones habituales de un gráfico en la teoría de conjuntos (es el par ordenado ( V , E ) para el cual los conjuntos de vértices y aristas, V y E , están vacíos ), en las pruebas se sirve como un caso base natural para la inducción matemática y, de manera similar, en estructuras de datos definidas recursivamente , K 0 es útil para definir el caso base para la recursividad (al tratar el árbol nulo como hijo de los bordes faltantes en cualquier árbol binario no nulo , cada El árbol binario no nulo tiene exactamente dos hijos). En el lado negativo, incluir K 0 como gráfico requiere que muchas fórmulas bien definidas para las propiedades del gráfico incluyan excepciones (por ejemplo, "contar todos los componentes fuertemente conectados de un gráfico" se convierte en "contar todos los componentes no nulos fuertemente conectados" de un gráfico", o la definición de gráficos conectados debe modificarse para no incluir K 0 ). Para evitar la necesidad de tales excepciones, a menudo se supone en la literatura que el término gráfico implica "gráfico con al menos un vértice", a menos que el contexto sugiera lo contrario. [1] [2]
En teoría de categorías , el gráfico de orden cero es, según algunas definiciones de "categoría de gráficos", el objeto inicial de la categoría.
K 0 cumple ( vacuamente ) la mayoría de las mismas propiedades básicas del gráfico que K 1 (el gráfico con un vértice y sin aristas). Como algunos ejemplos, K 0 es de tamaño cero, es igual a su gráfico complemento K 0 , un bosque y un gráfico plano . Puede considerarse no dirigido , dirigido o incluso ambos; cuando se considera dirigido, es un gráfico acíclico dirigido . Y es a la vez un gráfico completo y un gráfico sin bordes. Sin embargo, las definiciones para cada una de estas propiedades del gráfico variarán dependiendo de si el contexto permite K 0 .
Para cada número natural n , el gráfico sin aristas (o gráfico vacío) K n de orden n es el gráfico con n vértices y cero aristas. En ocasiones, un gráfico sin aristas se denomina gráfico nulo en contextos donde no se permite el gráfico de orden cero. [1] [2]
Es un gráfico regular 0 . La notación K n surge del hecho de que el gráfico sin aristas de n vértices es el complemento del gráfico completo K n .
