华南理工大学《离散数学》课件-第6章欧拉图

1、离散数学及其应用华南理工大学计算机科学与工程学院欧拉图欧拉图哥尼斯堡七桥问题。Leonhard Euler欧拉图定义：设 G=（V，E）是无向图或有向图，若G中有一条包含所 有边（有向边）的简单回路，称该回路为欧欧拉回拉回路路，称图G为欧拉欧拉 图图。若G中有一条包含G中所有边（有向边）的简单通路，称它为欧欧 拉通路拉通路，称图G为半欧拉图半欧拉图。规定平凡图是欧拉图。起点终点起点终点欧拉图的判断定定理理1 无向连通图G是欧拉图，当且仅当G的所有结点的度数都是偶 数。证明：（必要性）设G是欧拉图，图G有欧拉回路 C： v1 e1 v2 e2 v3 ek v1 。设vi 是图G 的任一结点， v

2、i 在欧拉回路C每出现1次，关联两条边，获得2度，若出 现 k 次就获得 2k 度。所以，欧拉图的所有结点的度数都是偶数。vid(vi)=2 +2欧拉图的判断定理1证明（续）（充分性）假设G中所有结点的度数都是偶数。从G中的任一结点v1 开始，经过任一和v1关联的边e1到另一结点v2，再经过另一 和v2关联的边e2到另一结点v3，依此类推，可以得到一条 包含G的边的简单回路C1：v1 e1 v2 e2 v3 em v1。若C1=G，则G为欧拉图，否则删除回路C1得到图G的子图G1 ，G1的所有结点的度数都是偶数。因为G是连通的，所以G1和删去的回路C1至少有一个公 共结点。设这个公共结点是vp

3、。在G1也可以找到一个从vp开212始的简单回路C 。将C 和C 可合并成一个简单回路。C1vpGvpC2重复前面的过程，直到用完图G中的所有边，可以得出 一条包含G的所有边的简单回路，就是图G的欧拉回路。G1G欧拉图的判断格尼斯堡七桥问题：欧拉图的判断定理定理2 连通无向图G为半欧拉图，当且仅当G中只有两个奇度数的结点,其余结点的度数都是偶数。 证明 （必要性）设 G 是半欧拉图，图 G 有欧拉通路 L： v0 e1 v1 e2 v2 em vm 。若结点v丌是欧拉通路L的端点， v在L上每出现1次，获得2度，若出现k次就获得2k度。若结点v是欧拉通路L的端点，由于两个端点是丌同的而且丌相邻

4、，v作为端点只能出现1次，获得1度，它还可能作为非端点在通路 上出现多次，每次获得2度，因此端点v的度数是奇数。所以，半欧拉图有 两个结点度数是奇数，其余结点的度数都是偶数。1122欧拉图的判断证明 （充分性）若连通无向图G只有两个奇度数结点，在这两个奇度数的结点之 间加一条边e得到图G，则图G的所有结点的度数都是偶数，有欧拉 回路。在G的欧拉回路中删去这条边e，则可得到一条包含G中所有 边的欧拉通路。因此图G是半欧拉图。欧拉图的判断终点终点例：在下图中，哪些是欧拉图？哪些是半欧拉图？起点起点起点终点欧拉有向图定义：如果连通有向图G中有一条包含G中所有有向边的有向回 路，称它为欧拉有向回路，称

5、图G为欧拉欧拉有有向图向图。如果连通有向图G中有一条包含G中所有有向边的有向通路，称它为欧拉有向通路，称图G为半欧拉有向半欧拉有向图图。abcdabcdabcd起点终点起点终点欧拉有向图的判断定理定理3 连通有向图G是欧拉图，当且仅当G中每个结点v的入度等 于它的出度。定定理理4 连通有向图G是半欧拉图，当且仅当G中有且仅有两个奇 度数结点，其中一个结点的入度比出度大1，另一个结点的入度比出 度小1,其余结点的入度和出度相等。证明（略）入度=出度入度=出度入度=出度入度 - 出度=1出度 -入度=1欧拉有向图的判断入度 - 出度=2入度=出度入度=出度例例 判断下列图是否欧拉有向图？是否半欧拉

6、有向图？出度 -入度=2出度 -入度=1入度 - 出度=1欧拉图定理定理5：G是非平凡的欧拉图当且仅当G是连通的且是若干个边丌重的回 路的并。欧拉图是能一笔画出的图。一个图能一笔画出是指从图的某一点出发， 丌间断地画完整个图，最后回到起点。计算机科学与工程学院离散数学及其应用华南理工大学计算机科学与工程学院哈密顿图哈密顿图环游世界问题哈密顿图定义：设图G=（V，E）是无向图或有向图。若G中有一条包含G 的所有结点(仅一次)的回路，称该回路为哈哈密密顿回顿回路路，称图G为哈密哈密 顿图顿图。若图G有一条包含G的所有结点的通路，称该通路为哈哈密密顿通顿通 路路，称图G为半哈密顿半哈密顿图图。哈密顿

7、图定理1： 设无向图G = (V，E) 是哈密顿图，则对于结点集V的每一个真 子集 S 均有：W(G-S) |S|, 其中，W(G-S) 是G-S 的导出子图的连通分支数。v1 v2v2 和v1不邻接v1v2v2 和v1邻接v1v2CG哈密顿图定理1： 设无向图G = (V，E) 是哈密顿图，则对于结点集V的每一个真 子集 S 均有：W(G-S) |S|, 其中，W(G-S) 是G-S 的导出子图的连通分支数。W(C- S) |S|v1v2W(G- v1- v2)=1W(G- S) W(C- S) |S|v2 和v1不邻接v1v2W(C- v1- v2)=2v2 和v1邻接v1v2CW(C-

8、v1- v2)=1G哈密顿图定理1证明证明：设C为G中的一条哈密尔顿回路。对于V的任何一个非空子集S， 在C中删去S中任一结点v1，则C- v1是连通的非回路。若再删去任一结点v2， 分两种情况讨论：如 v2 和v1邻接，则C- v1- v2是连通的， W(C- v1- v2)= 1； 如 v2 和v1丌邻接，则C- v1- v2是丌连通的，W(C- v1- v2)= 2。所以，删去两 个结点时有W(C- v1- v2) 2。依此类推，显然有W(C-S)|S| 。又因为C是G的生成子图，所以C-S是G-S的生成子图，因而W(G-S)W(C-S)。因此有W(G-S)|S|。哈密顿图例例 说明下图

9、 所示的无向图G丌是哈密顿图。解解 在图中删去结点集S=v2，v4，v6，v8，W(GS)=5，丌满足W(G-S)|S|。所以G丌是哈密顿图。v1v9v5v7v3v4v6v8v1v9v5v7v3v2哈密顿图910267845S=1 W(GS)=1 |S|3定理1是哈密顿图存在的必要条件。例如：彼德森图中对于结点集V的每一个真子集S均有：W(G-S)|S|，但彼德森图丌是哈密顿图。1191067845S=2 W(GS)=1 |S|3彼德森图哈密顿图10267845S=1 W(GS)=1 |S|S=1,9 W(GS)=1 |S|3定理1是哈密顿图存在的必要条件。例如：彼德森图中对于结点集V的每一个

10、真子集S均有：W(G-S)|S|，但彼德森图丌是哈密顿图。1191067845S=2 W(GS)=1 |S|S=2,3 W(GS)=1 |S|彼德森图哈密顿图1026783定理1是哈密顿图存在的必要条件。例如：彼德森图中对于结点集V的每一个真子集S均有：W(G-S)|S|，但彼德森图丌是哈密顿图。119678彼德森图45S=1 W(GS)=1 |S|S=1,9 W(GS)=1 |S|S=1,9,10 W(GS)=2 |S|45S=2 W(GS)=1 |S|S=2,3 W(GS)=1 |S|S=2,3,10 W(GS)=1 |S|哈密顿图26783定理1是哈密顿图存在的必要条件。例如：彼德森图中

11、对于结点集V的每一个真子集S均有：W(G-S)|S|，但彼德森图丌是哈密顿图。11678彼德森图45S=1 W(GS)=1 |S|S=1,9 W(GS)=1 |S|S=1,9,10 W(GS)=2 |S|45S=2 W(GS)=1 |S|S=2,3 W(GS)=1 |S|S=2,3,10 W(GS)=1 |S|S=2,3,9,10W(GS)=3 |S|哈密顿图哈密顿通路存在的充分条件定理定理 2 如果图G是有 n个结点的简单无向图，对于每一对丌邻接结 点u和v，满足d(u)+d(v) n-1，那么图G中存在哈密顿通路，图G是半 哈密顿图。推推论论1 如果图G是有 n个结点的简单无向图，对于每一

12、对丌邻接结 点u和v，满足d(u) + d(v) n，那么G中存在哈密顿回路，图G是哈密 顿图。推推论论2 如果G是有 n个结点的简单无向图，G中每个结点的度数都 至少为n/2，那么图G是哈密顿图。哈密顿图如：n 5的Cn图都是哈密顿图，但丌满足推论1和推论2.哈密顿图例例有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、意大利 语和俄语, D会讲日语和汉语, E会讲德语和意大利语, F会讲法语、日 语和俄语, G会讲法语和德语. 问能否将他们沿圆桌安排就坐成一圈, 使得每个人都能不两旁的人交谈?哈密顿图每个人用一个结点表示，两个人会讲同一种语言，则在对应的结 点连接一条边，得到图G。

13、图G的一条哈密顿回路是ABDFGECA，按这条哈密顿回路安排就坐成一圈, 每个人都能不两旁的人交谈。图G坐位安排图ABCDEFG旅行商问题旅行商问题(Travelling Salesman Problem, TSP )一个商品推销员要去一些城市推销商品，该推销员从一个 城市出发，需要经过所有城市后，回到出发地。应如何选择行 进路线，以使总的行程最短。https:/ Salesman Problem, TSP )从图论的角度来看，该问题实质是在一个带权完全无向 图中，找一个权值最小的哈密顿回路。解决方法：n个结点的图上，以每个结点为起点的所有的 哈密顿回路共有(n-1)! 条，计算(n-1)!/

14、2条回路的权值， 找出最小权的哈密顿回路。旅行商问题图G的哈密顿回路：计算机科学与工程学院离散数学及其应用华南理工大学计算机科学与工程学院最短路径问题最短路径问题 无向简单连通图的边或结点带有信息的图称为带带权图权图。 在一个无向简单连通边带权图G=（V，E，W）中，从u到v的一条通路中包含的各条边的权值之和称为这条通通路的路的长度长度。 从u到v的所有通路中长度最短的通路称为u到v的最短最短路径路径。 求给定两结点之间的长度最短的通路问题称为最最短短路径路径问题问题.uvabcd2233211uadv是u到v的最短路径Dijkstra算法Dijkstra（迪杰斯特拉）算法是求最短路径算法，用

15、于计算权值非 负的图的一个结点到其他所有结点的最短路径。算法思想：把图G(V，E)中结点集合V分成两组，第一组为已求出最短路径的结点集合S，第二组为其余未确定最短路径的结点集合T；初始时S中只有一个源结点，按最短路径长度的递增次序依次把集合T的结点加入集合S中。每个结点对应一个距离，S中的结点的距离就是从u到此结点的最 短路径长度；T中的结点的距离，是从u到此结点只包括S中的结点 为中间结点的当前最短路径长度。Dijkstra算法设带权图G(V,E,W）和结点u，其中每条边e的权W(e)为非负实数，求结 点u到其它结点的最短路径长度:1. 初始化结点距离值L(vi), viV。除L(u)初始化

16、为0，其它所有结点 L(vi)=+，S=u,T=V-u。2. 修改和结点u相邻的结点vi的距离值：L(vi)= W(u,vi)，更新T中的结点 距离值L 。3. 将T中具有最小L值的结点记为t，从集合T中删除t，添加t到集合S中， 即S = St， T=T-t 。4.修改T中和结点t相邻的结点vi的L值：L(vi)=minL(vi), L(t)+W(t,vi)。5.重复步骤3和4直到所有结点都被添加到集合S中。Dijkstra算法求结点a到其它结点的最短路径长度a6421581023bdcefDijkstra算法求结点a到其它结点的最短路径长度ba64215810230dcefDijkstra

17、算法求结点a到其它结点的最短路径长度S=a T=b,c,d,e,fb64215810230dcefaDijkstra算法求结点a到其它结点的最短路径长度42S=a T=b,c,d,e,fb64215810230dcefaDijkstra算法求结点a到其它结点的最短路径长度42S=a,c T=b,d,e,fb64215810230defacDijkstra算法求结点a到其它结点的最短路径长度42S=a,c T=b,d,e,fb64215810230defacDijkstra算法求结点a到其它结点的最短路径长度2S=a,c T=b,d,e,f3b64215810230defacDijkstra算法

18、求结点a到其它结点的最短路径长度2S=a,c T=b,d,e,f3b64215810230defacDijkstra算法求结点a到其它结点的最短路径长度2S=a,c T=b,d,e,f3b6421581023010defacDijkstra算法求结点a到其它结点的最短路径长度2S=a,c T=b,d,e,f3b6421581023010de12facDijkstra算法求结点a到其它结点的最短路径长度2S=a,c,b T=d,e,f6421581023010de12fac3bDijkstra算法求结点a到其它结点的最短路径长度2S=a,c,b T=d,e,f6421581023010de12f

19、ac3bDijkstra算法求结点a到其它结点的最短路径长度2S=a,c,b T=d,e,f64215810230d8e12fac3bDijkstra算法求结点a到其它结点的最短路径长度2S=a,c,b,d T=e,f64215810230e12fac3bd8Dijkstra算法求结点a到其它结点的最短路径长度2S=a,c,b,d T=e,f621581023e12f100a4c3bd8Dijkstra算法求结点a到其它结点的最短路径长度2S=a,c,b,d T=e,f621581023e12f100a4c3bd8Dijkstra算法求结点a到其它结点的最短路径长度2S=a,c,b,d,f T

20、=e621581023e120a4c3bd8f10Dijkstra算法求结点a到其它结点的最短路径长度2S=a,c,b,d,f T=e621581023e120a4c3bd8f10Dijkstra算法求结点a到其它结点的最短路径长度2S=a,c,b,d,f,e T= 6215810230a4c3bd8f10e12Dijkstra算法求结点a到其它结点的最短路径长度结点a到其它结点的最短路径长度2S=a,c,b,d,f,e T= 6215810230a4c3bd8f10abcdefa03281210e12计算机科学与工程学院离散数学及其应用离散数学及其应用华南理工大学计算机科学与工程学院中国邮路

21、问题离散数学及其应用中国邮路问题 一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道， 送完邮件后又返回邮局如果他必须至少一次走过他负责范围内的 每一条街道，如何选择投递路线，邮递员可以走尽可能少的路程？ 这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授） 在1962年首次提出的，因此在国际上称之为中国邮路问题 从图论的角度看，这个问题是在一个连通的边带权图G=（V，E，W） 中，寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的总权值最小，也就是说要从包含G的每条边的回路中找一条总 权值最小的回路。离散数学及其应用中国邮路问题如果G是欧拉图，只要求出图G的一条欧拉回路

22、即可。问题：在有奇度数结点的连通带权图中，在包含G中每条边至少 一次的回路中找一条总权值最小的回路。33553324欧拉图奇度数 结点离散数学及其应用中国邮路问题G图G有4个奇度数结点：b、h、d、f离散数学及其应用中国邮路问题GW(E1)=6W(E1)=9b与h，d与f 配对：b与d，h与f 配对：图G有4个奇度数结点：b、h、d、fG1W(E1)=12b与f，d与h配对：离散数学及其应用中国邮路问题首先注意到，若图G有奇度数结点，则G的奇度数结点必是偶数个 把奇数度结点配为若干对，每对结点之间在G中有相应的最短路，将这些最短路画在一起构成一个附加的边子集E1令G1 =G+E1，即把附加边子

23、 集 E1叠加在原图G上形成一个多重图G1 ，这时G1中没有奇度数结点显然 G1是一个欧拉图，因而可以求出G1的欧拉回路该欧拉回路不仅通过原图 G中每条边，同时还通过 E1中的每条边，且均仅一次邮递员问题的难点在于当G的奇数度节点较多时，可能有很多种配对方 法，应怎样选择配对，能使相应的附加边子集E1 的权值W(E1)为最小。离散数学及其应用中国邮路问题定理定理1 设G（V，E，W）为一个连通的带权图，则使附加边子集 E1 的权值W(E1)为最小的充分必要条件是G+ E1 中任意边至多重复一 次，且G+ E1 中的任意回路中重复边的权值之和不大于该回路总权 值的一半。证明证明 （略）（略）离散

24、数学及其应用中国邮路问题例：已知快递员要投递的街道图，求最优投递路线。离散数学及其应用中国邮路问题1. 先找出奇结点；2.对奇结点迚行配对，找到每对结点间的最短通路，给每条通路所含的边 加一条平行边；离散数学及其应用中国邮路问题1. 先找出奇结点；2.对奇结点迚行配对，找到每对结点间的最短通路，给每条通路所含的边 加一条平行边；离散数学及其应用中国邮路问题1. 先找出奇结点；2.对奇结点迚行配对，找到每对结点间的最短通路，给每条通路所含的边 加一条平行边；离散数学及其应用中国邮路问题3、当某条边添加的平行边大于等于2条时，将添加的平行边都删去；离散数学及其应用中国邮路问题3、当某条边添加的平行

25、边大于等于2条时，将添加的平行边都删去；离散数学及其应用中国邮路问题3、当某条边添加的平行边大于等于2条时，将添加的平行边都删去；离散数学及其应用中国邮路问题3、当某条边添加的平行边大于等于2条时，将添加的平行边都删去；4、检查每一条回路，若一条回路中重复边的权值和大于该回路权值的一半，把该回路的重复边删去，在没有平行边的边上加上平行边；离散数学及其应用中国邮路问题3、当某条边添加的平行边大于等于2条时，将添加的平行边都删去；4、检查每一条回路，若一条回路中重复边的权值和大于该回路权值的一半，把该回路的重复边删去，在没有平行边的边上加上平行边；离散数学及其应用中国邮路问题3、当某条边添加的平行

26、边大于等于2条时，将添加的平行边都删去；4、检查每一条回路，若一条回路中重复边的权值和大于该回路权值的一半，把该回路的重复边删去，在没有平行边的边上加上平行边；离散数学及其应用中国邮路问题3、当某条边添加的平行边大于等于2条时，将添加的平行边都删去；4、检查每一条回路，若一条回路中重复边的权值和大于该回路权值的一半，把该回路的重复边删去，在没有平行边的边上加上平行边；离散数学及其应用中国邮路问题3、当某条边添加的平行边大于等于2条时，将添加的平行边都删去；4、检查每一条回路，若一条回路中重复边的权值和大于该回路权值的一半，把该回路的重复边删去，在没有平行边的边上加上平行边；离散数学及其应用中国

27、邮路问题5、若没有任何回路的重复边的权值之和大于该回路权值的一半，图中 的任意一条欧拉回路就是最优邮路最优投递路线离散数学及其应用计算机科学与工程学院离散数学及其应用华南理工大学计算机科学与工程学院匹配和二分图匹配定义定义1 在图G=(V，E)中, 若ME, 且M中任意两条边都丌相邻，则称M为G的一个匹配匹配。匹配定义定义1 在图G=(V，E)中, 若ME, 且M中任意两条边都丌相邻，则称M为G的一个匹配匹配。若在M中再加入任意其它的边e，Me有相邻的边，则称M为G 的极大匹配极大匹配。匹配定义定义1 在图G=(V，E)中, 若ME, 且M中任意两条边都丌相邻，则称M为G的一个匹配匹配。若在M

28、中再加入任意其它的边e，Me有相邻的边，则称M为G 的极大匹配极大匹配。若G中丌存在匹配M1，使得|M1| | M|，则称M为G的最最大大匹匹配配。匹配定定义义2 若M是G的一个匹配，M的边和结点v关联，则称v为M饱和饱和点点，否则称v为M非饱和点非饱和点。若G=（V，E）的每个结点都是M饱和点，则称M为G的一个完美完美匹匹配配。饱和点非饱和点M交错路和M可扩充路定义定义3 若M是G=（V，E）的一个匹配，从G中的一个结点到另一 个结点存在一条由属于M的边和丌属于M的边交替出现组成的简单 路，则称这条简单路为M交错交错路路。M=e1,e7是匹配 e1e4e7e8是M交错路M交错路和M可扩充路定

29、义定义3 若M是G=（V，E）的一个匹配，从G中的一个结点到另一 个结点存在一条由属于M的边和丌属于M的边交替出现组成的简单 路，则称这条简单路为M交错交错路路。若M交错路的两端点为M非饱和点时，称这条M交错路是M可扩可扩充路充路。非饱和点非饱和点M=e1,e7是匹配e1e4e7e8是M交错路 e2e1e4e7e8是M可扩充路M交错路和M可扩充路定义定义3 若M是G=（V，E）的一个匹配，从G中的一个结点到另一 个结点存在一条由属于M的边和丌属于M的边交替出现组成的简单 路，则称这条简单路为M交错交错路路。若M交错路的两端点为M非饱和点时，称这条M交错路是M可扩可扩充路充路。非饱和点非饱和点M

30、=e1,e7是匹配e1e4e7e8是M交错路 e2e1e4e7e8是M可扩充路M1=e2,e4,e8是匹配,|M1|M|最大匹配的充分必要条件定理定理1 M是图G=(V，E)的最大匹配的充分必要条件是G中丌存在M可扩充路。M1 =e2,e4,e8是最大匹配二分图定义定义4 如果图G =(V, E)的结点集 V 能划分成两个子集V1和V2，使 得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为 二分（部）图二分（部）图，V1和V2称为互补互补结结点点集集，二分图通常记为G=（V1， V2，E）。二分图注意：n(n2)阶零图是二分图。V1=u1,u2,u3，V2 =v1,v2,v3,

31、v4V1V2二分图定定义义5 若V1中每一结点不V2中每一个结点均有且仅有一条边相关 联，则称二分图G为完全二分图完全二分图。若| V1|=m ， | V2|=n ，则记完全二 分图G为Km，n。K2,3K3,3二分图的判断定理定理2 一个无向简单图G=（V，E）是二分图，当且仅当G中无 奇数长度的回路。例例 判断下面各图是否是二分图。abcdfe答：都是二分图完备匹配和完美匹配(1)完备匹配(2)完美匹配V2 =v1,v2,v3,v4定定义义5 设G=（V，E）是二分图，V1和V2是G的互补结点集，若G的 一个匹配M使得|M|=min| V1|，| V2|，称匹配M是G的完备完备匹匹配配。这

32、时， 若| V1| V2|，称M是从V1到V2的一个完备匹配。如果| V1|=| V2|，称M是 G的完美匹完美匹配配。V1=u1,u2,u3V1=u1,u2,u3V2 =v1,v2,v3完备匹配定理定理3（Hall定理）定理） 设二分图G = (V,E )，V1和V2 是G的互补结点集， 存在从V1到V2的完备匹配，当且仅当对于V1中的任意k个结点（k=1,2,|V1|）至少邻接V2的k个结点。定理3中的条件通常称为相异性条件相异性条件。完备匹配不存在完备匹配V1=u1,u2,u3V2 =v1,v2,v3,v4V1=u1,u2,u3V2 =v1,v2,v3,v4完备匹配定理定理4 设G=（V

33、，E）是二分图，V1和V2 是G的互补结点集。若存在正整数t，使1V1中的每个结点至少关联t条边，2V2中的每个结点至多关联t条边， 则G中存在从V1到V2的完备匹配。证明证明 由条件（1）可知，V1中的k个结点至少关联kt条边（1k|V1|）。由条 件（2）可知，这些边至少关联V2中的k个结点。因此，V1中的k个结点至少邻接 V2中的k个结点。由定理3，G中存在完备匹配。V1的最小度=2 V2的最大度=2完备匹配完备匹配定理4的条件常称为t条件，是判断二分图存在完备匹配的充分条 件，丌是必要条件。V1的最小度=2V2的最大度=3完备匹配例题要分派5位教师A，B，C，D，E去上课。A可以上课的

34、时间是星期 二和星期三，B的时间是星期一和星期三，C的时间是星期四，和星 期五，D的时间是星期二和星期五，E的时间是星期一和星期四。应 如何排课才可以使每天都只有一位教师上课？例题要分派5位教师A，B，C，D，E去上课。A可以上课的时间是星期 二和星期三，B的时间是星期一和星期三，C的时间是星期四，和星 期五，D的时间是星期二和星期五，E的时间是星期一和星期四。应 如何排课才可以使每天都只有一位教师上课？解：令V1=A，B，C，D，E，V2=d1，d2，d3，d4，d5，d1，d2，d3，d4，d5分别表示星期一到星期五例题要分派5位教师A，B，C，D，E去上课。A可以上课的时间是星期 二和星

35、期三，B的时间是星期一和星期三，C的时间是星期四，和星 期五，D的时间是星期二和星期五，E的时间是星期一和星期四。应 如何排课才可以使每天都只有一位教师上课？解：令V1=A，B，C，D，E，V2=d1，d2，d3，d4，d5，d1，d2，d3，d4，d5分别表示星期一到星期五二分图：教师可以上课的时间安排例题要分派5位教师A，B，C，D，E去上课。A可以上课的时间是星期 二和星期三，B的时间是星期一和星期三，C的时间是星期四，和星 期五，D的时间是星期二和星期五，E的时间是星期一和星期四。应 如何排课才可以使每天都只有一位教师上课？解：令V1=A，B，C，D，E，V2=d1，d2，d3，d4，

36、d5，d1，d2，d3，d4，d5分别表示星期一到星期五二分图：教师可以上课的时间安排完备匹配： M=(A,d2),(B,d3),(C, d4),(D,d5),(E,d1)按完备匹配M排课可以使每天都只有一位教师上课。计算机科学与工程学院离散数学及其应用平面图华南理工大学计算机科学与工程学院平面图定义定义 设G=（V，E）是一个无向图，如果能把G画在平面上，使 得除结点处外，任意两条边都不相交，则称G为平平面面图图。平平面面图图（4）（5）（6）（1）（2）（4）是平面图，(3) （5）（6）不是平面图。（1）（2）（3）平面图定义：如果能把图G画在平面上，使得除结点外，边和边都不相 交，称图

37、G是可平面图。K4平面图定义 将一个平面图G，画成除结点处外，任意两条边都不相交 的和它同构的图，称这样的图为图G的平平面面嵌嵌入入。G1G1的平面嵌入G2G2的平面嵌入平面图平面图定义 若非平面图G任意删除一条边后，所得之图都是平面图，则称G为极小非平面图。(1)极小非平面图(2)平面图删去一条边极小非平面图极小非平面图极小非平面图平面图定义 设G为简单平面图，若在G的任意不相邻的结点u、v之间加 边（u，v）后，所得图是非平面图，则称G是极大平面图。极大平面图K1, K2, K3, K4都是极大平面图平面图定义定义 设G是一个平面嵌入，G的边将G所在的平面划分成若干个 区域，每个区域称为G

38、的一个面面。面积无限的区域称为无无限面限面或外外 部面部面，记成f0，面积有限的区域称为有限面有限面或内内部部面面，记为f1，f2， fk 。f1f2f3v1v2v3v4f0v5v6有限面平面图定义包围每个面的所有边所构成的回路称为该面面的边的边界界。一个面的边界包含的边数称为该面的次面的次数数，记为deg(f)。f0 的 边 界 : v6e8v5e7v4e5v2e6v2e3v1e1v3e2v4e7v5e8v6 Deg(f0)=9f1的边界:v2e1v2 Deg(f1)=1f2的边界:v2e3v1e6v3e4v2 Deg(f2)=3f3的边界:v2e2v4e5v3e4v2 Deg(f3)=3平

39、面图定定理理1 一个连通平面图G的边数为m，G的边将G所在的平面划分证明证明 对图G的每一条边e，若e在两个面的公共边界上，则在计算这 两个面的次数时，e各提供1. 当e只在一个面的边界上出现时，它必在 一个面的边界上出现2次，因而在计算这个面的次数时，e提供2. 因此 所有面的次数之和等于边数m的2倍。f成 f 个面，所有面的次数之和等于边数m的2倍，即deg( fi ) 2mi0平面图定理定理2 设G为任意的连通的平面图，G中有n个结点，m条边，f个 面，则有公式n-m+f=2 成立。该公式称为欧拉公式欧拉公式。证明证明 用归纳法证明。（对边数m归纳。）（略）平面图例例 假定连通平面图G有

40、30条边，若G的边把图分成20个区域，则 这个图有多少个结点？解解 将连通平面图G的边数m=30，面数f=20，代入欧拉公式n-m+f=2 得：n=2+m-f=2+30-20=12所以这个图有12个结点。欧拉公式的推论推论推论1 设G是有n （n 3）个结点，m条边，f个面的简单连通平面 图，边数m 3n-6。证明证明 当n=3，3个结点的简单连通平面图的边数m3, 因此m 3n-6成立。当n 3时，G的每个面至少由3条边围成，即每个面的次数deg(fi)3, 所以所有面的总度数i deg(fi)3f。而i deg(fi)=2m , 因而有2m 3f, 即f 2m/3。代入欧拉公式 2= n-

41、m+f n-m+2m/3 有 m 3n-6成立。因此m 3n-6成立。欧拉公式的推论推论推论2 设G是有n（n 3）个结点，m条边，f个面的简单连通平面 图，若每个面由4条或4条以上的边围成, 则m 2n- 4。推论推论3 K5和K3,3 都不是平面图。证明证明： K5 : n=5, m=10, 不满足推论1K3,3 : n=6, m=9, 不满足推论2注意：欧拉公式和推论1、推论2是平面图的必要条件欧拉公式的推广定理定理3 （欧拉公式的推广）设G为任意的平面图，G有k个连通分 支，n个结点，m条边，f个面，则有公式n-m+f=k+1成立。平面图定定义义 设m=（u，v）是图G的一条边，在G中

42、删去边m，增加新的结点w，使u，v均与w相邻，则称在图G中插插入入2度结点度结点w；设w为G的一个度数为2的结点，w与u，v相邻，删去w及与w相关联的边(w，u)，(w，v)，同时增加新边(u，v )，则称在图G中删去删去2度结度结点点w。ww插入2度结点删除2度结点平面图定义定义 若两个图G1和G2同构或通过反复插入或删除2度结点后是同 构的，则称G1和G2是同胚同胚的。12637891045（1）G1（2）G2平面图的充分必要条件定理定理5（ 库拉托斯基定理） 设G是无向图，则G是平面图的充分 必要条件是图G不含和K5或K3,3同胚的子图。推论推论 设G是无向图，则G是平面图的充分必要条件

43、是图G没有可收缩为K5或K3,3的子图。平面图1637891045例：彼得森图不是平面图。132542610978彼得森图 G12637891045G的子图和K3,3图同胚的图计算机科学与工程学院离散数学及其应用华南理工大学计算机科学与工程学院对偶图和图的着色对偶图与图的着色定定义义 设G是平面图。在图G的每个面中指定一个新结点，对两个 面公共的边，指定一条新边与其相交。由这些新结点和新边组成的图 称为G的对偶图对偶图G*。图G对偶图与图的着色定定义义 设G是平面图。在图G的每个面中指定一个新结点，对两个 面公共的边，指定一条新边与其相交。由这些新结点和新边组成的图 称为G的对偶图对偶图G*。图G对偶图与图的着色定定义义 设G是平面图。在图G的每个面中指定一个新结点，对两个 面公共的边，指定一条新边与其相交。由这些新结点和新边组成的图 称为G的对偶图对偶图G*。图G对偶图与图的着色定定义义 设G是平面图。在图G的每个面中指定一个新结点，对两个 面公共的边，指定一条新边与其相交。由这些新结点和新边组成的图 称为G的对偶图对偶图G*。图GG的对偶图G*设平面图G的结点数n、边数e和面数f，G的对偶图G*的结点数n*、