perm filename ENUMER.DOC[DOC,LMM] blob sn#044082 filedate 1973-05-18 generic text, type T, neo UTF8

ENUMERATION OF THE GRAPHS OF MOLECULES by Larry Masinter Stanford University Computer Science Department ABTRACT. Previously, enumerations of the number of equialence classes of graphs with a given partitions have been given (1,2). These results are extended to give enumerations for the number of equivalence classes of connected multigraphs. Connected multigraphs correspond directly with chemical molecules; thus the enumeration can be applied to count the number of chemical isomers constructable from a given set of atoms. Bounds may be placed on the multiplicity of each edge, corrsponding to restructions on multiple bonds in chemical structures. ENUMERATION OF THE GRAPHS OF MOLECULES 1 INTRODUCTION DEFINITIONS Def. A multi-graph of order n is the set N={1,...,n} (called the ___________ nodes of the graph) together with a mapping f from the set_____ E(n)={{i,j}|1≤i<j≤n} to the set of non-negative integers I+. Those eεE for which f(e)≠0 are said to be edges of the graph; the multiplicity of e is f(e). Also, if e={i,j} then node i is said to____________ be connected to node j with multiplicity f({i,j}). Multi-graphs may be restricted to those whose edges have maximum multiplicity k by restricting the range of f to be the set of integers {0,1,...,k}. A E(n) k-multigraph is thus an element of k .____________ Def. The degree of a node nεN is d(n)=∃ f({n,m}). The degree is ______ m≠n the total number of other nodes n is connected to, with each connection counted the appropriate multiplicity number of times. Def. The degree seqence of a graph f is defined to be the ordered ______ _______ list ds(f)=(o ,o ,...), where o ≤o ≤...≤o , and 1 2 1 2 n |{j:o =k}|=|{l:d(l)=k}|. It is the sorted list of the degrees of the j nodes of f. Def. Given a set X, the symmetric group on X, or S , is defined to be _________ _____ __ _ X the set of all automorphisms from X onto X. Def. Two graphs f, g of order n are said to be isomorphic if there __________ exists a permutation αεS such that ∀i,jεN f({i,j})=g({α(i),α(j)}). N This is written f↔g. Lemma. f↔g => ds(f) = ds(g). Def. Given a set F and an equivalence relation ↔ on F, we define the set of equivalence classes of F under ↔, F/↔, to be {{fεF:f↔g} | gεF}. ENUMERATION OF THE GRAPHS OF MOLECULES 2 STATEMENT OF PROBLEM Thus, the the problem is to find a generating function for the number of equivalence classes of k-multigraphs with a given degree sequence (o ,o ,o ,...) 0 1 2 Burnside lemma. E Given a set E, and a group G, a mapping %:G→S , a set B, and #=B ; E and the equivalence relation for f,gε# f↔g if there exists αεG such that f=g⊗%(α). Given a weight function w:#→@, where @ is a field, such that f↔g => w(f)=w(g). For F an equivalence class in #/↔, define W(F) to be w(f) for any fεF. Then 1 ∃ W(F) = - - ∃ ∃ w(f). Fε#/↔ |G| αεG f=f⊗%α To apply the Bernside lemma to this problem, it is necessary to devise a weight function such that two graphs with the same degree sequence have the same weight and graphs with different degree sequences have different weights. Further, to construct a generating function for the number of graphs with given degree sequences, the degree sequences should be reflected in the exponents of terms in the weight rather than in the coefficient. E(n) Thus, we define the weight function w on k into the set of real o polynomials in u ,u ,...,u by: 1 2 n f({i,j}) w (f)= π (u u ) o 1≤i<j≤n i j ENUMERATION OF THE GRAPHS OF MOLECULES 3 The exponent of u in w (f) will be the degree of node i in the graph i o (N,f). Unfortunately, ds(f)=ds(g) (or even f↔g) does not imply w (f)=w (g); although f and g have the same degree sequence, the o o exponents may be permuted among the u . It is necessary to apply a i symmetrizing operator ∂: Def. For w a function in u , u , ... u , define 1 2 n 1 ∂(w)(u ,u ,...,u )=-- ∃ w(u ,u ,...,u ) 1 2 n n! αεS α α α N 1 2 n Note: 1) ∂ is linear 2) if w is symmetric, then ∂w=w; specifically, ∂∂w=∂w for any w. The weight function w can now be defined by: E for fεk , w(f)=∂w (f). o This weight function satisfies our requirements: if the degree sequence of f is o ≤o ≤o ≤...o , the weight of f will be: 1 2 3 n o1 o2 on ∂u u ...u 1 2 n Then, using the definition of ↔ given earlier, with the representation of the group G=S by: N Def. %:S →S by %(β){i,j}={β(i),β(j)} N E we obtain: ENUMERATION OF THE GRAPHS OF MOLECULES 4 1 ∃ w(f)=-- ∃ ∃ w(f) fε#/↔ n! αεS f=f⊗%α n 1 =-- ∂ ∃ ∃ w (f) n! αεS f=f⊗%α o n Consider ∃ w (f) and the cycles of %α. f=f⊗%α <=> f is constant f=f⊗%αo on each cycle of %α. For a given α, let M be the number of cycles α α of %α; for 1≤r≤M , let C be the set of edges (elements of E) in the α r r-th cycle of %α, and α U = π u u r {l,p}εC l p r Then for f=f⊗%α, f({i,j}) w (f)= π (u u ) o i,j i j M α f(cycle r) = π (U ) r=1 r Since each f=f⊗%α can be specified by its value on the cycles of %α, M there is a 1-1 correspondence between such f and ∨ε{0,1,...,k} , where k is the maximum multiplicity (can be ∞), by ∨(r)=f(cycle r). In particular, Mα α ∨(r) V(α) = ∃ w (f) =∃ π ( U ) f=f⊗%α o ∨ r=1 r ENUMERATION OF THE GRAPHS OF MOLECULES 5 k Mα 1-(U ) Mα 1 = π r π ------- if k=∞) ------- (or } r=1 1 - U r=1 1-U r r 1 Our generating function is now --∂ ∃ V(α). We wish to group the n! αεS N summation by those permutations α with cycle index λ +2λ +...+nλ =n 1 2 n (λ is the number of i-cycles of α; note that this is different from i ⊗ the number of various cycles of %α). Let α (λ ,λ ,...,λ ) be the 1 2 n permutation obtained by filling in the integers 1,...,n into the slots in (.)(.)...(.) (..)(..)(..) ... (.. ...) ---------- ---------- ----- λ 1-cycles λ 2-cycles ... λ n-cycles 1 2 n ⊗ -1 ⊗ For ∨εS , ∨α ∨ has the same cycle structure as α ; further, there N λ n k are exactly Y(λ ,λ ,...,λ )= π (k λ !) such permutations. 1 2 n k=1 k Thus, 1 ⊗ -1 ∃ V(α) = ∃ ----- ∃ V(∨α ∨ ) αεS λ +...+λ =n Y(λ) ∨εS λ N 1 n N