Wang algebra

From KYNNpedia

In algebra and network theory, a Wang algebra is a commutative algebra <math>A</math>, over a field or (more generally) a commutative unital ring, in which <math>A</math> has two additional properties:
(Rule i) For all elements x of <math>A</math>, x + x = 0 (universal additive nilpotency of degree 1).
(Rule ii) For all elements x of <math>A</math>, xx = 0 (universal multiplicative nilpotency of degree 1).<ref name=Duffin>Duffin, R. J. (1959). "An analysis of the Wang algebra of networks". Trans. Amer. Math. Soc. 93: 114–131. doi:10.1090/s0002-9947-1959-0109161-6. MR 0109161.</ref><ref>Chen, Wai-Kai (2 December 2012). "5.4 The Wang-algebra formulation". Applied Graph Theory. North-Holland. pp. 332–352. ISBN 9780444601933. p. 333, p. 334</ref>

History and applications

Rules (i) and (ii) were originally published by K. T. Wang (Wang Ki-Tung, 王 季同) in 1934 as part of a method for analyzing electrical networks.<ref>K. T. Wang (1934). "On a new method of analysis of electrical networks". Memoir 2. National Research Institute of Engineering, Academia Sinica.</ref> From 1935 to 1940, several Chinese electrical engineering researchers published papers on the method. The original Wang algebra is the Grassman algebra over the finite field mod 2.<ref name=Duffin/> At the 57th annual meeting of the American Mathematical Society, held on December 27–29, 1950, Raoul Bott and Richard Duffin introduced the concept of a Wang algebra in their abstract (number 144t) The Wang algebra of networks. They gave an interpretation of the Wang algebra as a particular type of Grassman algebra mod 2.<ref>Whyburn, W. M. (March 1951). "The annual meeting of the society". Bulletin of the American Mathematical Society. 57 (2): 109–152. doi:10.1090/S0002-9904-1951-09479-3. MR 1565283. S2CID 120638163. (See p. 136.)</ref> In 1969 Wai-Kai Chen used the Wang algebra formulation to give a unification of several different techniques for generating the trees of a graph.<ref>Chen, Wai-Kai (1969). "Unified theory on the generation of trees of a graph Part I. The Wang algebra formulation". International Journal of Electronics. 27 (2): 101–117. doi:10.1080/00207216908900016.</ref> The Wang algebra formulation has been used to systematically generate King-Altman directed graph patterns. Such patterns are useful in deriving rate equations in the theory of enzyme kinetics.<ref>Qi, Feng; Dash, Ranjan K.; Han, Yu; Beard, Daniel A. (2009). "Generating rate equations for complex enzyme systems by a computer-assisted systematic method". BMC Bioinformatics. 10: 238. doi:10.1186/1471-2105-10-238. PMC 2729780. PMID 19653903.</ref>

According to Guo Jinhai, professor in the Institute for the History of Natural Sciences of the Chinese Academy of Sciences, Wang Ki Tung's pioneering method of analyzing electrical networks significantly promoted electrical engineering not only in China but in the rest of the world; the Wang algebra formulation is useful in electrical networks for solving problems involving topological methods, graph theory, and Hamiltonian cycles.<ref>郭金海 (Guo Jinhai) (2003). "王季同的电网络分析新方法及其学术影响 (Wang Ki-Tung's New Method for the Analysis of Electric Network and Its Scientific Influence)". The Chinese Journal for the History of Science and Technology, No. 4. Institute for the History of Natural Sciences, Chinese Academy of Sciences: 33–40.</ref>

Wang Algebra and the Spanning Trees of a Graph

The Wang Rules for Finding all Spanning Trees of a Graph G<ref name="Kauffman">Kauffman, Louis H. "Wang Algebra and the Spanning Trees of a Graph" (PDF). Mathematics Department, University of Chicago Illinois.</ref>
  1. For each node write the sum of all the edge-labels that meet that node.
  2. Leave out one node and take the product of the sums of labels for all the remaining nodes.
  3. Expand the product in 2. using the Wang algebra.
  4. The terms in the sum of the expansion obtained in 3. are in 1-1 correspondence with the spanning trees in the graph.

References

<references/>