系统结构论

系统结构论 系统结构论基础概念解释. 系统结构的意义: 系统内元素的分布状态与联系方式. 分布状态用元素的位置来描述. 联系方式用结构系统来描述,如树, 网络,森林,线,环等及其组合成的复合结构. 具体结构. 二元结构: 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,b)a 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)，记作的 d(v)。 v V,v 作为联系的始点的次数， 设S V,E 为一系统，称为 v 的出度出度(Out Degree)， 记作d (v)；v 作为联系的终元素的次数称为 v 的入度入度(In Degree)，记作d (v)；v 作为联 系的端点的次数称为 v 的度数度数，简称度度(Degree)，记作d(v)，显然d(v)  d (v)  d(v)。 在系统 1.1-3 中，d(v1)  3，d(v2)  4，d(v4) 1，d(v5)  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d(v)vV(S),分别称为系统S 的最大最大 度度(Max Degree)和最小度最小度(Min Degree)。若S V,E 是系统，除了(S),(S)，还有如 记(S)  max d(v)vV(S), 下的定义   最大出度最大出度 (G)  max d (v)vV  最大入度最大入度 (G)  max d (v)vV 最小出度最小出度 最小入度最小入度       (G)  mind (G)  mind    (v)vV (v)v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 中 d(v)  d(v ) d(v ) d(v ) d(v ) d(v )  3 4 410 12,而该系统有６条 12345 vV 联系，即元素度数和是联系数的２倍。事实上这是系统的一般性质。 定理定理 1.1-11.1-1 设系统S为具有元素集{v1,v2,.,vn}的 n,m 系统， 则  d(v )  2m。 i i1 n 若d(v)为奇数，则称v为奇度元素奇度元素, , 简称简称 奇元素奇元素，若d(v)为偶数，则称v为偶度元偶度元 素素 , ,简称简称 偶元素偶元素。 推论推论任一系统中，奇元素个数为偶数。 证明证明设V 1 {vv为奇元素}，V 2 {vv为偶元素}， 则所以d(v)也是偶数， 而V d(v) d(v) d(v)  2m ,因为d(v)是偶数， vV2vV 1 vV1vV2vV1 中每个点v的度d(v)均为奇数，因此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的元素集， 称d(v1),d(v2),., d(v 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 d(v)  2  2  3 3 4 14，所以 vV m  7 ⑵由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为系统 的度序列。 ⑶由握手定理 d(v)  2m  24