第八章一些特殊的图资料课件

2024/7/14离散数学1第八章第八章 一些特殊的图一些特殊的图内容导读内容导读:二部图二部图欧拉图欧拉图哈密顿图哈密顿图平面图平面图难点难点:各种图的判别定理各种图的判别定理2024/7/14离散数学2 A AB BC CD D2024/7/14离散数学3(1)(2)设无向图设无向图G=有两个有两个V的子集的子集V1,V2,它们具有满足：它们具有满足：V1V2=VV1V2=图图G中的每一边中的每一边e均具有均具有e=(vi,vj)其中：其中：viV1,vjV2则称则称G是一个是一个二部图二部图，2024/7/14离散数学4定义定义8.1若一个图若一个图G的结点集的结点集V能划分为两个子能划分为两个子集集V1和和V2，使得使得G的每一条边的每一条边vi,vj满足满足viV1,vjV2,则称则称G是一个是一个二部图二部图，V1和和V2称为称为G的的互补结点子集。此时可将互补结点子集。此时可将G记成记成G=若若V1中任一结点与中任一结点与V2中每一结点均有边相连中每一结点均有边相连接接,则称二部图为则称二部图为完全二部图完全二部图。若。若|V1|=n,|V2|=m则记完全二部图则记完全二部图G为为Kn,m。(1)(2)K2,3K3,32024/7/14离散数学5(1)(2)例例8.1判断下列图是否是二部图？判断下列图是否是二部图？v1v3v5v2v4v6v1v4v8v5v2v3v6v7v1v2v3v4v5(3)在图在图(1)中中,V1=v1,v3,v5,V2=v2,v4,v6,是一个是一个完全二部图。在图完全二部图。在图(2)中中,V1=v1,v4,v8,v5,V2=v2,v3,v7,v6,是一个二部图。在图是一个二部图。在图(3)中中,对于对于其中的顶点无法将它们分到两个不同的子集其中的顶点无法将它们分到两个不同的子集V1和和V2,使其边能满足二部图的定义使其边能满足二部图的定义,所以它不是二部图。所以它不是二部图。二部图是不是一定是连通图?2024/7/14离散数学6(4)(5)定理定理8.1一个无向图一个无向图G=是二部图是二部图当且当且仅当仅当G中无奇数长度的回路。中无奇数长度的回路。下图所示前下图所示前3个图中个图中,均无奇数长度的回路均无奇数长度的回路,所以它们都是二部图所以它们都是二部图,其中图其中图(2)所示为所示为K2,3,图图(3)所示为所示为K3,3,它们分别与图它们分别与图(4)和和(5)同构同构。(1)(2)(3)2024/7/14离散数学7(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在图在图(1)中，中，e1,e1,e7,e5,e4,e6等都是图等都是图中的匹配。中的匹配。在图在图(2)中找出匹配。中找出匹配。定义定义8.2设设G=为无向图为无向图,E*E,若若E*中任意两中任意两条边均不相邻条边均不相邻,则子集则子集E*称为称为G中的中的匹配匹配(或或边边独立集独立集),并把并把E*中的边所关联的两个结点称为中的边所关联的两个结点称为在在E*下是匹配的。下是匹配的。2024/7/14离散数学8(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在图在图(1)中中,e5,e1,e7,e4,e6e3,e7,e2,e6是极大匹配是极大匹配，后后4个是最大匹配，匹配数个是最大匹配，匹配数 1=2。若在若在E*中再加入任何一条边就都不是匹配了中再加入任何一条边就都不是匹配了,则称则称E*为为极大匹配极大匹配。边数最多的极大匹配称为。边数最多的极大匹配称为最大匹配最大匹配，最大匹配中的元素，最大匹配中的元素(边边)的个数称为的个数称为G的的匹配数匹配数，记为，记为 1(G),简记为简记为 1。2024/7/14离散数学9(2)e1e2e3e4e5e6e7在图在图(2)中中,e2,e5,e3,e6,e1,e7,e4都是极大都是极大匹配匹配,其中其中e1,e7,e4是最大匹配。是最大匹配。2024/7/14离散数学10(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在图在图(1)中中不存在完美匹配。不存在完美匹配。在图在图(2)中中,e1,e7,e4是最大匹配，同时也是是最大匹配，同时也是完美匹配。完美匹配。今后常用今后常用M表示匹配，设表示匹配，设M为为G中一个匹配，中一个匹配，v V(G),若存在若存在M中的边与中的边与v关联，则称关联，则称v为为M饱和点饱和点，否则，否则v为为M非饱和点非饱和点，若，若G中每个顶点中每个顶点都是饱和点，则称都是饱和点，则称M为为G中中完美匹配完美匹配。2024/7/14离散数学11定义定义8.3设设G=为二部图为二部图,M为为G中一个最大中一个最大匹配匹配,若若|M|=min|V1|,|V2|,则称则称M为为G中的一中的一个个完备匹配完备匹配,此时若此时若|V1|V2|,则称则称M为为V1到到V2的的一个完备匹配。如果一个完备匹配。如果|V1|=|V2|,这时这时M为为G中的完中的完美匹配。美匹配。G1G2G3在上图中在上图中,e1,e2为为G1中的最大匹配中的最大匹配,G1中不存在完备中不存在完备匹配匹配,更无完美匹配。更无完美匹配。G2中中e1,e2,e3为完备匹配为完备匹配,但但G2中无完美匹配。中无完美匹配。G3中中e1,e2,e3为完备匹配为完备匹配,同时也是同时也是完美匹配。完美匹配。e1e2e1e2e3e1e2e32024/7/14离散数学12例例8.2 8.2 我们班级成立了我们班级成立了 3 3 个运动队个运动队:篮球队、排球队和足球队。篮球队、排球队和足球队。今有今有张、王、李、赵、陈张、王、李、赵、陈5 5位同学位同学，若已知，若已知张、王为篮球队员张、王为篮球队员；张、李、赵为排球队员张、李、赵为排球队员；李、赵、陈为足球队员李、赵、陈为足球队员，问能否从这，问能否从这5 5人中选出人中选出3 3名不兼职的队长？名不兼职的队长？解解:构造二部图构造二部图G=VG=,E其中其中V V1 1=篮球队篮球队,排球队排球队,足球队足球队,V V2 2=张张,王王,李李,赵赵,陈陈 图中的边分别表示这图中的边分别表示这5 5位同学是相应球位同学是相应球队的队员队的队员,图中存在图中存在V V1 1到到V V2 2的匹配的匹配,因此因此题目要求可以满足。题目要求可以满足。如可选如可选张为篮球队长张为篮球队长,李为排球队长李为排球队长,陈为陈为足球足球队长。队长。篮篮排排足足张张王王李李 赵赵 陈陈V V1 1V V2 22024/7/14离散数学13篮篮排排足足张张王王李李 赵赵 陈陈V V1 1V V2 2篮篮排排足足张张王王李李 赵赵 陈陈V V1 1V V2 2篮篮排排足足张张王王李李 赵赵 陈陈V V1 1V V2 2篮篮排排足足张张王王李李 赵赵 陈陈V V1 1V V2 2剩剩下下的的匹匹配配同同学学们们自自己己找找2024/7/14离散数学14几个问题几个问题1 1“一笔画一笔画”问题问题2 2“街道清扫车街道清扫车”设某封闭式小区的路网结构如图设某封闭式小区的路网结构如图所示，请证明能否设计出一条路所示，请证明能否设计出一条路线使得清洁车从小区大门出发清线使得清洁车从小区大门出发清扫每条道路恰好一次，且在清扫扫每条道路恰好一次，且在清扫完最后一条道路后正好返回小区完最后一条道路后正好返回小区大门处。大门处。3 3 七桥问题七桥问题小区大门ABCD8.2 8.2 欧拉图欧拉图2024/7/14离散数学15ABCD在以下在以下4个图中个图中,不能一笔画出图不能一笔画出图,而能一笔而能一笔画出图画出图,且在且在中笔又能回到出发点。中笔又能回到出发点。在在中存在关联所有顶点的中存在关联所有顶点的简单通路简单通路,在在中存在关联所有顶点的中存在关联所有顶点的简单回路简单回路2024/7/14离散数学16定义定义8.48.4 通过图通过图(无向图或有向图无向图或有向图)中所有边一次且中所有边一次且仅一次行遍所有顶点的通路称为仅一次行遍所有顶点的通路称为欧拉通路欧拉通路。通过图中所有边一次且仅一次行遍所有顶通过图中所有边一次且仅一次行遍所有顶点的回路称为点的回路称为欧拉回路欧拉回路。具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图。具有欧拉通路而无欧拉回路的图称为具有欧拉通路而无欧拉回路的图称为半欧半欧拉图。拉图。规定：平凡图是欧拉图。规定：平凡图是欧拉图。2024/7/14离散数学17ABCDEe1e2e3e4例例8.48.4 左下图既是左下图既是欧拉回路欧拉回路，也是，也是欧拉图欧拉图 而右下图则是而右下图则是欧拉通路欧拉通路2024/7/14离散数学18推论推论 无向图无向图G G是是欧拉图欧拉图 G G是连通图，且是连通图，且G G中中没有奇度顶点没有奇度顶点。无向图无向图G G是是半欧拉图半欧拉图 G G是连通图，且是连通图，且G G中中恰有两个奇度顶点恰有两个奇度顶点。定理定理8.48.4无向图无向图G G具有欧拉通路具有欧拉通路 G G是连通图，且是连通图，且G G中中有有零个或两个奇度顶点零个或两个奇度顶点。若无奇度顶点，则通路为欧拉回路；若无奇度顶点，则通路为欧拉回路；若有若有两个奇度顶点，则它们是每条欧拉通路的端点。两个奇度顶点，则它们是每条欧拉通路的端点。2024/7/14离散数学19例例8.5考察下图是否为欧拉图考察下图是否为欧拉图或存在欧拉通路或存在欧拉通路？存在两个奇度顶点存在两个奇度顶点根据定理根据定理8.4推论知推论知不是欧拉图不是欧拉图.存在一条欧拉通路存在一条欧拉通路2024/7/14离散数学20定理定理 8.5 8.5有向图有向图D D具有欧拉通路具有欧拉通路 D D 是连通的是连通的,且除了且除了两个顶点外两个顶点外,其余顶点的入度均等于出度。在其余顶点的入度均等于出度。在这两个特殊的顶点中这两个特殊的顶点中,一个顶点的入度比出度一个顶点的入度比出度大大1,1,另一个顶点的入度比出度小另一个顶点的入度比出度小1 1。推论推论一个一个有向图有向图D D是欧拉图是欧拉图 D D是连通的，是连通的，且所有且所有顶点的入度等于出度顶点的入度等于出度。特别提醒：特别提醒：欧拉回路要求边不能重复，结点可欧拉回路要求边不能重复，结点可以重复以重复.笔不离开纸，不重复地走完所有的边，笔不离开纸，不重复地走完所有的边，回到原处回到原处.就是所谓的一笔画就是所谓的一笔画.2024/7/14离散数学21v0v1v2e10e12e21e00e01e20e22e12e01例例8.78.7 考察考察下图是下图是欧拉通路或欧拉回路吗？欧拉通路或欧拉回路吗？三个顶点的度出度与入度相同三个顶点的度出度与入度相同 是是欧拉回路欧拉回路！沿着边沿着边 e00,e01,e12,e22,e21,e10,e01,e12,e20回到出发点回到出发点2024/7/14离散数学22几个问题几个问题在一个大城市，有很多取款机，那么，如何制定出一个在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每个提款机一次就能运送完钱最优的路线，使运钞车过每个提款机一次就能运送完钱钞？钞？货郎担问题货郎担问题旅行商人问题旅行商人问题(TravelingSalesmanProblem,TSP)优化算法优化算法近似解近似解演化算法演化算法8.3 8.3 哈密顿图哈密顿图2024/7/14离散数学23几个问题几个问题1.在一个大城市，有很多取款机，那么，如何制定出一个在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每个提款机一次就能运送完钱最优的路线，使运钞车过每个提款机一次就能运送完钱钞？钞？货郎担问题货郎担问题旅行商人问题旅行商人问题(TSP)2.考虑在七天内安排七门课程的考试，要求同一位教师所考虑在七天内安排七门课程的考试，要求同一位教师所任教的两门课程考试不安排在接连的两天里，如果教师任教的两门课程考试不安排在接连的两天里，如果教师所担任的课程都不多于四门，则是否存在满足上述要求所担任的课程都不多于四门，则是否存在满足上述要求的考试安排方案？的考试安排方案？时间表问题时间表问题3.国际象棋的跳马是否可以遍历其棋盘，即从任一格出发国际象棋的跳马是否可以遍历其棋盘，即从任一格出发跳到每一格仅一次并最后回到出发的棋盘格子？跳到每一格仅一次并最后回到出发的棋盘格子？4.在一个至少有在一个至少有5人出席的圆桌会议上（会议需要举行多人出席的圆桌会议上（会议需要举行多次），为达到充分交流的目的，会议主持者希望每次会次），为达到充分交流的目的，会议主持者希望每次会议每人两侧的人均与前次不同，这是否可行？请应用图议每人两侧的人均与前次不同，这是否可行？请应用图论知识进行论证。论知识进行论证。5.5.周游世界问题周游世界问题周游世界问题周游世界问题2024/7/14离散数学24哈密尔顿图哈密尔顿图l问题问题1859年爱尔兰数学家威廉年爱尔兰数学家威廉哈密尔顿（哈密尔顿（SirWilliamHamilton）发明了一个小游戏玩具：一）发明了一个小游戏玩具：一个木刻的正十二面体，每面系正五角形，三面交个木刻的正十二面体，每面系正五角形，三面交于一角，共有于一角，共有20个角，每角标有世界上一个重要个角，每角标有世界上一个重要城市。哈密尔顿提出一个问题：要求沿正十二面城市。哈密尔顿提出一个问题：要求沿正十二面体的边寻找一条路通过体的边寻找一条路通过20个城市，而每个城市只个城市，而每个城市只通过一次，最后返回原地。哈密尔顿将此问题称通过一次，最后返回原地。哈密尔顿将此问题称为周游世界问题。为周游世界问题。游戏)l求解求解抽象为图论问题抽象为图论问题哈密尔顿给出了肯定回答，该问题的解是存在哈密尔顿给出了肯定回答，该问题的解是存在的的哈密尔顿回路哈密尔顿回路(圈圈)哈密尔顿图哈密尔顿图运筹学、计算机科学和编码理论中的很多问题都可以化为哈密尔顿图问题运筹学、计算机科学和编码理论中的很多问题都可以化为哈密尔顿图问题 William Rowan Hamilton(1805-1865)2024/7/14离散数学25定义定义 8.5 8.5 经过图（有向图或无向图）中所有顶经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为点一次且仅一次的通路称为哈密顿通路哈密顿通路。经过图中所有顶点一次且仅一次的回经过图中所有顶点一次且仅一次的回路称为路称为哈密顿回路。哈密顿回路。具有哈密顿回路的图称为具有哈密顿回路的图称为哈密顿图哈密顿图.具有具有哈密顿通路哈密顿通路但不具有哈密顿回路但不具有哈密顿回路的图称为的图称为半哈密顿图半哈密顿图.注注:平凡图是哈密顿图平凡图是哈密顿图。8.3 8.3 哈密顿图哈密顿图2024/7/14离散数学26例例8.10指出下列各图是否哈密顿图指出下列各图是否哈密顿图,有无哈密顿有无哈密顿通路通路,回路？回路？解解(1)容容易易判判断断,存存在在哈哈密密顿顿回回路路,故故是是哈哈密密顿顿图图.(2)只只有有哈哈密密顿顿通通路路,无无哈哈密密顿顿回回路路,故故不不是是哈哈密顿图密顿图.(3)无哈密顿通路，显然不是哈密顿图无哈密顿通路，显然不是哈密顿图.(1)(2)(3)2024/7/14离散数学27定理定理 8.6 8.6 必要条件必要条件 设无向图设无向图G=G=是哈密顿图是哈密顿图,对于任意对于任意V V1 1 V V且且V V1 1,均有均有 p(G-Vp(G-V1 1)|V V1 1|,其中其中p(G-Vp(G-V1 1)为为G G中删除中删除V V1 1(删除删除V V1 1中各顶点及关联的边中各顶点及关联的边)后所得图后所得图的连通分支数。的连通分支数。证证:设设C C为为G G中任意一条哈密顿回路。中任意一条哈密顿回路。若若V V1 1中的顶点在中的顶点在C C上彼此相邻，则上彼此相邻，则 p(C-V p(C-V1 1)=1)=1|V V1 1|设设V V1 1中的顶点在中的顶点在C C上存在上存在 r(2r(2 r|V V1 1|)个个 互不相邻，则互不相邻，则 p(C-Vp(C-V1 1)=r)=r|V V1 1|一般说来一般说来,V V1 1中的中的顶点在顶点在C C上既有相邻的上既有相邻的,又有不又有不相邻的相邻的,因而总有因而总有 p(C-Vp(C-V1 1)|V V1 1|，而而C C是是G G的生成子图的生成子图,p(G-Vp(G-V1 1)p(C-Vp(C-V1 1)|V V1 1|2024/7/14离散数学28e1e2e3e4e5e6v1v2v3v4V1=v1,v4或或V1=v2,v3 v5若若V1中的顶点在中的顶点在C上彼此相邻，则上彼此相邻，则P(C-V1)=1|V1|2024/7/14离散数学29e1e2e3e4e5e6e7V1=v1,v2,v3或或V1=v1,v4,v3 v1v2v3v4v5设设V1中的顶点在中的顶点在C上存在上存在r(2r|V1|)个个互不相邻，则互不相邻，则P(C-V1)=r|V1|2024/7/14离散数学30例例8.13利用定理利用定理8.6可判断某些图不是可判断某些图不是哈密顿哈密顿图图设下图设下图为为G G1 1,取取 V V1 1=v,则则P(GP(G1 1-V-V1 1)=2)=2|V V1 1|=1 G G1 1-V-V1 1为图为图所示所示,由由定理定理8.6可知可知G G1 1不是不是哈密顿哈密顿图图v2024/7/14离散数学31定理定理 8.7 8.7 充分条件充分条件 设设 G G 是是 n(n3)n(n3)阶无向简单图，若对阶无向简单图，若对 G G中任意不相邻的顶点中任意不相邻的顶点 v vi i,v,vj j的度数之和大于等于的度数之和大于等于n-n-1 1，即，即 d(vd(vi i)+d(v)+d(vj j)n-1 )n-1 则则G G中存在哈密顿通路中存在哈密顿通路.推论推论 设设G G为为n(n 3)n(n 3)阶无向简单图，若对于阶无向简单图，若对于G G中任中任意两个不相邻的顶点意两个不相邻的顶点v vi i,v,vj j，均有均有 d(vd(vi i)+d(v)+d(vj j)n)n 则则G G中存在哈密顿回路，从而中存在哈密顿回路，从而G G为哈密顿图。为哈密顿图。2024/7/14离散数学32e1e2e3e4e5e6d(vi)+d(vj)n-1存在哈密顿通路存在哈密顿通路d(vi)+d(vj)n存在哈密顿回路存在哈密顿回路2024/7/14离散数学33(2)(3)再如下图再如下图G任意两个不相邻的顶点任意两个不相邻的顶点vi,vj vi,vj d(vi)+d(vj)n-1 d(vi)+d(vj)n-1 则则G G中存在哈密顿通路中存在哈密顿通路.d(vi)+d(vj)n d(vi)+d(vj)n 则则G G中存在哈密顿回路，中存在哈密顿回路，从而从而G G为哈密顿图。为哈密顿图。abdc(1)(1)和和(2)2024/7/14离散数学34定理定理 8.8 8.8 在在 n(n2)n(n2)阶有向图阶有向图 D=D=中，如果所有中，如果所有有向边均用无向边代替，所得无向图中含生成子有向边均用无向边代替，所得无向图中含生成子图图K Kn n,则有向图则有向图 D D 中存在哈密顿通路中存在哈密顿通路.推论推论 n(n 3)n(n 3)阶有向完全图阶有向完全图G G为哈密顿图为哈密顿图。2024/7/14离散数学35例例8.15已知有关人员已知有关人员a,b,c,d,e,f,g的有关信息的有关信息a：说英语；说英语；b：说英语或西班牙语；说英语或西班牙语；c；说英语，意大利语和俄语；说英语，意大利语和俄语；d：说日语和西班牙语说日语和西班牙语e：说德语和意大利语；说德语和意大利语；f：说法语、日语和俄语；说法语、日语和俄语；g：说法语和德语说法语和德语.试问：上述试问：上述7人中是否任意两人都能交谈？人中是否任意两人都能交谈？(可借助其余可借助其余5人中组成的译员链帮助人中组成的译员链帮助)2024/7/14离散数学36abcdefg解解设设7个个人人为为7个个结结点点,将将两两个个懂懂同同一一语语言言的的人人之之间间连连一一条条边边(即即他他们们能能直直接接交交谈谈),这这样样就就得得到到一一个个简简单单图图G,问问题题就就转转化化为为G是是否否连连通通.如如图图所所示示,因因为为G的的任任意意两两个个结结点点是是连连通通的的,所所以以G是是连连通通图图.因因此此,上述上述7个人中任意两个人能交谈个人中任意两个人能交谈.a：说说英语英语；b：说说英语英语或或西班牙西班牙语；语；C:说英语说英语,意大利语意大利语和和俄语俄语；d：说说日语日语和和西班牙西班牙语语e：说德语和说德语和意大利语意大利语；f：说说法语法语、日语日语和和俄语俄语；g：说说法语法语和德语和德语.2024/7/14离散数学37abcdefg如如果果题题目目改改为为：试试问问这这7个个人人应应如如何何安安排排座座位位,才才能使每个人都能与他身边的人交谈？能使每个人都能与他身边的人交谈？解解：用用结结点点表表示示人人，用用边边表表示示连连接接的的两两个个人人能能将将同同一种语言，够造出一种语言，够造出哈密顿图如右上哈密顿图如右上图所示。图所示。a：说英语；说英语；b：说英语或西班牙语；说英语或西班牙语；c；说英语，意大利说英语，意大利语和俄语；语和俄语；d：说日语和西班牙语说日语和西班牙语e：说德语和意大利语；说德语和意大利语；f：说法语、日语和俄语；说法语、日语和俄语；g：说法语和德语说法语和德语.英英英英西西日日法法德德意意2024/7/14离散数学38对对于于平平面面图图,先先举举一一例例,设设有有一一个个电电路路它它有有六六个个元元件件，三三个个分分成成一一组组，一一个个元元件件组组的的每每个个元元件件都都用用导导线线与与另另一一组组的的每每个个元元件件相相接接，是是否否有有这这样样的的接接法法使使得得导导线线互互不不交交叉叉？这这个个问问题题可可用用左左下下图图表表示示,它它的的最最少少交交叉叉点点是是一一个个，用用右右下下图表示图表示8.4.平面图平面图2024/7/14离散数学39定义定义8.6一一个个图图G能能画画在在平平面面上上，除除顶顶点点之之外外，再再没没有边与边相交有边与边相交.则称则称G为为平面图平面图。画画出出的的没没有有边边交交叉叉的的图图称称为为G的的一一个个平平面面嵌嵌入入或或G的的一个平面一个平面.在在下下图图中中(2)是是(1)(K4)的的平平面面嵌嵌入入,所所以以(1)是是平平面面图图,单单独独看看(2)也也是是平平面面图图,对对于于(3)(K5)无无论怎样画法论怎样画法,也去不掉交叉边也去不掉交叉边,所以不是平面图。所以不是平面图。(1)(2)(3)(4)2024/7/14离散数学40例例8.16右右下下图图是是左左下下图图的的平平面面嵌嵌入入,所所以以左左下下图图是平面图是平面图,单独看右下图也是平面图。单独看右下图也是平面图。2024/7/14离散数学41定义定义8.7设设G是是一一个个连连通通的的平平面面图图,G的的边边将将G所所在在的的平平面面划划分分成成若若干干个个区区域域,每每个个区区域域称称为为G的的一一个个面面。其其中中面面积积无无限限的的区区域域称称为为无无限限面面或或外外部部面面,常常记记为为R0,面面积积有有限限的的区区域域称称为为有有限限面面或或内内部部面面。包包围围每每个个面面的的所所有有边边所所构构成成的的回回路路称称为为该该面面的的边边界界,边边界界的的长长度度称称为为该该面面的的次次数数,R次次数数记记为为deg(R)对对于于非非连连通通的的平平面面图图G可可以以类类似似地地定定义义它它的的面面、边界及次数。边界及次数。2024/7/14离散数学42v1v2v3v4v5v6v1v2v3v4v5v6v7R0R1R2R1R0R2(1)(2)在下图中在下图中,图图(1)所示为连通的平面图所示为连通的平面图,共有共有3个面个面R0,R1,R2。R1的边界为初级回路的边界为初级回路v1v3v4v1,deg(R1)=3。R2的边界为初级回路的边界为初级回路v1v2v3v1,deg(R2)=3。R0无限面无限面,它的边界为复杂回路它的边界为复杂回路v1v4v5v6v5v4v3v2v1,deg(R0)=8。图图(2)所示为所示为非连通的平面图，有两个连通分支，非连通的平面图，有两个连通分支，deg(R1)=3，deg(R2)=4，R0的边界由两个初级回路的边界由两个初级回路v1v2v3v1和和v4v5v6v7v4围成，围成，deg(R0)=7。2024/7/14离散数学43v1v2v3v4v5v6v1v2v3v4v5v6v7R0R1R2R1R0R2(1)(2)定理定理8.9在一个在一个平面图平面图G中中,所有面的次数之和边所有面的次数之和边数数m的的2倍，即倍，即 deg(Ri)=2m在如下图所示：无论是连通的还是非连通的在如下图所示：无论是连通的还是非连通的平面图，各面次数之和均等于边数的两倍。平面图，各面次数之和均等于边数的两倍。i=1r其中其中r为面数为面数2024/7/14离散数学44定义定义8.8设设G为为一一个个平平面面图图,如如果果在在G中中任任意意不不相相邻邻的的两两个个顶顶点点之之间间再再加加一一条条边边,所所得得图图为为非非平平面面图图,则称则称G为为极大平面图极大平面图。例：例：GG2024/7/14离散数学45定义定义8.8在在非非平平面面图图G中中任任意意删删除除一一条条边边，所所得得图图为为平面图平面图,则称则称G为为极小非平面图极小非平面图。例：例：GG2024/7/14离散数学46欧拉公式：欧拉公式：定理定理8.10设设G为任意的为任意的连通连通的平面图的平面图,则有则有nm+r=2成成立立。其其中中,n为为G中中的的顶顶点点数数,m为为边边数数,r为为面面数。数。(或或结点数与面数之和边数结点数与面数之和边数2)定定理理中中平平面面图图的的连连通通性性条条件件是是重重要要的的。如如下下所所示示的平面图，的平面图，n=7,m=7,r=3，欧拉公式不成立欧拉公式不成立则欧拉公式则欧拉公式成立成立2024/7/14离散数学47欧拉公式证明欧拉公式证明:对边数m作数学归纳:1.m=0,G为孤立点,n=1,r=1,结论成立2.设m=k-1(k=1)时结论成立,要证明m=k时结论成立.若G为树,任取一树叶v并删除它,则G=G-v,则G连通,G中有n=n-1,m=m-1,r=r因此由归纳假设可得:n-m+r=2即:(n-1)-(m-1)+r=2也就是:n-m+r=2.连通而不含回路的连通而不含回路的无向图称为无向树无向图称为无向树2024/7/14离散数学48其次,若G不是树,则G中必有初级回路,设C为一初级回路,边e在C上,令G=G-e因为e在C上,所以G仍连通,在G中,n=n,m=m-1,r=r-1,利用归纳假设可得n-m+r=22024/7/14离散数学49Thank you very much!人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。