资源描述：
《相容商空间理论及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、相容商空间理论及其应用张铃张钹安徽大学清华大学主要内容商空间理论的推广相容关系的几个等价形式相容商空间理论模糊相容关系的几个等价形式极大覆盖网络及其应用模糊相容关系的结构模糊相容关系的度量商空间理论简述给定问题(X,f,T)及等价关系RX—论域，f—属性，T—拓扑（结构）商空间([X],[f],[T])将讨论问题(X,f,T)转化成讨论问题([X],[f],[T])利用从商空间中得到的结论来指导下一步的求解（商逼近的思想）从结构上的逼近获得性质上的逼近等价关系相当于划分，但在具体求解问题时，进行聚类（或简化后）得到的集合往往达不到各子集不相交的条件。于是有必要将等价关系建立的商空间理论推
2、广到更一般的情况。最简单的推广就是将“等价关系”推广成“相容关系”相容关系的几个等价形式相容关系R是X上满足自反、对称的关系，称R为X上相容关系当X为有限集合时R是相容关系，可表成矩阵，满足：（自反）（对称）即：R是对角线＝1,对称的{0,1}矩阵定义1：给定X的一个覆盖，做一矩阵R：则R是一个X上的相容关系定义2：给定相容关系R，做网络：，以X为N的节点集合，若第二种形式：给定网络定义3：给定网络，设是N的所有极大完全子图的集合，称为N的一个完备极大覆盖，记为C*第三种形式：完备极大覆盖C*相容、覆盖和网络之间的关系｛0,1}对称矩阵R21N3C*图中的数字表示定义序号图表示三种概念按
3、定义可以互相转换。下面要证明这种转换是唯一的相容关系的几种等价形式相容关系的几个等价形式（X有限集）定理1：下面的断言是等价的1.给定X上的一个相容关系2.给定上一个对角线上＝1的对称{0,1}矩阵3.给定一个以X为节点集的无自环网络4.给定X的一个完备极大覆盖模糊相容关系的几种等价形式定理2：下面的断言是等价的：给定上的一个模糊相容关系R给定X上的一个分层递阶的覆盖（相容）链：给出一个对角线元素＝1的对称[0,1]矩阵给定以X为节点集的归一化加权网络给定X上的一个对称模糊覆盖其中是其核包含的模糊集给定X上的一个覆盖C，对应唯一一个相容关系R。但是一个相容关系可能对应于不同的覆盖例1：覆
4、盖C1={(1,2),(2,3),(1,3),(3,4)},C2={(1,2,3),(3,4)},、这两个覆盖对应的相容关系均为2134512345我们从相容关系R定义网络N(R)，再从N(R)定义完备极大覆盖C*，将它作为R对应的覆盖，这样定义的覆盖是唯一的。这样就得到相容与覆盖的对应关系（相当于等价与划分的关系）相容关系与论域上的拓扑的关系定义3.1:给定X上的一个覆盖先将覆盖C改成表示形式。其中然后在X上定义一个等价关系：得到商空间记为令其中给定问题，在上定义拓扑基：其中表C中集合的有限并。由产生的拓扑记为定义为问题关于相容关系C的商空间命题3.1：是连续的保假原理：问题在中无解，
5、则对应的问题在也无解。命题3.2：若问题在中有解，且是中的连通集，则对应的问题在也有解。应用覆盖网络定义4.1：设是N的所有极大完全子图集合，称是N的一个完备极大覆盖。若是N的极大完全子图，且B是N的覆盖，称是N的极大覆盖下面讨论将相容商空间方法应用于网络中求两点的最短程。目前图论中求最短程的主要方法是：Dijkstra方法和Floyd方法Dijkstra,Floyd方法提出至今已50年，但未见有本质的改进方法提出[1]Dijkstra,E.W.,Anoteontwoproblemsinconnexionwithgraphs,InNumerischeMathematik,1(1959),
6、S.269-271.[2]Bellman,Richard,Onaroutingproblem,QuarterlyofAppliedMathematics,Volume16,Number1,pp.87-90,1958.定义4.2:给定一个网络N，设C是N的一个极大覆盖，作网络：以为节点，若有公共点，则定义对应的两节点相连，所得到的网络，称为N的一级覆盖网络，记为。归纳定义，设已求到N的第i级覆盖网络，设是的一级覆盖网络，则称为N的第i+1级覆盖网络上面定义的完备极大覆盖，主要是为了与相容关系有一个一一对应的关系，但要求出所有的极大完全子图其计算量是NP完全问题，好在在实际应用中，一般只需要
7、极大覆盖就可以，不必求完备极大覆盖。我们已得到求N的极大覆盖链的算法，其复杂性为，其中m是N的边的个数。定义4.3:：给定一个网络N，设L是N中由a到节点b的最短程，，是N的1级覆盖网络，定义L在的投影其中归纳定义：令定理4.2:给定一个网络N，设L是N中由a到节点b的最短程，充分必要条件是上由由到的最短程（其中，是L在第i级覆盖网络上的投影）N的极大覆盖链对应于N的一个覆盖链。于是定理4.2说明在原来空间N上求最短程问题可以转化成
