系统结构论.doc

系统结构论 系统结构论基础概念解释. 系统结构的意义: 系统内元素的分布状态与联系方式. 分布状态用元素的位置来描述. 联系方式用结构系统来描述,如树, 网络,森林,线,环等及其组合成的复合结构. 具体结构. 二元结构: 2. 3.  1.线性结构 元素成线状联系在一起. 2.非线性结构 . 元素结构图形状非直线型. 3.树形结构 元素按树状分布并联系在一起. 4.网状结构 元素按网状分布并联系在一起. 4.环状结构 元素按环状分布并联系在一起.  系统结构论 系统结构是建立和处理离散数学模型的一重要工具论是一门应用性很强的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题都可以建立论模型来解决。随着计算机科学的发展，论的用也越来越，同时也得到了充分的发展。主要介绍与科学关系密切的的内容。 的基本概念 我们已集合的笛卡尔积的概念，为了定义，还需要给出集合的无序积的概念。。 设为两个集合，无序对集合称为集合A与B的无序积，记作。无序。 例如，设，，则,。 为了引出的定义，我们先介绍如下的例子。 例(1) 北京上海香港是中国的几个著名的城市，分别用字母表示为,城市的集合为，城市间现有的航线的集合是。我们也可以将这些城市的航线关系用来表示。 的程序框.1-2 1.1.1 系统的定义及相关概念定义.1-1 一个无向是一个二元组，记作，其中是一个非空集合，element）；E是无序积的多重子集元素可重复出现的集合，称为的集，中的元素称为无向或简称。 在一个中，为了表示分别是的集和，常将记成，而将记成。以上给出的是一个的数学定义。们可以用来表示，而这种有助于我们理解的性质。这种表示法每个用点来表示，每条用线来表示，线连接着代表该端点的两个。例如,,S的如6.1-3所示 定义.1-2　一个是一个二元组，记作，其中是一个非空的集；是笛卡尔积×V的多重子集，其元素称为。 对于一个，一般也画出来表示。例如，其中,的为.1-4。 给标以名称，如.1-3中的这样的称为标定。同时也可对进行标定，, , , , , . 当时,称和是的端，并称与和是关联的，而称与是邻接的。若两条关联于同一个，则称两是邻接的。无关联的称为；若一条关联的两个重合，则称此为环。若，则称与（或）关联的次数是1;若，称与关联的次数为2；若不是的端点，则称与的关联次数为0。在6.1-3中，, ,是的端点，与的关联次数均为1，是，是环，与关联的次数为2。 当是时，又称是的，是的终。 如果的和都是有限集，则称为有限，本书讨论的都是有限。若中,,为了方便起见，这样的也称为，有时也简称阶。系统称为零，称为平凡。 关联于同一对的两条称为（若是方向应相同）。不含平行和环的称。在本书中除非特别声明，一般是指。 的度 定义.1-3 设为一，,关联的次数称为的度数，简称度，记作。 设为一，,作为的始点的次数，称为的出度，记作；作为的的次数称为的入度，记作；作为的点的次数称为的度数，简称度，记作，显然。 在.1-3中，，，，；在.1-4中，，，,,。 称度为1的为悬挂点，悬挂点的称为悬挂。如中，是悬挂点，是悬挂。 记, ,别称为的最大度和最小度。若是，除了,，还有如下的定义 最大出度 最大入度 最小出度 最小入度 6.1-4中,, , ,,, . 例.1-2 在.1-3中 而该有６，即度数和是数的２倍。事实上这是的一般性质。 定理.1-1 设为具有的，则 若为奇数，则称为奇，若为偶数，则称为偶。 推论 任一中，个数为偶数。 证明　　设，， 则因为是偶数，所以也是偶数，而中每个点的度均为奇数，因此为偶数。 对，还有下面的定理。 定理.1-2　设，， 则以上两个定理及推论都很重要，要牢记并灵活运用。 设是的，称为的度序列。如.1-3的度序列为，.1-4的度序列是。 例.1-3 ⑴系统的度序列为，则数是多少？ 　； 能成为的度序列吗？为什么？ 　有12条，度数为３的有６个，其余度均小于３，问中至少有几个？ 解　由握手定理 所以　　　 　由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为的度序列。 　由握手定理，度数为３的有６个占去18度，还有６度由其余占有，其余的度数可为，当均为２时所用数最少，所以应由３个占有这６度，即中至少有９个。 证明在个人的集体，总有两个人在此中恰有相同个数的朋友。 解 以代表人，二人如果是朋友，则在代表他们的间连上一条，这样可得无向，每个人的朋友数是中代表他的的度数，于是问题转化为：阶无向必有两个的度数相同。 用反证法，设中个的度数均不相同，则度序列为，说明中有，而是，这与有度相矛盾所以必有两个的度数相同。 定义6.1-4 设是无向