资源描述：
《偏序集上的一种拓扑排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、总38卷 第4期数 学 研 究Vol.38No.42005年12月JournalofMathematicalStudyDec.2005a偏序集上的一种拓扑排序叶先一 张福基(厦门大学数学科学学院,福建厦门361005)摘 要 拓扑排序是有向图的一种重要运算.用一种线性的算法得到有向无圈图的一个更趋于合理的拓扑序列.关键词 拓扑序列;排序;算法中图分类号 O157.5文献标识码 A1 引 言若集合X上的关系R是自反的、反对称的和传递的,则称R是集合X上的偏序(关系).设R是集合X上的偏序,如果对每个x,y∈X,必有xRy或y
2、Rx,则称R是集合X上的全序(关系).由某个集合上的一个偏序加强为该集合上的一个全序,这个操作称为拓扑排序.对一个有无圈图G进行拓扑排序,就是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若∈E(G),则u在线性序列中出现在v之前.通常,这样的线性序列称为满足拓扑次序的序列,简称拓扑序列. 有向无圈图上的点满足偏序关系,在这样的偏序集上得到拓扑序列已经有不少的方法.如Knuth在[2]书中给出了一个求拓扑序列的算法.[5]中用了一种探索式算法计算一个顶点在某个特定条件下的排序.而在文献[6]中Jian
3、junZhou用了DFDA(Depth-FirstDiscoveryAlgorithm)改进了[5]中的算法,并给出了一个拓扑序列的增量的排序.由于有向无圈图可能存在着多个拓扑序列,文献[7]给出了一个求有向图全部拓扑序列的方法.一个自然的问题是,在各种拓扑排序中哪些排序是更合理的?对有向无圈图的一个拓扑序列,实际上已经将图分了层次,我们认为将同层的点按祖先数的大小得其次序.这样能更全面地将有向图的信息在拓扑序列中表示出来.本文先给出了一个求祖先数的算法,而后提出了一个排序算法,结合两个算法得到有向无圈图的一个更合理的拓扑序列
4、.2 求祖先数的算法设图G是一个有向无圈图,我们先给出求图G祖先数的算法.这个算法的思想是从入度为0的点出发,删除一条出弧时,在进入点增加相应的祖先数,直至所有的边全都删除为止.a收稿日期:2005-03-20基金项目:国家自然科学基金资助项目(10371102)©1994-2006ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net第4期 叶先一等:偏序集上的一种拓扑排序·441·算法中ances[
5、i][]存放顶点i的祖先标号.ancestor()找出入度为0的点放入数组m[]′while(图G不是空图){j=1x=m[j]while(m[j++]!=0){for(x的外邻集的每个点i){if(目前i的祖先数为0) 将x的祖先及x本身添加至ances[i][]else{c[]={x}∪ances[x][]ances[i][]=ances[i][]∪c[]}} 删除边xi 把i放入数组b[]中m[j]=0} 将b[]中的元素全都放入m[]中}定理1求祖先数算法的复杂度是O(mn)证明 设有向图有m
6、条边n个点.对每条弧算法要进行一次操作,这个操作就是求集合并的运算.根据文献[4]p18,做集合S1和S2的并需要的时间为O(ûS1û+ûS2û).首先,x并入集合ances[x][]只需一个单位时间,因为x不属于ances[x][].对ancestor()算法而言,ances[i][]和c[]所含元素最多为n-1.因此ances[i][]=ances[i][]∪c[]只需要n个单位时间.所以对每一条弧的操作最多只需要n个单位时间,所以算法的复杂度为O(mn).□3 支配排序算法[1]书中的习题10.1.3可以写成如下引理形式
7、:引理1若D是没有有向圈的有向图,则存在V的一个有序顶点列v1,v2,⋯,vv,使得对于1FiFv,D的每条以vi为头的弧只在{v1,v2,⋯,vi-1}中都有它的尾.从引理可以看出,有向无圈图存在一个拓扑序列,但问题在于对一个有向无圈图,我们原先并未预先知道这个顶点列的满足引理的一个标号.所以我们先给出一个对顶点分层次的标号,如果我们对同层的点考虑其祖先数,这样能得到更合理的拓扑排序.支配排序算法的步骤是:1.先找出图G中入度为0的点也即第一层的点,顺序置入数组S[]中.2.寻找剩下的点中只被S[]中的点支配的点,置入数组b
8、[]中.3.对数组b[]中的点按祖先数递增的顺序进行排序.©1994-2006ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net·442·数学研究2005年4.
