系统结构论

系统结构论 系统结构论基础概念解释. 系统结构的意义 系统内元素的分布状态与联系方式. 分布状态用元素的位置来描述. 联系方式用结构系统来描述,如树, 网络,森林,线,环等及其组合成的复合结构. 具体结构. 二元结构 1. 3. 2. 122 1.线性结构 元素成线状联系在一起. 2.非线性结构 .元素结构图形状非直线型. 3.树形结构 元素按树状分布并联系在一起. 4.网状结构 元素按网状分布并联系在一起. 4.环状结构 元素按环状分布并联系在一起. 123 系统结构论基础系统结构论基础 系统结构是建立和处理离散数学模型的一种重要工具。系统结构论是一门应用性很强 的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、 计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立系统结构论模 型来解决。随着计算机科学的发展，系统结构论的应用也越来越广泛，同时系统结构论也 得到了充分的发展。这里将主要介绍与系统科学关系密切的系统结构论的内容。 1.1 系统结构的基本概念 我们已知集合的笛卡尔积的概念，为了定义无向系统，还需要给出集合的无序积的概 念。 任意两个元素 a,b 构成的无序对无序对（Unordered pair）记作a,b，这里总有a,b  b,a。 设A,B为两个集合，无序对的集合{a,ba AbB}称为集合 A 与 B 的无序积无序积 （Unordered Product），记作A若u  v，称e与u关联的次数关联的次数为 2；若u不是e的端点，则称e与u的关关 联次数联次数为 0（或称 e e与 u 不关联不关联）。在系统6.1-3 中，e1 v1,v2,v1,v2是e1的端点，e1 与v1、v2的关联次数均为 1，v5是孤立元素，e2是环，e2与v2关联的次数为 2。 当e  u,v 是联系时， 又称u是e的始元素始元素Initial Element，v是e的终元素终元素Terminal Element。 如果系统的元素集V和联系集E都是有限集，则称系统为有限系统有限系统Finite System，本 书讨论的系统都是有限系统。若系统S V,E 中V  n,E  m,为了方便起见，这样 0 系统称为零系统 零系统Null的系统也称为n,m系统系统，有时也简称 n 阶系统阶系统。这时 n， System，1,0 系统称为平凡系统平凡系统Trivial System。 关联于同一对元素的两条联系称为 平行联系平行联系Parallel Connection（若是联系方向应相 同），平行联系的条数称为 联系的重数联系的重数 。不含平行联系和环的系统称 简单系统简单系统 Simple System。在本书中除非特别声明，一般是指简单系统。 1.1.21.1.2 元素的度元素的度 定义定义 1.1-31.1-3设S V,E 为一无向系统，v V,v关联联系的次数称为 v 的度数度数， 简称度度DeSree，记作的 dv。 v V,v 作为联系的始点的次数， 设S V,E 为一系统，称为 v 的出度出度Out Degree， 记作d v；v 作为联系的终元素的次数称为 v 的入度入度In Degree，记作d v；v 作为联 系的端点的次数称为 v 的度数度数，简称度度Degree，记作dv，显然dv  d v  dv。 在系统 1.1-3 中，dv1  3，dv2  4，dv4 1，dv5  0； 在系统 1.1-4 中，d v1  2，d v1 1，    dv 4  0,dv 4  0,dv 2  dv 2  2。 称度为 1 的元素为悬挂点悬挂点Hanging Element，与悬挂点关联的联系称为悬挂联系悬挂联系Hanging Connection。如系统 1.1-3 中，v4是悬挂点，e6是悬挂联系。 S  mindvvVS,分别称为系统S 的最大最大 度度Max Degree和最小度最小度Min Degree。若S V,E 是系统，除了S,S，还有如 记S  max dvvVS, 下的定义   最大出度最大出度 G  max d vvV  最大入度最大入度 G  max d vvV 最小出度最小出度 最小入度最小入度       G  mind G  mind    vvV vvV 124 系统 6.1-4 中,S  4, S  2, S  2,S  0,S  2,S 1. 例例 1.1-21.1-2在图 1.1-3 中 dv  dv  dv  dv  dv  dv  3 4 410 12,而该系统有６条 12345 vV 联系，即元素度数和是联系数的２倍。事实上这是系统的一般性质。 定理定理 1.1-11.1-1 设系统S为具有元素集{v1,v2,.,vn}的 n,m 系统， 则  dv  2m。 i i1 n 若dv为奇数，则称v为奇度元素奇度元素, , 简称简称 奇元素奇元素，若dv为偶数，则称v为偶度元偶度元 素素 , ,简称简称 偶元素偶元素。 推论推论任一系统中，奇元素个数为偶数。 证明证明设V 1 {vv为奇元素}，V 2 {vv为偶元素}， 则所以dv也是偶数， 而V dv dv dv  2m ,因为dv是偶数， vV2vV 1 vV1vV2vV1 中每个点v的度dv均为奇数，因此V 1 为偶数。 对系统，还有下面的定理。 定理定理 1.1-21.1-2设系统S V,E ，v {v1,v2,.,vn}， E  m 则d i1 n v i dv i  m. i1 n 以上两个定理及推论都很重要，要牢记并灵活运用。 设v {v1,v2,.,vn}是系统S的元素集， 称dv1,dv2,., dv n 为S的度序列。 如系 统 1.1-3 的度序列为3,4,4,1,0，系统 1.1-4 的度序列是3,4,3,2。 例例 1.1-31.1-3⑴系统S的度序列为2,2,3,3,4，则联系数m是多少 ⑵ 3,3,2,3；5,2,3,1,4能成为系统的度序列吗为什么 ⑶系统S有 12 条联系，度数为３的元素有６个，其余元素度均小于３，问系统G中 至少有几个元素 解解 ⑴由握手定理 2m dv  2  2  3 3 4 14，所以 vV m  7 ⑵由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为系统 的度序列。 ⑶由握手定理 dv  2m  24