Grafo nulo

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 ₀ , es el único grafo que no tiene vértices (por lo tanto, su orden es cero). De ello se deduce que K ₀ tampoco tiene aristas . Así, el grafo nulo es un grafo regular de grado cero. Algunos autores excluyen a K ₀ de la consideración como grafo (ya sea por definición o, más simplemente, por conveniencia). La utilidad de incluir K ₀ como grafo válido depende del contexto. Por un lado, K ₀ se deduce naturalmente de las definiciones habituales de grafo en 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 ambos vacíos ), en demostraciones sirve como caso base natural para la inducción matemática y, de manera similar, en estructuras de datos definidas recursivamente, K ₀ 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 , todo árbol binario no nulo tiene exactamente dos hijos). En el lado negativo, incluir K ₀ como grafo requiere que muchas fórmulas bien definidas para propiedades de grafos incluyan excepciones para él (por ejemplo, o bien "contar todos los componentes fuertemente conexos de un grafo" se convierte en "contar todos los componentes fuertemente conexos no nulos de un grafo", o bien la definición de grafos conexos debe modificarse para no incluir K ₀ ). Para evitar la necesidad de tales excepciones, a menudo se asume en la literatura que el término grafo implica "grafo con al menos un vértice" a menos que el contexto sugiera lo contrario. ^{[ 2 ] [ 3 ]}

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 ₀ cumple ( vacuamente ) la mayoría de las mismas propiedades básicas de grafos que K ₁ (el grafo con un vértice y sin aristas). Por ejemplo, K ₀ tiene tamaño cero, es igual a su complemento K ₀ , 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 a la vez un grafo completo y un grafo sin aristas. Sin embargo, las definiciones de cada una de estas propiedades de grafos variarán según el contexto y si se admite K ₀ .

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. Un grafo sin aristas se denomina ocasionalmente grafo nulo en contextos donde no se permite el grafo de orden cero. ^{[ 2 ] [ 3 ]}

Es un grafo 0- regular . 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 .

• Glosario de teoría de grafos
• Gráfico cíclico
• Grafo de ruta

• Contenido multimedia relacionado con gráficos nulos en Wikimedia Commons.