Algoritmos lineales para el índice de Hosoya y la matriz de Hosoya de un árbol
Autores: Vesel, Aleksander
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Algoritmos lineales para el índice de Hosoya y la matriz de Hosoya de un árbol
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
índice de Hosoya
índices topológicos
Grafo molecular
Descriptor de estructura
Química combinatoria
Matriz de Hosoya
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 22
Citaciones: Sin citaciones
El índice de Hosoya de un grafo se define como el número total de sus conjuntos de aristas independientes. Este índice es un ejemplo importante de índices topológicos, un descriptor de estructura basado en grafos moleculares que es de gran interés en química combinatoria. El índice de Hosoya inspira la introducción de una matriz asociada con un grafo acíclico molecular llamada la matriz de Hosoya. Proponemos un algoritmo lineal simple, que no requiere preprocesamiento, para calcular el índice de Hosoya de un árbol arbitrario. Un enfoque similar nos permite mostrar que la matriz de Hosoya se puede calcular en tiempo constante por entrada de la matriz.
Descripción
El índice de Hosoya de un grafo se define como el número total de sus conjuntos de aristas independientes. Este índice es un ejemplo importante de índices topológicos, un descriptor de estructura basado en grafos moleculares que es de gran interés en química combinatoria. El índice de Hosoya inspira la introducción de una matriz asociada con un grafo acíclico molecular llamada la matriz de Hosoya. Proponemos un algoritmo lineal simple, que no requiere preprocesamiento, para calcular el índice de Hosoya de un árbol arbitrario. Un enfoque similar nos permite mostrar que la matriz de Hosoya se puede calcular en tiempo constante por entrada de la matriz.