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

Resumen

This article presents a practical method to count the different signed paths which maintain an electric charge on each one of the lines of an electrical network. We assume that there is just one charge (positive or negative) on each network node. We model the problem of counting the signed paths via the #2SAT problem. The #2SAT problem consists on counting models of Boolean formulas in two conjunctive forms. Our method is based on the topology of the graph representing the electrical network and from which we get its Boolean formula in two conjunctive form. A set of recurrence equations are applied, starting from the terminal nodes up to the root node of the network. Such recurrence equations allow us to compute #2SAT for the formula associated to the electrical network. The computed value (#2SAT) represents the different ways to keep charge on all line of the electrical network.