Un enfoque computacional general para contar grafos etiquetados
Autores: Goyal, Ravi; De Gruttola, Victor
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Un enfoque computacional general para contar grafos etiquetados
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Fórmula recursiva
Gráficos etiquetados
Propiedades de gráficos
Secuencia de grados
Distribución de grados
Estudios de simulación
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 27
Citaciones: Sin citaciones
Este documento presenta una fórmula recursiva general para estimar el número de grafos etiquetados, así como detalles para evaluar la fórmula para las siguientes propiedades de grafos: número de aristas (densidad del grafo), secuencia de grados, distribución de grados, clasificación de mezcla y mezcla de grados, es decir, la fórmula estima el número de grafos etiquetados que tienen valores dados para propiedades del grafo. El enfoque propuesto se puede extender a propiedades adicionales de grafos (por ejemplo, número de triángulos) y también a propiedades de grafos bipartitos. Para configuraciones especiales en las que existen fórmulas de investigaciones anteriores, estudios de simulación demuestran la validez del enfoque propuesto. Además, demostramos cómo nuestro enfoque se puede utilizar para cuantificar el nivel de variabilidad en los valores de una propiedad del grafo en el subconjunto de grafos que mantienen constante un valor especificado de otra propiedad del grafo (o propiedades).
Descripción
Este documento presenta una fórmula recursiva general para estimar el número de grafos etiquetados, así como detalles para evaluar la fórmula para las siguientes propiedades de grafos: número de aristas (densidad del grafo), secuencia de grados, distribución de grados, clasificación de mezcla y mezcla de grados, es decir, la fórmula estima el número de grafos etiquetados que tienen valores dados para propiedades del grafo. El enfoque propuesto se puede extender a propiedades adicionales de grafos (por ejemplo, número de triángulos) y también a propiedades de grafos bipartitos. Para configuraciones especiales en las que existen fórmulas de investigaciones anteriores, estudios de simulación demuestran la validez del enfoque propuesto. Además, demostramos cómo nuestro enfoque se puede utilizar para cuantificar el nivel de variabilidad en los valores de una propiedad del grafo en el subconjunto de grafos que mantienen constante un valor especificado de otra propiedad del grafo (o propiedades).