En la matemática campo de la teoría de grafos , el término " grafo nulo " puede referirse ya sea a la orden - cero gráfico , o alternativamente, a cualquier gráfico sin aristas (este último a veces se llama un "gráfico de vacío").
Gráfico de orden cero
Gráfico de orden cero (gráfico nulo) | |
---|---|
Vértices | 0 |
Bordes | 0 |
Circunferencia | |
Automorfismos | 1 |
Número cromático | 0 |
Índice cromático | 0 |
Género | 0 |
Propiedades | Integral Symmetric Treewidth -1 |
Notación | |
Tabla de gráficos y parámetros |
El gráfico de orden cero ,, es el gráfico único que no tiene vértices (por lo tanto, su orden es cero). Resulta quetampoco tiene bordes . Por tanto, el gráfico nulo es un gráfico regular de grado cero. Algunos autores excluyendesde la consideración como un gráfico (ya sea por definición, o más simplemente por una cuestión de conveniencia). Ya sea que incluyacomo un gráfico válido es útil depende del contexto. En el lado positivo,se sigue naturalmente de las definiciones habituales de la 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 vacíos ), en las demostraciones sirve como un caso base natural para inducción matemática , y de manera similar, en estructuras de datos definidas de forma recursiva es útil para definir el caso base para la recursividad (al tratar el árbol nulo como el hijo de los bordes faltantes en cualquier árbol binario no nulo , cada árbol binario no nulo tiene exactamente dos hijos). En el lado negativo, incluyendoya que un 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 fuertemente conectados no nulos 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 asume 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 gráfico de orden cero es, según algunas definiciones de "categoría de gráficos", el objeto inicial de la categoría.
cumple (al vacío ) la mayoría de las mismas propiedades básicas del gráfico que(el gráfico con un vértice y sin aristas). Como algunos ejemplos,es de tamaño cero, es igual a su gráfico de complemento , un bosque y un gráfico plano . Se puede considerar no dirigidos , dirigida , o incluso ambos; cuando se considera según las indicaciones, es un gráfico acíclico dirigido . Y es tanto un gráfico completo como 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.
Gráfico sin bordes
Gráfico sin bordes (gráfico vacío, gráfico nulo) | |
---|---|
Vértices | norte |
Bordes | 0 |
Radio | 0 |
Diámetro | 0 |
Circunferencia | |
Automorfismos | ¡norte! |
Número cromático | 1 |
Índice cromático | 0 |
Género | 0 |
Propiedades | Simétrico integral |
Notación | |
Tabla de gráficos y parámetros |
Para cada número natural n , el gráfico sin bordes (o gráfico vacío)de orden n es el gráfico con n vértices y cero aristas. En ocasiones, un gráfico sin bordes se denomina gráfico nulo en contextos en los que no se permite el gráfico de orden cero. [1] [2]
Es un gráfico regular 0- . La notaciónsurge del hecho de que el gráfico sin bordes n- vértice es el complemento del gráfico completo .
Ver también
- Glosario de teoría de grafos
- Gráfico de ciclo
- Gráfico de ruta
Notas
- ^ a b Weisstein, Eric W. "Gráfico vacío" . MathWorld .
- ^ a b Weisstein, Eric W. "Gráfico nulo" . MathWorld .
Referencias
- Harary, F. y Read, R. (1973), "¿Es el gráfico nulo un concepto sin sentido?", Graphs and Combinatorics (Conferencia, Universidad George Washington), Springer-Verlag, Nueva York, NY.