Algoritmo para calcular el índice Merrifield-Simmons sobre mallas poligonales

Abstract

Contar conjuntos independientes en grafos es un problema computacional dentro de la teoría de grafos: incluso grafos de grado máximo tres, se clasifican como #P-completo, por lo que los enfoques clásicos suelen crecer de forma exponencial. En este contexto se propone un algoritmo orientado a calcular el índice de Merrifield-Simmons (MS) en mallas poligonales, estructuras que modelan grafos moleculares asociados algrafeno ya compuestos aromáticos bencenoides. La idea central del método es construir una trayectoria hamiltoniana que visite cada vértice de una cuadrícula hexagonal isomórfica exactamente una vez. El cómputo de los conjuntos independientes se realiza aplicando tres reglas: (1) una recurrencia tipo Fibonacci, cuando la arista visitada pertenece al árbol de búsqueda; (2) una regla de sustracción, al detectar bordes o aristas frontales o posteriores; y (3) una regla de camino de retroceso, que aprovecha las aristas implicadas en retrocesos para recortar de manera importante el número de pasos. La metodología completa incluye generar listas de adyacencias, construir la matriz de adyacencias y ejecutar DFS para localizar ciclos y bordes de retroceso .Aunque el problema sigue siendo exponencial, el algoritmo reduce drásticamente las operaciones del conteo del MS enmallas poligonales, por lo que la estimación del orden de complejidad en el peor caso se expresa como O(2min(r,c)+2xPolinomial(n,m)), mejorando frente a técnicas clásicas de transferencia de matrices.