高校教师排课设计方案毕业论文.doc

《高校教师排课设计方案毕业论文.doc》由会员分享，可在线阅读，更多相关《高校教师排课设计方案毕业论文.doc（24页珍藏版）》请在三一办公上搜索。

1、吕梁学院本科毕业论文（设计）高校教师排课设计方案姓 名 系 别数学系专 业数学与应用数学申请学位学士学位指导教师 职 称 日 期2012年6月摘 要排课是高校教务管理中一项重要的工作,其实质是为学校所设置的课程安排一组适当的教学时间与空间,从而使整个教学活动能够有计划、有秩序地进行.排课要求保证班级、教师、教室不冲突,并且要满足教室、教师资源的实际约束条件,即在同一时间内,同一个班级仅能由一位教师上一门课;同一时间内,同一教室仅能有一个班级占用;一位教师也只能在某一时间内,在某一个教室给某一班级讲授一门课.文章首先应用图论中的匈牙利算法和边着色理论来设计具体排课算法,得出了排课流程图,并用C语

2、言程序予以实现,有效地处理了排课过程中教师、教室和班级三者之间的冲突问题.为了使课表编排更加合理化、人性化,对有限制的排课问题进行了研究.针对固定一位教师的授课时间和班级进行了简单描述,而且也对固定两位教师的授课时间和班级进行了讨论与研究,并分别排出了满足一位教师要求与两位教师要求的课表.关键词: 排课; 匹配; 边着色ABSTRACTRow of class teaching management in Colleges and universities is an important work, and its essence aims to set the curriculum of a

3、n appropriate set of teaching time and space for school, so that the entire teaching activity can be carried out systematicly and orderly. Arranging demand that guarantee class, teacher, and classroom do not conflict, and to consider the actual resource constraints of the classroom and teachers, at

4、the same time, the same class can be used only by a teacher on a class; the same time, the same class can have only one class occupation; a teacher can only at one time, in one room to an class teach a lesson. The first application of the Hungarian algorithm and edge coloring theory in graph theory

5、to design the specific course scheduling algorithm, and gain the scheduling flowchart, and using C language procedures to achieve, to solve effectively the conflict of the scheduling process, the classroom teacher and class among the above three problems. In order to make the arrangement of curricul

6、um schedule more reasonable, humanization, so the restriction of course scheduling problem is studied. According to fixed a teachers teaching time and class, the paper not only make the simply description, but also on the fixed two teachers teaching time and class make the discussion and study, and

7、discharged with a teacher and two teachers demand schedule.Keywords: curriculum arrangement; matching; edge coloring.目 录 引 言1第1章 知识介绍21.1匹配的知识介绍21.2边着色的理论内容5第2章 简单排课模型72.1排课的现状分析72.2排课问题的简化描述72.3排课问题的分析82.4排课算法82.5排课的算法设计92.6思路流程图10第3章 有限制的排课问题113.1一位教师的授课时间与班级固定113.2两位教师的授课时间与班级固定12结束语15参考文献16谢 辞17

8、附 录18附录118附录219引 言课表是学校实施教学计划的时间安排,对保证教学质量具有相当重要的作用.课表编排是一项非常复杂的工作,用手工排课需要付出艰巨的劳动.尽管如此,也不能保证不会发生冲突.随着教学资源、师资力量和招生规模的变化,每次需要多大的工作量、多长时间排出来以及能不能正常安排教学过程都是一个未知数.在排课表时,需要考虑的约束条件太多,有时即便排出的课表能够运用,也不能保证这一课表方案的效果是较好的.为此,国内外对课表问题做了大量的研究,也提出了多种解决方法.1962年,Gotlieb曾提出了一个课表问题的数学模型,并利用匈牙利算法解决了三维线性运输问题;1965年,Mihoc和

9、Balas将课表公式化为了一个优化问题;Krawczk提出了一种线性编程的方法;Junginger将课表问题简化为一个三维运输问题.目前,解决课表问题的方法有:模拟手工课表法、图论法、拉格朗日法、二次分配型法等.通过图论的方式来解决排课问题是一个比较典型的方法.图论的边着色理论可以从根本上避免手工排课的不确定性,它可以综合考虑各方面因素,对排课方案进行优化以满足实际需要.第1章 知识介绍图论是数学的一个分支,它以图为研究对象.图是由若干给定的点和联结两点的线所构成.其中用点代表事物,用联结两点的线表示相应两个事物间具有的特定关系.1.1匹配的知识介绍定义11:一个图定义为一个三元组,记作.其中

10、是个非空有限集合,它的元素称为结点;也是个有限集合,其元素称为边,而是:或:定义的.定义21:在图中,如果每条边都是弧,该图称为有向图;若每条边都是无向边,该图称为无向图.定义31:在有向图中,对任意结点,以为始结点的弧的条数,称为结点的出度,记为;以为终结点的弧的条数,称为的入度,记作;结点的出度与入度之和,称为结点的度数,记为,显然.对于无向图中,结点的度数等于联结它的边数,也记为.对于无向图,记: 它们分别称为图的最大度和最小度.定义41:在无向图中, 如果每个结点的度是, 即,则图称为度正则图.显然,对于度正则图,.三度正则图定义51:给定简单无向图,且,.若和的诱导子图和都是零图,则

11、称是二部图或偶图,并将二部图记作,并称,是的划分.在一个二部图中,若,且对任意的,均有,则称G为完全二部图,记为. 定理14:设是一个正则二分图,则必有的模相等.证明:设. 假设,不妨设,由于是正则的,故由点集引出的边有条,同时连向这个点集的边数亦为条（亦即由点集引出的边数为）,由于是正则的二分图,故点集的每个点的度数为,而,故中点的度数大于,这与是一个正则图矛盾,从而必有的模相等.定理2:简单图为二部图的充要条件是中所有基本圈的长度为偶数.定义6:给定简单无向图,若且中任意两条边都是不邻接的,则子集称为的一个匹配或对集,并把中的边所关联的两个结点称为在下是匹配的.令是的一个匹配,若结点与中的

12、边关联,则称是饱和的;否则,称是不饱和的;若中的每个结点都是饱和的,则称是完全匹配.如果中没有匹配,使,则称是最大匹配.显然,每个完全匹配是最大匹配,但反之不真.例1:图1-1中的一个最大匹配是;的一个完全匹配是.图1-1定义7:令是图中的一个匹配.若存在一个链,它是分别由和中的边交替构成,则称该链是中的交错链;若交错链的始结点和终结点都是不饱和的,则称该链为增广链;特别地,若交错链的始结点也是它的终结点而形成圈,则称该圈为交错圈.定义8:给定两个集合和,与的对称差,记为,其定义为定理31(Berge定理）:图的一个匹配是最大匹配的充要条件是中不含有增广链. 证明 必要性:令是中的最大匹配.用

13、反证法,假设中含有增广链,作其中表示链中所有边的集合.则是的匹配且.可见,不是最大匹配,这与已知矛盾.故中不含有增广链.充分性:假设中不含增广链,且不是的最大匹配,于是可令是的最大匹配,则 (1)考虑,则从定理2可得图(可见图1-2)中每个分图或是交错链,或是交错圈(它必是偶长度).但因(1)知,图中的边比多,所以图中的交错链必以中的边为起始边和终止边,即该链在中饱和的而在中是不饱和的.因此,该链是中的增广链,这与已知中不含增广链矛盾,于是,必是中的最大匹配.在图1-2(a)中有两个匹配和,其中(b)表示图.图1-2定理41(Hall定理):给定二部图,中存在使中每个结点饱和的匹配的充要条件是

14、对任意有 (2)其中表示与中结点邻接的所有结点集合.证明 必要性:假设中存在使中每个结点饱和的匹配,且.因为在作用下,中的结点中的不同结点匹配,显然,.充分性:假设是满足(2)的二部图,但中不存在使中每个结点饱和的匹配.这是与(2)矛盾的.令是中的最大匹配,由刚才假设知,不使中每个结点饱和.所以,在中存在不饱和结点,比如.再令表示经交错链而可达的所有结点集合.因是最大匹配,由定理3可知,是中仅有的不饱和结点.作和(见图1-3).图1-3显然,在作用下,中的结点与中的结点匹配.所以, (3)和.事实上,有 (4)因为中每个结点是经交错链而可达的.由(3)和(4)得到这与(2)矛盾.故中存在使的每

15、个结点饱和的匹配.1.2边着色的理论内容在图论的历史中,有一个著名的问题四色猜想.在一张地图中,若相邻国家着以不同的颜色,那么最少需要多少种颜色呢?每个地图可以导出一个图,其中国家都是点,当相应两个国家相邻时,这两个点用一条线来连结.四色猜想是图论中的一个问题,它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用.在排课系统中主要运用边着色问题来解决核心算法.下面具体介绍一下边着色的理论内容.给定图,对的所有结点进行着色时,要求相邻的两结点的颜色不一样,问最少需要几种颜色?这就是所谓的结点着色问题.若对的所有边进行着色,要求与同一结点关联的边有不同的颜色,问最少需要多少种颜色?这

16、便是所谓的边着色问题.然而边着色问题可以转换成相应的结点着色问题.其作法是:在每条边上任取一结点,联结相邻两边上的结点得一新边,于是对原图的边着色就转化为由各边选取的结点及新边所构成的图的结点着色.定义9:图,若能用种颜色给的边着色使得相邻的边有不同的颜色,则称图可边着色且着色是正常的.研究图的边着色问题,有它的实际意义.所谓排课表问题,就是个典型的应用实例.例如某所学校有名教师和个班级,已确定教师每周给班级上节课,在教室足够的前提下,问应怎样制定课程表能满足教师、班级、教室资源不冲突,并使上课的节数尽可能少.设,令和为偶图的两个互补结点子集,若给上节课,则在结点与之间连接条平行边,如图1-4

17、所示.显然,同一节课中,一位老师只能教一个班级,而每个班级最多只能由一位老师上课,所以一节课里教师和班级构成了一个匹配,排课问题就是将偶图划分为匹配并使匹配的个数尽可能少,相当于寻找边着色的色数.这里以两个课时为一节课,每天四节,一周五天,故而排课问题中偶图的边色数是20,代表的是20个时间段.因此,如果没有教师教多于20节的课以及没有班级上多于20节的课,那么就可制定20节的课表,也是最多节数的课程表.图1-4 排课问题的偶图第2章 简单排课模型2.1排课的现状分析在学校的教务管理工作中,课程表的编排是一项十分复杂、棘手的工作.排课需要考虑教师、课程、班级和授课时间等因素.经优化的排课,可以

18、在任意一段时间内,教师不冲突,授课不冲突,授课的班级不冲突,教室占用不冲突,且综合衡量全校课表在宏观上是合理的.如何为学校所设置的课程安排出一组适当的教学时间和空间,对稳定教学秩序,提高教学质量有着积极的意义.在国外很早就有人研究课程编排问题,在1962年,Gotlieb曾提出了一个课表问题的数学模型,并利用匈牙利算法解决了三维线性运输问题.然后,人们对课表问题的算法、解的存在性等方面做了许多深入探讨.近40年来,在计算机新技术的基础上,人们又进行了不断地尝试,并取得一些成效.如1965年,Mihoc和Balas将课表公式化为了一个优化问题;Krawczk提出了一种线性编程的方法;Jungin

19、ger将课表问题简化为一个三维运输问题.最近几年,我们在课程编排方面已经取得了一些成绩,但是对于多数学校而言,这种课表编排还不具备实用价值,只能在极为简单的情况下才能实现.然而,人们并没有放弃研究课表问题,进入九十年代以后,国外对课表问题的研究仍然十分活跃.比较有代表的有印度的Vastapur大学管理学院的Arabinda Tripathy、加拿大Montreal大学的Jean Aubin和Jacques Ferland等.我国对课表问题的研究是开始于80年代初期,具有代表性的是南京工学院的UTSS(A University Timetable Scheduling System)系统,清华大

20、学的TISER(Timetable SchedulER)系统,大连理工大学的智能教学组织管理与课程调度等.不管是国外的研究还是国内的研究,从实际使用情况来看,国内外研制开发的软件系统都不是很实用.比如,我国研制的系统大多是模拟手工排课过程的,这种课表编排系统经实践证明是不适合进行大量推广的,因为它过于依赖各个学校的教学体制,限制性较大.另外,排课系统本来就是很复杂的,排课很难做到面面俱到,而且,每个学校都有其特殊性,如果想要改动某个地方,有可能使全部的课程发生大调整,这就是说全校的课程都会发生变动,在实际应用中会发现这是很难实现的.经过长时间的研究,目前解决课表问题的方法有:模拟手工排课法,图

21、论方法,拉格朗日法,二次分配型法等多种方法.2.2排课问题的简化描述排课实际上就是安排每一个教师在具体的时间段到某个具体的班级去上课.这个安排要求满足下面的条件:同一时间每位教师只能到一个班级去上课;一个班级在同一个时间也只能由一位教师来上课.用图论的知识可以来表示这个问题.在一所学校里有名教师和个班级,教师每周要给班级上节课.教师给班级上课就将与相连,如果一周内教师给班级上两次课,则连两条线,以此类推.可以先作一个二部图,其中代表个班级,代表名教师,代表与间连接的边.有相同顶点的边称为相邻边.对每一条边进行着色,一种颜色代表一个课时,通常在大学中两节课为一个课时,每天四课时,一周五天,故而在

22、排课问题中边色数是20,代表的是20个课时,同种颜色的边代表同一个课时.因为在同一时间每位教师只能到一个班级去上课,而一个班级也只能由一位教师来上课,相邻的边代表有共同的教师或学生,不可安排在同一课时同时上课,因此相邻的边不能着相同的颜色.课表的安排就变成了对所有的边进行着色,有相同顶点的边着不同的颜色,而所有颜色的种类不能超过20种.这里有:不考虑教室和教学设备的因素,即认为教室和教学设备总是可以使用的.不考虑合班课、小班课,即某一教师讲课时都有且只有一个班级的学生在听课.不考虑节假日,即放假或补课不算在课表编排中.2.3排课问题的分析排课的目的是为学校所设置的课程安排出一组适当的教学时间和

23、空间.排课系统设计的难点是在排课过程中合理解决教师、教室和班级三者之间的冲突问题.在解决这一问题中,可采用图论中的着色理论.首先用二部图来表示教学要求,即建立教师班级分配图.由于在任何一节课时里,一位教师最多只能教一个班级,并且每个班级最多也只能由一位教师讲课.所以,关于一个课时的教学时间表对应于图中的一个对集,反之,每一个对集对应于在一个课时里教师到班级的一种可能分配.因此,要研究的问题就是把二部图的边划分成与课时数相同的对集,但课时数最少只能是顶点最大度,把的边划分成对集,等价的就是求一个二部图的正常边着色.由于不考虑教室和教学设备的因素,因此每个对集里所含的边的条数就是在这个课时里所需的

24、教室数.2.4排课算法要把二部图的边划分为对集,需要用到匈牙利（Hungarian）算法,该算法是:若中每个结点是饱和的,停止.否则,令是中不饱和结点,作和.若,因为,则,由Hall定理知,不存在使中每个结点都是饱和的匹配,停止.否则,令.若是饱和的,令,作和并转到;否则,令是以为始结点和为终结点的增广链,作并转到.其中,表示中所有边的集合.2.5排课的算法设计设班级教师二部图的二分类为,表示班级,表示教师,有,在中增加一些孤立点成,使.第1步:令是以为二分类划分的正则二部图.第2步:若,则令,转第4步.否则转第3步.第3步:取,使得:,其中,令,转第2步.第4步:任取的一个对集.第5步:若已

25、饱和,转第8步.否则,取中一个不饱和点,作.第6步:在中取一点.第7步:若是饱和的,有使,作,转第6步.否则,存在一条以为始结点,为终结点的增广链,作,转第5步.第8步:若,令,转第4步.第9步:把对集中多余的边去掉.第10步:把对集数扩大到.第11步:把起初对集中的边均匀分配到个对集中.第12步:为每个对集指定一种颜色.注:排课算法拟lingo语言见附录1,C语言程序见附录2.2.6思路流程图得到K个对集去掉多余的边是否得到K个完美对集匈牙利算法扩充虚拟点和边使成为K正则二部图开始由教学任务表建立班级教师二部图G N Y Y 对集数是否大于等于K N Y资源不足,返回出错信息结束给每一个对集

26、分配一种颜色将对集数扩大P,并且均匀对集所含的边第3章 有限制的排课问题在课表编排过程中,除了要保证班级、教师、教室不冲突,满足教室、教师资源的实际约束条件外,对于课时较多的教师,还需要考虑他们的授课意愿,这样才能使课表编排更加合理与人性化.下面就从当某一教师的授课时间和班级固定后,再对其他教师的课程进行安排这一方面来对排课模型进行优化.3.1一位教师的授课时间与班级固定由对集的定义可知:同一个对集中的边互不相同.在第2章中所得到的各个对集所含的边都不相同.由二部图的所有对集构成了学校的周课表,并且每一个对集对应一个课时,对集中的一条边对应一位教师给一个班级授课这一授课关系.因此,学校中的某一

27、位教师所带班级的授课时间固定问题就可以转化为二部图中的对集固定问题.假设教师要对他所带班级的授课时间固定,那么就可以按照2.5的具体算法排出课表,然后找出含有边的对集,根据教师的要求,把边所在的对集对应于给班的授课课时.例如:教师给班级授课,且要求班的课在第1课时,班的课在第3课时,班的课在第5课时,班的课在第10课时,班的课在第12课时,班的课在第15课时.那么就把所在的对集对应于第1课时,所在的对集对应于第3课时,所在的对集对应于第5课时,所在的对集对应于第10课时,所在的对集对应于第12课时,所在的对集对应于第15课时.其它的对集对应于除这些课时以外的课时,这样得到的课程表就是满足教师的

28、要求,即教师的授课时间与班级固定的课表.例3.1:假设一天内有5位教师给6个班级分别代了不同的课,其中表示班级,表示教师,表示教师对班级的授课次数.教师要求对他的授课时间固定,要求班的课在第1课时,班的课在第2课时,班的课在第4课时.请排出一张满足要求的课表.分析 在排课表前首先填写教师定位表,为了直观反映定位情况,可用如下关联矩阵表示(如图3-1所示),然后将关联矩阵表示成二部图(如图3-2所示). 图3-1 图3-2由排课的具体算法找出对集:,.按照要求,教师给班的课在第1课时,班的课在第2课时,班的课在第4课时.那么就把对集对应于课时1,对集对应于课时2,对集对应于课时4,对集对应于剩下

29、的某一课时.由于一天最多有4个课时,故对集对应于课时3.这样便排出了一张有四个课时的课表(如下表3-1所示).表3-1 一张四个课时的课表 课时1 课时2 课时3 课时43.2两位教师的授课时间与班级固定由排课要求知在同一课时,同一班级只能有一位教师讲课.故两位教师的授课时间与班级固定问题必须满足:在同一课时他们不能给同一个班级授课.假设教师要求对他们所带的班级授课时间固定,那么可以先把教师所带班级的课按照要求排在课表内,然后再对其他教师的课进行安排.转化为二部图问题就是把二部图中的边划分为对集,并且这些对集要满足一些固定的边在里面.在二部图中把与结点相关联的边按要求放在不同的对集中,同样把与

30、结点相关联的边按要求放在不同的对集中.若教师的课在同一课时,则把表示他们授课关系的边放在一个对集中,一个对集表示一个课时.这样就先固定了两位教师的课,下面来讨论位教师的课如何安排.首先把二部图中的结点以及与它们相关联的边去掉,根据2.5排课的具体算法对位教师进行排课,得到个对集.把个对集进行分配(分配后的对集数不能超过20).在这些对集中找出不含有结点所在边的对集.其中须找出的对集包括:含有结点所在的边而不含有结点所在边的对集;含有结点所在边而不含有结点所在边的对集;结点所在边与结点所在边都同时不包含的对集.在对个对集进行分配时,由于,故一定可以找出满足上述要求的对集.把个对集分配为20个对集

31、,在分配过程中,考虑教师在同一课时上的不同班级的课,这样就可以保证存在对集使得这一对集中同时不含有结点所在边与结点所在边,这里为教师在同一课时所带的不同班级.然后把只由结点所在边构成的对集,只由结点所在边构成的对集,结点所在边与结点所在边同时构成的对集跟找出的这些对集进行组合,使得最后得到的所有对集数不超过20.把所在的对集对应于要给班的授课课时,其它的对集对应于除这些课时以外的课时,这样就排出了满足两位教师要求的课表.例3.2:假设一天内有5位教师给6个班级分别代了不同的课,其中表示班级,表示教师,表示教师对班级的授课次数.教师要求对他们的授课时间固定:老师要求班的课在第1课时,班的课在第2

32、课时,班的课在第3课时;教师要求班的课在第1课时,班的课在第3课时,班的课在第4课时.请排出一张满足要求的课表.分析 在排课表前首先填写教师定位表,为了直观反映定位情况,可用如下关联矩阵表示(如图3-3所示),将关联矩阵表示成二部图(如图3-4所示). 图3-3 图3-4首先根据教师的要求确定对集:,.去掉结点及与它们相关联的边,然后根据第2章的具体算法得到对集:,.对集与对集可组合成一个对集,对集与对集可组合成一个对集,对集和对集可组合成一个对集.于是得到新的对集:,.按照要求,教师给班的课在第1课时,班的课在第2课时,班的课在第3课时;教师给班的课在第1课时,班的课在第3课时,班的课在第4

33、课时.那么就把对集对应于课时1,对集对应于课时2,对集对应于课时3,对集对应于课时4.这样便排出了一张有四个课时的课表(如下表3-2所示).表3-2 一张四个课时的课表 课时1 课时2 课时3 课时4 结束语本文运用图论中的边着色理论对高校排课问题进行了研究.首先建立简单排课模型,利用匈牙利算法把二部图的边划分为对集,然后给出了排课的具体算法和流程图,并用C语言程序予以实现.然后对有限制的排课问题进行了研究.对于固定一位教师的授课时间和班级进行了简单描述,对固定两位教师的授课时间和班级进行了探索和研究.由于所学知识有限,所建的排课模型对合班课没有很好的考虑,目前还只能实现同一专业班级进行合班的

34、情况,要很好地实现不同专业合班课的安排,在应用图的理论时,把几个班级作为一个授课单位用一个图顶点来考虑,不失为一个好的解决途径,但这只是理论上的思索,还有待于在实践中进行求证.在对多位教师的有限制的排课方面也没有进行更深入的研究.参考文献1 李盘林,李丽双,赵铭伟等.离散数学M.北京:高等教育出版社,2005,(06)2 李雷孝,冯永祥.高校计算机自动排课系统的研究与实现J.内蒙古工业大学学报,2007,(26)3 吴金荣.关于大学课程表问题的研究J.运筹与管理,2002,(6)4 卢开澄.图论及其应用.北京:清华大学出版社,19955 王凤,林杰.高校排课问题的图论模型及算法J.计算机工程及

35、应用,2009,(27)6 张健.基于图论的高校排课系统实现J.重庆师范大学学报（自然科学版）,2005,(01)7 陶华亭,郭玲.用图论方法解决排课冲突问题J.郑州经济管理干部学院学报,2004,(03)8 Bela Bollobas Extremal Graph Theory Academic press, inc (LONDON)LTD 19789 余航.图论应用问题探析J.商场现代化,2008,(18)10 王书荣.自动排课算法的分析J.信息与电脑,2011,(12)11 孙波,钟声.匹配限制着色排课模型J.计算机工程,2008,(02) 谢 辞时光如梭,短暂而有意义的两年大学生活即将

36、结束,此时看着毕业设计摆在面前,我感慨万千.它不仅承载了我这两年来的学习收获,更让我学会了如何求学、如何进行科学研究甚至如何做人.回想起这两年来的学习生活,有太多的人给予我帮助与鼓励,在此我将对我的恩师们,还有所有的同学们表示我的谢意!首先,衷心感谢我的指导老师 对我毕业论文的悉心教诲和指导!在跟随雷老师的这段时间里,我不仅跟雷老师学到了许多专业知识,同时也学习到了雷老师严谨求实、一丝不苟的治学态度和踏踏实实、孜孜不倦的工作精神,它将使我受益终生.在此我对雷老师的教育和指导表示衷心的感谢!其次,我还要感谢数学系的各位老师,在这两年求学生涯中你们给了我很多帮助与教导,从你们身上我学到了很多.最后

37、我要感谢同组的各位同学以及我的各位室友,在毕业论文设计的这段时间里,你们给了我很多的启发,提出了很多宝贵的意见,对于你们的帮助和支持,在此我表示深深的感谢!附 录附录1input: 二部图B=(X,Y,E). Output: 用数组mate表示的B的最大匹配. begin for all xXY do matex:=0; (comment: 初始值)stage: begin for all xX do exposeax:=0; A:=;(comment: 开始构造辅助图（X,A）) for allx,yE do if matey=0 then exposedx:=y else if matey

38、x then A:=A(x,matey); Q:=; for all xX do if matex=0 then Q:=Qx,labelx:=0; while Q do begin 令x是Q中一个结点; 从Q中去掉x; if exposedx0 then augment(x), go to stage; else for all 未标号的x1使得(x,x1)A do labelx1:=x, Q:=Qx1;endendendProcedure augment(x)if labelx=0 then matex:=exposedx,mateexposedx:=x;else beginexposedl

39、abelx:=matex;matex:=exposedx;mateexposedx:=x;augment (labelx)end附录2# include # define N# define Mmain() int VN+M /顶点集 int adjN+M N+M; N表示V1的顶点数,M表示V2的顶点数 int exposedN=0; int AN M=0; int labelN; int mateN+M; int exposedN; for (i=0; iN, i+)for (j=N; jM, j+) if (adji j=!0) if (matej=0 exposedi=j; if (m

40、atej!=i); int quartN=0; for (i=0; iN, i+) if (matei=0) quart0=i; labeli=0; bleak; for (i=0; iN, i+) if (quartj!=0 if (exposedquarti!=0) argument (quarti; label ; mate ; exposed ) ; go to stage; else for (j=0; jN, j+) if (Ai j=1); labelj=i; j=j+; quartj=i; argument (int x, int label ; int mate , int exposed ) if (labelx=0) mateexposedx=x; else exposed labelx=matex; matex=exposedx; mateexposedx=x; argumentlabelx, label , mate , exposed ;