Algorithm to Count the Number of Signed Paths in an Electrical Network via Boolean Formulas

Abstract

Este artículo presenta un método práctico para contar los diferentes caminos signados los cuales mantienen una carga eléctrica sobre cada una de las líneas de una red eléctrica. Consideramos que hay sólo una carga (positiva o negativa) en cada nodo de la red. Nosotros modelamos el problema de contar los caminos signados vía el problema #2SAT. El problema #2SAT consiste en contar modelos de fórmulas booleanas en dos forma conjuntiva. Nuestro método esta basado en la topología del grafo que representa la red eléctrica y de la cual se obtiene su fórmula booleana en dos forma conjuntiva. Un conjunto de ecuaciones de recurrencia son aplicadas, partiendo de los nodos terminales hacia el nodo raíz de la red. Tales ecuaciones de recurrencianos permiten calcular el valor #2SAT para la fórmula asociada a la red eléctrica. El valor calculado (#2SAT) representa las diferentes formas de mantener carga sobre todas las líneas dela red eléctrica.