##### Document Text Contents

Page 1

TOPICS IN THE GENERAL THEORY OF STRUCTURES

Page 2

THEORY AND DECISION LIBRARY

General Editors: W. Leinfellner and G. Eberlein

Series A: Philosophy and Methodology of the Social Sciences

Editors: W. Leinfellner (Technical University of Vienna)

G. Eberlein (Technical University of Munich)

Series B: Mathematical and Statistical Methods

Editor: H. Skala (University of Paderborn)

Series C: Game Theory, Mathematical Programming and Mathematical

Economics

Editor: S. Tijs (University of Nijmegen)

Series D: System Theory, Knowledge Engineering and Problem Solving

Editor: W. Janko (University of Vienna)

SERIES D: SYSTEM THEORY, KNOWLEDGE ENGINEERING AND

PROBLEM SOLVING

Editor: W. Janko (Vienna)

Editorial Board

G. Feichtinger (Vienna), H. T. Nguyen (Las Cruces), N. B. Nicolau (Palma de Mallorca),

o. Opitz (Augsburg), H. J. Skala (Paderborn), M. Sugeno (Yokohama).

Scope

This series focuses on the design and description of organisations and systems with application

to the social sciences. Formal treatment of the subjects is encouraged. Systems theory,

information systems, system analysis, interrelated structures, program systems and expert

systems are considered to be a theme within the series. The fundamental basics of such concepts

including computational and algorithmic aspects and the investigation of the empirical

behaviour of systems and organisations will be an essential part of this library. The study of

problems related to the interface of systems andorga'nisations to their environment is

supported. Interdisciplinary considerations are welcome. The publication of recent and

original results will be favoured.

Page 104

100 M. A. AIZERMAN ET AL.

When the set X is denumerable and when the subset X'~ C X of elements

x c X, for which Cf (x) '" x is finite. we denote by Xf set ~U<f'(X''f)' where.

as usual. ce (X'le) indicates set [ 'f (x) I x f. XI(}. Evidently. set X ~

is finite and functionf is a correspondence of set X~ to itself. There-

fore. a finite graph with the above-mentioned connected components corresponds

to function ~ (x).

The function f (x) is called the subordination function or function S.

Oriented graphs with numbered vertices corresponding to functions S

will be called CH-graphs.

Thus. function S defines a finite CH-graph using the set of vertices

X'f . To all the other elements x E. X'\ X l(l (whose number may be infinite)

correspond isolated vertices. which will bE! considered "external to the

structure" and will not be represented in a figure.

Suppose, now. that set X could be represented as a partition into k mi-

nimal subsets X~ ,which makes

Xlf = U X~

ce (X~ ) ~

correspond to itself.

(for i '" j f/J). i 1. 2 ••.•• , k

Then. each of these subsets supplies vertices with the i-th connected

component of· the CH-graph.

Due to the fact that functions S have a single value. it follows that

only a cycle in the i-th connected component corresponds, on graphrf • to

subset X~ f X1e, such that ~. (~;i ) = X~i • If there. is an element xn £. X~i

such that 'f (~) = xn ' then XI/ = £ xnl and subset X~ should not include any

other element satisfying this equality. On graphr~ a tree. whose root is an

encircled vertex, corresponds to such a subset.

For X~i we will use the term complex cycle of the i-th subset ~ , and

for elements x t X~ belonging to complex cycles. the term complex elements

of graph T'f' •

The structure of a CH-graph is univocally determined if. for a given

function S, its subset X~ and the partition of this subset into cycles x~i

is found and, further. it is established which of these are isolated.

To determine subset X~ it is sufficient to consider a sequence of sets

XO' Xl' X2'·······. Xk .·····, where Xo = X'f'. Xi +1 = If (Xi)' i = 1, 2 ••..•

A subset X~ is a set Xk. therefore ~(Xk) = Xk • In reality. graph

r ';+1 with vertices taken from set Xk+1 coincides with graph r ~ with

vertices taken from set Xk • without the hanging vertices. If a CH-graph

contains a chain with maximal length k. having no edges common with any of

its cycles. then X~ = x'ie and X* ~ X'f • To distinguish all cycles X*,) of

subset X~ , which is the partition of X~ into minimal subsets. for which

. *. *.

~(X~1 ) = X~ , requires. in general, a complete analysis of all the

subsets in X~ • To facilitate this search. a procedure can be proposed.

Let be x.t X~and form ~ chain X<fi = [%(X1)' 'f !~X1)' ..•• ' cpk(X1)]

for which Cf 1(x1) = 0/ ( <f 1-1(x1» and f s+1(x1) E: xc( .

This chain always exists and belongs to the j-th connected component.

Now, let X 2 E X'f \ (X~ u X~) and form, for x2' the same chain ~2

This chain will not have intersections with the first one and will re-

present the second cycle of the CH-graph. By continuing this procedure, the

partition of subsets into cycles will be obtained.

Page 105

ANALYSIS OF STRUCTURES BY GRAPH-DYNAMICS 101

Consider, now, the procedure for partitioning the whole set Xo/ of the

CH-graph into subsets xf· 1

For. xi f XL( \ X*'( w~ can build a chain X~ = fXl' Cf l(xl)' •.. ' f'S(xl)j

with f 1(xl) ( f ( ~ 1-l(xl» and ~ s+l(xl) E X~J Such a chain

always exists and belongs to the j-th connected component. Now, for

x2 E. X~ \ x;f U X~ let us construct a chain xq = {x!, Cf.l(x~~, •.. ~t(X2)S

with 'f. t+l(x2) E X~ u X~ . If, at the same time, f t+ (x2) E. X~ U Xtf

all the elements of this chain also belong tn the i-th connected component.

Otherwise, Cf t+l(x2) £; ~i and therefore, all these elements belong to the

i-th connected component.

The continuation of such a procedure leads to the partition of set X

into its component subsets.

Example 2.1. Let x be a set formed by the first 20 letters of the latin

alphabet: X = a, b, c, ••...•. ,s, t. Using X, two functions Cf 1 and tf' 2 are

defined by Table 2.1

x a b c d e f g h i j k 1 m n 0 p q r s

If I (x) b a c d p f a a g j m 1 b n m a q r m

Cf 2 (x) h s c 1 1 P b f 1 0 b 0 c s c a 0 n s

Table

Subsets xt for these functions are

xllf I [ a, b, c, g, h, i, k, m, 0, p, s}

xlCf 2 { a, b, d, c, f, g, h, i, j, k, 1, m, n, 0, p, q, r, t J

Functions !f I' <f2 make these subsets correspond to subsets

'f l(XI Cf 1) = ta , b, g, m, p}

Cf 2tXl If 2) = {a, b, c, f, h, n, 1, 0 p, s J

Subsets X'f for both correspondences are

x 'f 1 = Xl ~ I U 'f 1 (Xl ce I) = Xl Cf I

X if 2 = Xl ce 2 Uf(! 2(X1 <t' 2) = X

t

t

1

2.1

* ,~ In order to distinguish subsets X ~ 1 and X If 2' construct the sequence

of subsets xO r l' Xl Cf I'···· and X°'f 2' X1'f 2'.... as follows:

X0'fl =X~l; Xl'fl = la, b, g, m, pl; x2rl = [a, bJ; x3<f'1 =x2'f\

xOIf 2 = X?'2; Xlr 2 = fa, b, c, f, h, 1, n, 0, p, s}

X21f1 =£a, c, f, h, 0, p, s}; X1'2 = [a, c, f, h, p, s1; X4r2 =X3f2;

Page 208

SUBJECT INDEX

C-Calculus 163, 174, 184-185

C-Calculus, a measure theory model 177-180

C-Calculus mathematical framework 175-176

C-Contour extraction 189

C-Contraction 191

C-Dilation 192

C-Filter 185-186

Classes of Function S 76-85

Coins Distribution Function 24-25

Coins Invariance principle 24-25

Collective Choice 140-142

Collective Opinions 140

Complex Hierarchical Graphs (CH-Graphs) 97-99

CH-Graphs Hultiplication 101-107

CH-Graphs Structure 98-101

Convergence and filtering in C-calculus 166-170

C-Product 164, 184

Cramer-Rao inequality 204

Cross-entropy 201

C-Separation 190

C-Set 164, 184

C-Sum 164, 184

Distance 72

Dynamics of trees 69-72

Function S, First order equations 86-93

Function S Graph 74-75

Function S Higher order equations 94-96

Function S Subordination 72-73

Graph Dynamics Problems 129-131

Graph Trajectory 71, 10t~106

Heisenberg inequality 204

Hierarchical Modular Systems (HHS) 11, 13-14,61

HMS-Distribution Law 15-17

Hierarchical Systems 9-10, 61

Hypergraph in Structural Properties 152-155

Individual Choice 138-139

J-Divergence 202

207

Page 209

208

Levels, Formation of 12-13

Levels, Information of 12

Majority 137

Monetary Systems 18-23

Monetary System reorganization 28

Movement Analysis 193

Natural Language, Self-organizing system 60-64

Partition 9

Pattern 5-6

Population Distribution on a Territory 29-35

Predicate Calculus 149-152

.Quantification 6-8

Refinement 11, 13-14

Set 5

Shannon Entropy 200

Stability 8

Structure 5

Structure and Stability of a complex envelope 113-117

Subsets of periodic solution 107-112

System 5, 149

Tournament Functions 157

Tournament Matrix 158

WEB Grammars 122-128

SUBJECf INDEX

TOPICS IN THE GENERAL THEORY OF STRUCTURES

Page 2

THEORY AND DECISION LIBRARY

General Editors: W. Leinfellner and G. Eberlein

Series A: Philosophy and Methodology of the Social Sciences

Editors: W. Leinfellner (Technical University of Vienna)

G. Eberlein (Technical University of Munich)

Series B: Mathematical and Statistical Methods

Editor: H. Skala (University of Paderborn)

Series C: Game Theory, Mathematical Programming and Mathematical

Economics

Editor: S. Tijs (University of Nijmegen)

Series D: System Theory, Knowledge Engineering and Problem Solving

Editor: W. Janko (University of Vienna)

SERIES D: SYSTEM THEORY, KNOWLEDGE ENGINEERING AND

PROBLEM SOLVING

Editor: W. Janko (Vienna)

Editorial Board

G. Feichtinger (Vienna), H. T. Nguyen (Las Cruces), N. B. Nicolau (Palma de Mallorca),

o. Opitz (Augsburg), H. J. Skala (Paderborn), M. Sugeno (Yokohama).

Scope

This series focuses on the design and description of organisations and systems with application

to the social sciences. Formal treatment of the subjects is encouraged. Systems theory,

information systems, system analysis, interrelated structures, program systems and expert

systems are considered to be a theme within the series. The fundamental basics of such concepts

including computational and algorithmic aspects and the investigation of the empirical

behaviour of systems and organisations will be an essential part of this library. The study of

problems related to the interface of systems andorga'nisations to their environment is

supported. Interdisciplinary considerations are welcome. The publication of recent and

original results will be favoured.

Page 104

100 M. A. AIZERMAN ET AL.

When the set X is denumerable and when the subset X'~ C X of elements

x c X, for which Cf (x) '" x is finite. we denote by Xf set ~U<f'(X''f)' where.

as usual. ce (X'le) indicates set [ 'f (x) I x f. XI(}. Evidently. set X ~

is finite and functionf is a correspondence of set X~ to itself. There-

fore. a finite graph with the above-mentioned connected components corresponds

to function ~ (x).

The function f (x) is called the subordination function or function S.

Oriented graphs with numbered vertices corresponding to functions S

will be called CH-graphs.

Thus. function S defines a finite CH-graph using the set of vertices

X'f . To all the other elements x E. X'\ X l(l (whose number may be infinite)

correspond isolated vertices. which will bE! considered "external to the

structure" and will not be represented in a figure.

Suppose, now. that set X could be represented as a partition into k mi-

nimal subsets X~ ,which makes

Xlf = U X~

ce (X~ ) ~

correspond to itself.

(for i '" j f/J). i 1. 2 ••.•• , k

Then. each of these subsets supplies vertices with the i-th connected

component of· the CH-graph.

Due to the fact that functions S have a single value. it follows that

only a cycle in the i-th connected component corresponds, on graphrf • to

subset X~ f X1e, such that ~. (~;i ) = X~i • If there. is an element xn £. X~i

such that 'f (~) = xn ' then XI/ = £ xnl and subset X~ should not include any

other element satisfying this equality. On graphr~ a tree. whose root is an

encircled vertex, corresponds to such a subset.

For X~i we will use the term complex cycle of the i-th subset ~ , and

for elements x t X~ belonging to complex cycles. the term complex elements

of graph T'f' •

The structure of a CH-graph is univocally determined if. for a given

function S, its subset X~ and the partition of this subset into cycles x~i

is found and, further. it is established which of these are isolated.

To determine subset X~ it is sufficient to consider a sequence of sets

XO' Xl' X2'·······. Xk .·····, where Xo = X'f'. Xi +1 = If (Xi)' i = 1, 2 ••..•

A subset X~ is a set Xk. therefore ~(Xk) = Xk • In reality. graph

r ';+1 with vertices taken from set Xk+1 coincides with graph r ~ with

vertices taken from set Xk • without the hanging vertices. If a CH-graph

contains a chain with maximal length k. having no edges common with any of

its cycles. then X~ = x'ie and X* ~ X'f • To distinguish all cycles X*,) of

subset X~ , which is the partition of X~ into minimal subsets. for which

. *. *.

~(X~1 ) = X~ , requires. in general, a complete analysis of all the

subsets in X~ • To facilitate this search. a procedure can be proposed.

Let be x.t X~and form ~ chain X<fi = [%(X1)' 'f !~X1)' ..•• ' cpk(X1)]

for which Cf 1(x1) = 0/ ( <f 1-1(x1» and f s+1(x1) E: xc( .

This chain always exists and belongs to the j-th connected component.

Now, let X 2 E X'f \ (X~ u X~) and form, for x2' the same chain ~2

This chain will not have intersections with the first one and will re-

present the second cycle of the CH-graph. By continuing this procedure, the

partition of subsets into cycles will be obtained.

Page 105

ANALYSIS OF STRUCTURES BY GRAPH-DYNAMICS 101

Consider, now, the procedure for partitioning the whole set Xo/ of the

CH-graph into subsets xf· 1

For. xi f XL( \ X*'( w~ can build a chain X~ = fXl' Cf l(xl)' •.. ' f'S(xl)j

with f 1(xl) ( f ( ~ 1-l(xl» and ~ s+l(xl) E X~J Such a chain

always exists and belongs to the j-th connected component. Now, for

x2 E. X~ \ x;f U X~ let us construct a chain xq = {x!, Cf.l(x~~, •.. ~t(X2)S

with 'f. t+l(x2) E X~ u X~ . If, at the same time, f t+ (x2) E. X~ U Xtf

all the elements of this chain also belong tn the i-th connected component.

Otherwise, Cf t+l(x2) £; ~i and therefore, all these elements belong to the

i-th connected component.

The continuation of such a procedure leads to the partition of set X

into its component subsets.

Example 2.1. Let x be a set formed by the first 20 letters of the latin

alphabet: X = a, b, c, ••...•. ,s, t. Using X, two functions Cf 1 and tf' 2 are

defined by Table 2.1

x a b c d e f g h i j k 1 m n 0 p q r s

If I (x) b a c d p f a a g j m 1 b n m a q r m

Cf 2 (x) h s c 1 1 P b f 1 0 b 0 c s c a 0 n s

Table

Subsets xt for these functions are

xllf I [ a, b, c, g, h, i, k, m, 0, p, s}

xlCf 2 { a, b, d, c, f, g, h, i, j, k, 1, m, n, 0, p, q, r, t J

Functions !f I' <f2 make these subsets correspond to subsets

'f l(XI Cf 1) = ta , b, g, m, p}

Cf 2tXl If 2) = {a, b, c, f, h, n, 1, 0 p, s J

Subsets X'f for both correspondences are

x 'f 1 = Xl ~ I U 'f 1 (Xl ce I) = Xl Cf I

X if 2 = Xl ce 2 Uf(! 2(X1 <t' 2) = X

t

t

1

2.1

* ,~ In order to distinguish subsets X ~ 1 and X If 2' construct the sequence

of subsets xO r l' Xl Cf I'···· and X°'f 2' X1'f 2'.... as follows:

X0'fl =X~l; Xl'fl = la, b, g, m, pl; x2rl = [a, bJ; x3<f'1 =x2'f\

xOIf 2 = X?'2; Xlr 2 = fa, b, c, f, h, 1, n, 0, p, s}

X21f1 =£a, c, f, h, 0, p, s}; X1'2 = [a, c, f, h, p, s1; X4r2 =X3f2;

Page 208

SUBJECT INDEX

C-Calculus 163, 174, 184-185

C-Calculus, a measure theory model 177-180

C-Calculus mathematical framework 175-176

C-Contour extraction 189

C-Contraction 191

C-Dilation 192

C-Filter 185-186

Classes of Function S 76-85

Coins Distribution Function 24-25

Coins Invariance principle 24-25

Collective Choice 140-142

Collective Opinions 140

Complex Hierarchical Graphs (CH-Graphs) 97-99

CH-Graphs Hultiplication 101-107

CH-Graphs Structure 98-101

Convergence and filtering in C-calculus 166-170

C-Product 164, 184

Cramer-Rao inequality 204

Cross-entropy 201

C-Separation 190

C-Set 164, 184

C-Sum 164, 184

Distance 72

Dynamics of trees 69-72

Function S, First order equations 86-93

Function S Graph 74-75

Function S Higher order equations 94-96

Function S Subordination 72-73

Graph Dynamics Problems 129-131

Graph Trajectory 71, 10t~106

Heisenberg inequality 204

Hierarchical Modular Systems (HHS) 11, 13-14,61

HMS-Distribution Law 15-17

Hierarchical Systems 9-10, 61

Hypergraph in Structural Properties 152-155

Individual Choice 138-139

J-Divergence 202

207

Page 209

208

Levels, Formation of 12-13

Levels, Information of 12

Majority 137

Monetary Systems 18-23

Monetary System reorganization 28

Movement Analysis 193

Natural Language, Self-organizing system 60-64

Partition 9

Pattern 5-6

Population Distribution on a Territory 29-35

Predicate Calculus 149-152

.Quantification 6-8

Refinement 11, 13-14

Set 5

Shannon Entropy 200

Stability 8

Structure 5

Structure and Stability of a complex envelope 113-117

Subsets of periodic solution 107-112

System 5, 149

Tournament Functions 157

Tournament Matrix 158

WEB Grammars 122-128

SUBJECf INDEX