GRAPH THEORY ANALITICS OF SD FLOW DIAGRAM
Associate Prof. Jia Ren'ang
( Jiangxi University, China )
The article advances and discusses a theory that using dig-
graph theory to analyse SD flow diagram. First, on the basis of
the concept strongly connected digraph generation out-tree and
extreme out-tree, we prove two existence generation out—tree
theorem and three relative propositions of flow diagrams genera-
tion out-tree. The method to define the extreme out-tree and
feedback loop set are obtained in complicated SD flow diagrams,
also the general laws are advanecd that each variable produces
corresponding increment that in the feedback loop and extreme out-
tree and at the different simulation moment, one increment4x is
given to certain variable x, All these conclusions are useful to
the debugging and the result-analysis of SD model and are also
useful to analyse the effects of controll variable in system.
I Basic Concepts
Before expounding the problems, we have to cite the follow-
ing basic definitions.
Définition 1.1- A digraph is defined to be a pair (V,X),
where (1) V is a non-empty finite set V=V(D), the elements of V
is called vertices, and (2) X is a set X=xX( p} of ordered pair of
different elements, the elements of X is called arcs,
In accordance with the definition of digraph, the flow dia-
gram in SD is a digraph D=(V,X), its sets of vertices are
V={Ii| Li is level variable, i=1,2,...,m}{J
{Ri} Ri is rate variable, i=1,2,...,.n ju
{Ait Ai is auxiliary variable, i=1,2,.+.,k}U
{Sil Si is supplementary variable, i=1,2,...,g3U
fail ai is constant, i=1,2,...,4}
and its set of arcs are
X={xi] xi is substance channel between two variables, i=1,2,...,
eUfyijyi is information channel between two variables, i=1,2,...,
bY
Let's take SD flow diagram as digraph, the variable symbol in
SD flow diagram is called variable point by a joint name, and sub-
stance and information channel between two variables are called
are by a joint name.
Definitions about in-degree and out-degree of variable point.
Definition 1.2 For the flow diagram D=(V,X), Vis a set of
variable points and X is a set of arcs, x¢X, u,v¢V,x=(u,v), in
which u,v are initial endpoint and terminal endpoint of arc x.
We may call them endpoint by a joint name. The number of arc
which u is taken as its initial endpoint is called out-degree of
u, and it is denoted odDu or Odu. Also, the number of arc which
u is taken as its terminal endpoint is called in-degree of u, and
it is denoted idDu or idu.
Definitions about directed walk, path, circuit(loop) etc.
Definition 1.3 For the flow diagram D=(V,X), let's suppose
there are alternate sequence of variable point and are v, x, V, X,V2
Page 494
System Dynamics '91 Page 495
ooeXnV,,» among which voV,,..+.Vais variable point and 'x,x,,....xXn1is
arc. :
a. For any x,in sequence, v;,.v,;are taken as the endpoints, then
this sequence is called directed semiwalk with length n, and
variable points of the sequence are different,it is semipath.
b. For any x;in sequence, v;,is taken as the initial endpoint,
also v,;is taken as the terminal endpoint, then this sequence
is called directed: walk with length-n, and if variable points
are different in this sequence, it is called directed path.
c.Directed closed-walk is called directed loop.
d. If sequence is directed path, then vocan reach vy.
According to definition 1.3, the feedback loop in SD Flow
Diagram is directed loop.
Definition about connectivity.
Definition.1.4 In flow diagram D, u,v are any two variable
points. If there is a semipath to join them, D is weakly connected,
if there is at least a variable point can be reached by another,
then D is unilateral connected; if they can be reached with each
other, D is strongly connected.
Definition about out-tree.
In the following we call any parts of flow diagram D subgraph
and D is the subgraph of itself.
Definition 1.5 If there is a variable point v in a subgraph
of flow diagram D, and for any variable point of D, there exists
one and only one directed path which is from v to u (for u=v, we
consider that there exists only one path that its length is zero
which is from v to u), then this subgraph is a out-tree, v is the
root of out-tree.
Definition about spanning concept.
Definition 1.6 .The directed semiwalk that include all varia-
ble points of flow diagram D is called spanning directed semiwalk.
By analogy, directed walk, directed semipath, directed path, feed-
back loop, out-tree are called respectively spanning directed walk,
spanning directed semipath, spanning directed path, spanning feed-
back loop,spanning out-tree.
We dont consider reference vertex (constant vertex ai) of flow
diagram at following discuss, because the property of constant aj
in the problem we discuss can be realized by its corresponding
variable point of level, rate or auxiliary variable, But in re-
search we can make the explanation more simple without considering
constant vertex aj.
Sxample 1 Fig. 1.1 shows the flow diagram of SD World Model II
and the spanning out-tree of this flow diagram is shown by Fig 1.2.
The root v of out-tree in the flow diagram (Birth Rate shown
by Fig 1.2) can control] each variable of out-tree, with strongly
practical significance. When one increment Sv is given a variable
v, each variable produce corresponding new increment at the dif-
ferent simulation moment. ‘Thus variable in practical system is
found out, the crucial control variable is out. For example, in
the World Model II, birth rate is a root of one of spanning out-
tree, birth rate may controll each variable, moreover, we may
known ow to controll other variables by out-tree.
But not every flow diagram exists spanning out-tree, for exam-—
ple, SD traffic flow diagram in Fig 1.3 doesn't exist spanning out-
Page 496
System Dynamics '91
tree, This just like that in the social economic system, also not
So
eve
Fig
1,1 SD of the World Model II
*
CIR POLOM
DRe——s PF aL craa~————r BOL: , orm
: |
BRE zs NRFR
sant, Qur CFLFR
CIQE CIAF
Fig 1.2 Diagram
7° Ee AS, > BR
POL DRMM
7 x \ ~*FOLA NRMM
| EPM POLR Quy
4 ae
cID POLAT
of spanning out-tree of SD World Model alg
a —“forip et (PA S-- PP ©
[PRL il tl
opR} {OVI} ‘eS =f oval
S~~R CF &y
Fig 1.3 SD Flow Diagram © the traffic in Beijing
Ly.1 -RY.1 ,L7.2 Bl.2
FT qu bray
FIL L
\
\a15.4 0 R15.1\ L522 RIS 2
R11.1
pry Lea tar] [pa & = opp
\ ,
con \
\ l \\ ry
[AIT«1 Ss \A15 61) \ A160 01
i)
112.1 R121 \ 112.2 R12.2
| OBR: any ‘ OPAhe—— T=fORD] ad]
\ if
~ 4 \
Fig 3.1
Page 497
Page 498 System Dynamics '91
Note: SD Flow Diagram of the traffic in Beijing includes four
subgraphes, they are path, freight transport, passenger traffic
and other traffic subgraph. For details, please see the fifth
reference.
Il The existing condition of spanning out-tree
Theorem 2.1 Unilateral connected flow diagram exists spanning
out-tree.
Proof By the theorem 5.6.2 in[I], a flow diagram D is uni-
lateral connected flow diagram, if, and only if, there is a span-
ning atrected walk in flow diagram D. Suppose W= vi v2... wnis
point-sequence of spanning directed walk Wiwhich contains a little
arcs in D, then j¥1, idvj21, jan,Odvjz1.
a. If idviz0, for (vj,vi), leave out the arc (vj,vi), then
Wi becomes subgraph W2 of satisfying idvi=0.
b. For each (Vi, Vj), by leaving out each arc (vg,vj )(ke1), then
Wz becomes W3o0f idvj=1 in (v,Vj).
ec. For each (v;,vk) satisfying each (v,),v;) in W3, by the way
as that in b that leave out the arc (vt svg (ick) 5 then W3 becomes
W4 that make every vysatisfy idvke=].
By analogy, subgraph Wy is obtained. The vertice sets of va-
riable points in Wn is{vo,w,...,Vnt,where idv=0,idv=1 (j=2,3,...,n).
Because in-are of v;which hasn't been considered are not taken
out during defing Wn, Wn is weakly connected.
According to theorem3.4.2 in{1}, Wn is a out-tree, because
it insides all variable points in D, it is a spanning out-tree
of D. QED |
Theorem 2.2 vi i8 @ initial endpoint of a spanning directed
walk Wn of the unilateral connected rays diagram D, if, and only
if, v, is a root of a out-tree T of the unilateral connected flow
diagram.
Proof Root vi of out-tree Wn constructed during proving
theorem 2.1 is one initial endpoint of a directed walk W of uni-
lateral connected flow diagram. Necessity is tenable.
By theorem 5.6.2 infl), for the unilateral connected flow
diagram D, vzva... Wn exists unilateral walk Wf-1, because v; is
the root of out-tree /, v,; may connect with any v3(j=2,3,...)n).
So there is a unilateral walk with initial endpoint v,, which is
consisted by v, and Wnt, Q.E.D
Theorem 2.5 A flow diagram LD is strongly connected, if, and
only if, there exists spanning out-tree in it and each variable
point is the root of certain spanning omt-tree 1.
Proof By theorem 5.6.2 in (IJ, a flow diagram D is strongly
connected, if, and only if, there is a spanning closed directed
walk in it. Therefore, each variable point v exists unilateral
directed walk with initial endpoint v};. By theorem 1.2, there
exists spanning out-tree with a root vj . Necessity is tenable.
Vice versa, because the root of spanning out-tree can connect
with each variable point of out-tree, each variable point in D
can be reached with each othef. Sufficiency is tenable.
System Dynamics '91 Page 499
Strongly connected flow diagram posses very good property.
Proposition 2.1 In the strongly connected tiow diagram,
when one increment is given to any variable point, other variable
points will produce corresponding increment.
For many flow diagrams, when their exogenous variable points
and supplementary variable points are taken out, they can posses
strong connectivity. For example, the World Model II is just. like
this. But it is very troublesome to judge the strong connectivity
of a complicated flow diagram with the definition of strongly con-
nected. The following two proposition can help us do it more simple.
t Eropost tioy 2.2 A feedback loop is a branch of strongly con-
nected.
Proposition 2.3 Suppose Dj=(V(Dj),X(D;))(i=1,2) are two
branches of strongly connected of flow diagram D=(V(D),X(D)), when
one of the following conditions is satistiea, the derived subgraph
D3=(V(D3), X(D3)) of V(D; )UV(D2) is-the branch of strongly connected.
1.V(D )AV(D ag .
2. There exists arc x,, whose initial endpoint is in V(Dj) and
terminal endpoint is in V(D2),at the same time, there also
exists arc x2, whose initial endpoint is in V(D2), and terminal
endpoint is in V(D)).
So-called derived subgraph D3of V(D,)UV (D2), Dashould satisfy
V¥(D3)=V(D) UV\D2) and u, VEV(D3), if (u,v) X(D), then (u,v)EX(D3)-
We can use definition of strongly connected to prove the above
proposjtion correct directly. In accordance with proposition 2.3,
it is rather easy to judge that the World Model II is strongly
connected.
III, The method to define the extreme out-tree of flow diagram
In this section, we discuss about the extreme out-tree of flow
diagram. .
Definition 3.1 In flow diagram D=(V(D).,x(D)), if for any out-
tree 13(V(T%), X(4)) of D, its out-tree T=(V(T),X(1)) unsatisfies
V(T)CV(Tz), then out-tree T is the extreme out-tree of D.
Not every flow diagram has spanning out-tree, but any one of
flow diagram has extreme out-tree.
Next we first give the method to draw a diagram of extreme
out-tree of branch of strongly connected. Here is a definition.
Definition 3.2 Di=(V(Di), X(Di)) is the subgraph of D=(V(D),
X(D)). If D is strongly connected, and for any variable. poinVé
(V(D)= ¥(D1)), derived subgraph of V(D )U{V} doesn't posses strong.
connectivity, then D; is the branch of extreme strongly connected
of D.
A. The method to define spanning out-tree of branch of extreme
strongly connected.
a. Choose any point V in branch of extreme strongly connected
and leave out all in-arces of point V.
b. Find out all Uj satisfied (V,U;) and leave out all in-arcs
not.satified (V,Wx) from each Ui respectively, then define the
second hierarchy variable point of out-tree (V is the first hie-
rarchy variable point.)
ce. Handle each variable point at the second hierarchy respectively
according to "b", then we will get the third hierarchy variable
point. By analogy, we can get the spanning out-tree T.
The exactitude of this defining method arises from the proof
of theorem 2.1. :
According to this method, let's consider the flow diagram of
Page 500 System Dynamics '91
the World Model II shown by Fig 1.1. We can take Birth Rate as
the roor of out-tree, then we may get the spanning out-tree shown
by Fig 1.2.
B. The method to define extreme out-tree of flow diagram.
a. To define the branch of extreme strongly connected of flow
diagram D with the definition of strongly connected and proposition
2.2, 2.3, and to mark different branches of strongly connected by
the method that give numbers to each variable point. The way is
suppose Dee(V(D;)> X(Dj)) is the code number i branch of extreme
strongly connected, then level, rate,and auxiliary variable point
in D are Lj;, Rix, Ajt pespectively, j,k,t are @Q numbers of
level, rate and auxiliary variable in D respectively.
b. Suppose D),D2.....Dn are n branches of extreme strongly
connected, end draw connected arc of branch of each extreme strongly
connected, only draw one for the same direction arc. At the same
time, suppose Di Day +, Da are variable points, then one no loop
digraph G is got.
ce. Find out the extreme unilateral digraph of digraph G. If
digraph G has G,G2...,.G,x extreme unilateral digraph, then flow
diagram D exists K extreme out-tree.
d. Draw the corresponding spanning out-tree of each digraph
G3 by the way that draw spanning out-tree of branch of extreme
strongly connected. Each spanning out-tree of this is the extreme
out-tree of D.
Example 2. Draw extreme out-tree of traffic flow diagram
in Fig 1.3.
P.S a. To define the branch of extreme strongly connected
by the definition and proposition 2.2, 2.3 of strongly connected.
Then give code numbers to each variable points. ( Shown by Fig 3.1)
b. Suppose branch Di of each extreme connected is variable
point, and draw no loop digraph G as Fig 3.2 .
ec. To draw the extreme unilateral digraph G,,yG2.G3 of
G as Fig 3.2.
d. To draw the corresponding spanning out-tree of each
G3.
4 C. Property of extreme out-tree.
Proposition 3.1 Give one increment to any variable point u
of extreme out-tree of flow diagram D, only the following two kinds
of variable points will produce the corresponding increment in flow
diagram.
as. th€ following variable points of u
b. the preceding variable point Vv of u, this v is torminal end-
point of arc whose initial endpoint is u or following vari-
able point of u.
This property is useful to the debugging of SD model.
IV; The defining method of feedback loop of the finished flow
diagram
The flow diagram is set up gradually. A complicated system
model is always a complicated flow diagram. For example, the flow
diagram of the World Model II is complicated, so it is rather trou-
blesome to list all feedback loop of a complicated flow diagram,
but for the quantitative analysis and qualitative analysis system,
it's very important to find out the sets of feedback loop. ‘So we
advance the gradually-reduce method. First, here is a definition.
System Dynamics '91 Page 501
D2 D3 D7 D6
R2.1 L3,1 7.41317 .1 R641
pa| D8
ate aan 2B.
D1 ——
A5.1 YA9.1
410.4417, 15.75 |__[aTe.t] |ar7.1
D10 D141 DI5 DI6 DIT
A12.13 112.1 A13.1 414.2] py
jzo\_ae_fean
Fig3.2 Stronglt connected points
DI—>b2 —> Ds —+ 89 D6 —+D7 —+D8 —> D9
33—> v4.5 tb)
NS p12 13 —~D14 DIQ—>D11-—-Di2—-D15—> D4
D15 —>D16—>D17 DES D617
(a) (e)
Fig 3.3 The branch of extreme unilateral connectivity
Mah eee sisal eat ast me
R3.
Pa 4 12.1 L7.1
we | A? “112.1 U
3% a7. BAST Ape R7.1 wee men
¢ ¢
Tes. yee! bars... “R122 Rr2 (|. ) A9
age 115.2 +
por Nea
45.2 : R10.1
{Nae 5.2 N
all at7.4 111.1
RT‘ ag.1 RI we
| 112.1 ha
49.1
? R12.1 R15.1 ase
aoewled : Ste
yoN \ at6.1
R12,.2 a13.1 15.2 |
(a) { AIT.1
ai4.1
(Ce)
Fig34 &1l extreme out-tree of connected flow diagram shown by
Fig 3.1
Page 502 System Dynamics '91
Definition 4.1 In the flow diagram D=(V(D),X(D)), if weV(D)
and satisfy with idu=0 or Odu=0, then u is the hanging variable
point of D.
The step of the gradually-reduce method in the feedback loop
sets of finished flow diagram D.
Step 1. Leave out all hanging points and its related arcs
of D to get th@:subgraph D1.
Step 2. For D1, take any level variable point Li of suograpu
D (it can also be rate or auxiliary variable point ), begin with Li
find out all feedback loop of including Lj by the exhaustive way
one by one.
Step 3. Leave out level variable point Lj and its related arcs,
and then leave out all hanging points and related arcs which are
preduced in the course of leaving out, then subgraph D2 of D is got.
Step 4. Execute the step 2,3 repeatedly to the flow diagram
D2, and execute in cycles, then we may get all elements in feedback
loop sets of finished flow diagram. ( The example is omitted. )
V. General laws onAx increment producing corresponding variable
In this section, we will discuss the calculation formula and
general laws on each variable produces corresponding increment that
in the feedback loop and extreme out-tree and at the different si-
mulation moment, one incrementAx is given to certain variable.
Definition 5.1 Variable y is in certain simulation step divi-
tion, because there existsAx of related variable x, andAy=y(now
available value)-y(original value)*0, then the variable y produces
a corresponding incrementAy of order 1. If from jasimulation step
divition to j simulation step divition, there exists the phenomenon
that k simulation step divition produced corresponding increment of
order 1, then variable y produced k corresponding increment.of otter K
j Simulation and is denoted by A(By(k=1,2....).
When y is multifactor variable of x,x....x,and if from the
simulation step divition joto j, factor x;makes y produce corres-
ponding increment4Yand k isn't smaller than the orders of corres-
ponding increment that other factors x; make y produce, then we say
variable y produce increment as to the simulation step divition j
A. Problems about feedback loop
Suppose there exists feedback loop (1!) in SD F.D.
~in < Rn-j<—- An-j~+— In-t<—..... +— R3 e— AZ = — 13
Gan Rn ——~ Li-—> Al —> RI —> Le—> 42> R2
where Lj. Aj. Rjdenote respectively level,auxiliary and rate vari-
able and A} may be the abbreviation of many auxiliary variables,
Ri may be the combination n rate variables.
Proposition 5.1 Suppose there are Li,Ai,Ri in the path of
F.D..D and before them one variable x exists incrementAx at the
jo Simulation divition, then orders of their corresponding incre-
ments are same in simulation divition j>j, at each moment.
The proposition is true because of the provide of DYNAMO lang-
uage in SD. That is, at the same Simulation divitionj,Ai and Ri are
caleulated after calculating li. This result is the foundation of
that next two theorem are true.
We know by proposition 5.1 that only after we get the laws of
Li's changing, we will get the laws of corresponding Ai amd Ri.
Theorem 5.1 In simulation, with the condition without con-
sidering feedback effect and in Rn of feedback loop (1), we add
inerement with thus laws (shown by table 1) from jo simulation
divition.
System Dynamics '91 Page 503
Jj Jo} J,+DT j,+2DT jo+3DT awe LENGTH
Ro | Rn Rn Rn Rn cas Rn
where j, is integer multiple of DI, then the orders of correspond-
ing increment that each variable produce in the feedback loop (1)
should satisfy the following formula,
For A Li(i=t,2,ee0,n)5
0 oS J$o4(4—1) DT
eat Ubedy- (4-1)D0) v2, Jes dacs rena
Fors. Rn, considering feedback effect,
k= 50 jo <j<jot(n-1)DT
3-35. -(n-: jo+mDI< j< LENG
t (n-2)DTJ/DE Di<j< LENGTH
other Ai and Ri produce corresponding increments with the same
orders of Li. mana!
B. The problems about out-tree
Definition 5.2 Suppose T is the out-tree including n vari-
ables of SD flow diagram, then out—tree IT is out-tree of n orders.
Corollory 5.1 Suppose vis the root of n out-tree T of SD
flow diagram. If one incrementAv is given to v just at the simu-
lation step divition j,(j, is integer multiple ef DT), then
a. When v is non-level variable point, at most to the step
divition (j,nDT), each variable point of out-tree will produce
corresponding increment; When v is level variable point, at most
to the step divition j +(n-1)DI, each variable of out—tree will
produce. corresponding increment. ‘ ‘ :
b. If there are k level variables from v to v,,.when v is
non-level variable, v; will produces a corresponding increment
at most to the simulation divition (jotkDT). When v is level
variable point, it can be reduced a step; v,will produce at least
corresponding increment of (n-k) orders when it simulates to the
divition (jynDT).
We have acheived very good results in applying above-metioned
theoty in debugging the model of System Dynamics in Jianxi provi-
eial scientific program.
REFERENCES
1. Li Weixuan,1979, Theory of Graphs. Hunan: Scientific P.H.Press.
2. Jay,W.Forrester,1968. Principles of System. Mass The MIT
Press.
3. Wang Qifan, 1988. System Dynamics. Qinghua University Press.
4. Bondy J.a., Murty U.S.R, 1976. Graph Theory with Applications.
Macmillan Press LTD.
5. Edited by Wang Qifan, 1988. Theses on System Dynamics in the
National academic discussion.
