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