En el campo matemático de la teoría de grafos , el término " grafo nulo " puede referirse tanto al grafo de orden cero como, alternativamente, a cualquier grafo sin aristas (este último a veces se denomina "grafo vacío").
El grafo de orden cero , K 0 , es el único grafo que no tiene vértices (por lo tanto, su orden es cero). De ello se deduce que K 0 tampoco tiene aristas . Por lo tanto, el grafo nulo es un grafo regular de grado cero. Algunos autores excluyen a K 0 de la consideración como grafo (ya sea por definición o simplemente por una cuestión de conveniencia). Si incluir a K 0 como un grafo válido es útil depende del contexto. En el lado positivo, K 0 se deduce naturalmente de las definiciones habituales de teoría de conjuntos de un grafo (es el par ordenado ( V , E ) para el cual los conjuntos de vértices y aristas, V y E , están ambos vacíos ), en las demostraciones 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 recursión (al tratar el árbol nulo como el hijo de las aristas faltantes en cualquier árbol binario no nulo , cada árbol binario no nulo tiene exactamente dos hijos). En el lado negativo, incluir K 0 como un gráfico requiere que muchas fórmulas bien definidas para propiedades de gráficos incluyan excepciones para ello (por ejemplo, o bien "contar todos los componentes fuertemente conectados de un gráfico" se convierte en "contar todos los componentes fuertemente conectados no nulos de un gráfico", o bien la definición de gráficos conectados tiene que 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 la teoría de categorías , el grafo de orden cero es, según algunas definiciones de "categoría de grafos", el objeto inicial de la categoría.
K 0 cumple ( vacuamente ) la mayoría de las mismas propiedades básicas de los grafos que K 1 (el grafo con un vértice y sin aristas). Como algunos ejemplos, K 0 es de tamaño cero, es igual a su grafo complementario K 0 , un bosque y un grafo planar . Puede considerarse no dirigido , dirigido o incluso ambos; cuando se considera dirigido, es un grafo acíclico dirigido . Y es tanto un grafo completo como un grafo sin aristas. Sin embargo, las definiciones para cada una de estas propiedades de grafo variarán dependiendo de si el contexto permite K 0 .
Para cada número natural n , el grafo sin aristas (o grafo vacío) K n de orden n es el grafo con n vértices y cero aristas. En ocasiones, un grafo sin aristas se denomina grafo nulo en contextos en los que no se permite el grafo de orden cero. [1] [2]
Es un grafo regular 0-. La notación K n surge del hecho de que el grafo sin aristas de n vértices es el complemento del grafo completo K n .
Medios relacionados con Grafos nulos en Wikimedia Commons