第八章一些特殊的图

1、2022-7-31第八章第八章 一些特殊的图一些特殊的图内容导读内容导读: 二部图二部图 欧拉图欧拉图哈密顿图哈密顿图平面图平面图难点难点:各种图的判别定理各种图的判别定理2022-7-32 2022-7-33(1)(2) 设无向图设无向图 G = 有两个有两个V的子集的子集V1,V2, 它们具有满足：它们具有满足： V1V2= V V1V2= 图图G中的每一边中的每一边 e 均具有均具有 e = ( vi , vj ) 其中：其中： vi V1 , vj V2 则称则称G是一个是一个二部图二部图，2022-7-34定义定义8.1 若一个图若一个图G的结点集的结点集V能划分为两个子能划分为两个

2、子集集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,32022-7-35(1)(2)例例 8.1 判断下列图是否是二部图？判断下列图是否是二部图？v1v3v5v2v4v6v1v4v8v5v2v

3、3v6v7v1v2v3v4v5(3)在图在图 (1) 中中, V1=v1, v3, v5, V2=v2, v4, v6, 是一个完是一个完全二部图。在图全二部图。在图 (2) 中中, V1=v1, v4, v8, v5, V2=v2, v3, v7, v6, 是一个二部图。在图是一个二部图。在图 (3) 中中, 对于对于其中的顶点无法将它们分到两个不同的子集其中的顶点无法将它们分到两个不同的子集V1和和 V2,使其边能满足二部图的定义使其边能满足二部图的定义, 所以它不是二部图。所以它不是二部图。二部图是不是一定是连通图?2022-7-36(4)(5)定理定理8.1 一个无向图一个无向图 G

4、= 是二部图是二部图当且当且仅当仅当G中无奇数长度的回路。中无奇数长度的回路。 下图所示前下图所示前3个图中个图中, 均无奇数长度的回路均无奇数长度的回路, 所以它们都是二部图所以它们都是二部图, 其中图其中图(2)所示为所示为K2, 3, 图图(3)所示为所示为K3, 3, 它们分别与图它们分别与图(4)和和(5)同构同构。(1)(2)(3)2022-7-37(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在图在图(1)中，中，e1, e1, e7 , e5, e4 , e6 等都是图中等都是图中的匹配。的匹配。在图在图(2)中找出匹配。中找出匹配。定义定义8.2 设设

5、G = 为无向图为无向图, E* E, 若若E*中任意两中任意两条边均不相邻条边均不相邻, 则子集则子集E*称为称为G中的中的匹配匹配(或或边独边独立集立集), 并把并把E*中的边所关联的两个结点称为在中的边所关联的两个结点称为在E*下是匹配的。下是匹配的。2022-7-38(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在图在图(1)中中, e5, e1, e7 , e4 , e6 e3, e7 , e2, e6 是是极大匹配极大匹配，后后4个是最大匹配，匹配数个是最大匹配，匹配数 1 =2。若在若在E*中再加入任何一条边就都不是匹配了中再加入任何一条边就都不是匹配了,

6、则称则称E*为为极大匹配极大匹配。边数最多的极大匹配称为。边数最多的极大匹配称为最大匹配最大匹配，最大匹配中的元素，最大匹配中的元素(边边)的个数称为的个数称为G的的匹配数匹配数，记为，记为 1(G), 简记为简记为 1 。2022-7-39(2)e1e2e3e4e5e6e7在图在图(2)中中, e2, e5 , e3 , e6 ,e1 , e7 , e4 都是极大匹都是极大匹配配, 其中其中e1, e7, e4 是最大匹配。是最大匹配。2022-7-310(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在图在图(1)中中不存在完美匹配。不存在完美匹配。在图在图(2)中中,

7、e1, e7, e4 是最大匹配，同时也是是最大匹配，同时也是完美匹配。完美匹配。今后常用今后常用M表示匹配，设表示匹配，设M为为G中一个匹配，中一个匹配，v V(G), 若存在若存在M中的边与中的边与v关联，则称关联，则称v为为M饱和点饱和点，否则，否则v为为M非饱和点非饱和点，若，若G中每个顶点中每个顶点都是饱和点，则称都是饱和点，则称M为为G中中完美匹配完美匹配。2022-7-311定义定义8.3 设设 G = 为二部图为二部图, M为为G中一个最大中一个最大匹配匹配, 若若 |M| = min |V1|, |V2| , 则称则称M为为G中的一中的一个个完备匹配完备匹配, 此时若此时若|

8、V1| |V2|, 则称则称M为为V1到到 V2的的一个完备匹配。如果一个完备匹配。如果|V1|= |V2| ,这时这时M为为G中的完中的完美匹配。美匹配。G1G2G3在上图中在上图中, e1, e2 为为G1中的最大匹配中的最大匹配, G1中不存在完备中不存在完备匹配匹配, 更无完美匹配。更无完美匹配。 G2中中e1, e2 , e3为完备匹配为完备匹配, 但但G2中无完美匹配。中无完美匹配。 G3中中e1,e2, e3为完备匹配为完备匹配, 同时也是完同时也是完美匹配。美匹配。e1e2e1e2e3e1e2e32022-7-312例例8.2 8.2 我们班级成立了我们班级成立了 3 3 个运

9、动队个运动队: :篮球队、排球队和足球队。篮球队、排球队和足球队。今有今有张、王、李、赵、陈张、王、李、赵、陈5 5位同学位同学，若已知，若已知张、王为篮球队员张、王为篮球队员；张、李、赵为排球队员张、李、赵为排球队员；李、赵、陈为足球队员李、赵、陈为足球队员，问能否从这，问能否从这5 5人中选出人中选出3 3名不兼职的队长？名不兼职的队长？解解: :构造二部图构造二部图G=VG=,E其中其中V V1 1= = 篮篮球队球队, ,排球队排球队, ,足球队足球队 , ,V V2 2= = 张张, ,王王, ,李李, ,赵赵, ,陈陈 图中的边分别表示这图中的边分别表示这5 5位同学是相应球位同学

10、是相应球队的队员队的队员, ,图中存在图中存在V V1 1到到V V2 2的匹配的匹配, ,因因此题目要求可以满足。此题目要求可以满足。如可选如可选张为篮球队长张为篮球队长, ,李为排球队长李为排球队长, ,陈为陈为足球足球队长。队长。篮篮排排足足张张王王李李 赵赵 陈陈V V1 1V V2 22022-7-313篮篮排排足足张张王王李李 赵赵 陈陈V V1 1V V2 2篮篮排排足足张张王王李李 赵赵 陈陈V V1 1V V2 2篮篮排排足足张张王王李李 赵赵 陈陈V V1 1V V2 2篮篮排排足足张张王王李李 赵赵 陈陈V V1 1V V2 2剩下的匹配同学们自己找剩下的匹配同学们自己找

11、2022-7-314几个问题几个问题1 “1 “一笔画一笔画”问题问题2 “2 “街道清扫车街道清扫车”设某封闭式小区的路网结构如图设某封闭式小区的路网结构如图所示，请证明能否设计出一条路所示，请证明能否设计出一条路线使得清洁车从小区大门出发清线使得清洁车从小区大门出发清扫每条道路恰好一次，且在清扫扫每条道路恰好一次，且在清扫完最后一条道路后正好返回小区完最后一条道路后正好返回小区大门处。大门处。 3 3 七桥问题七桥问题小区大门ABCD8.2 8.2 欧拉图欧拉图2022-7-315ABCD在以下在以下4个图中个图中, 不能一笔画出图不能一笔画出图, , 而能一笔而能一笔画出图画出图, 且在

12、中笔又能回到出发点。且在中笔又能回到出发点。在中存在关联所有顶点的在中存在关联所有顶点的简单通路简单通路, 在中存在关联所有顶点的在中存在关联所有顶点的简单回路简单回路2022-7-316定义定义8.48.4 通过图通过图( (无向图或有向图无向图或有向图) )中所有边一次且中所有边一次且仅一次行遍所有顶点的通路称为仅一次行遍所有顶点的通路称为欧拉通路欧拉通路。 通过图中所有边一次且仅一次行遍所有顶通过图中所有边一次且仅一次行遍所有顶点的回路称为点的回路称为欧拉回路欧拉回路。 具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图。 具有欧拉通路而无欧拉回路的图称为具有欧拉通路而无欧拉回路的图称

13、为半欧半欧拉图。拉图。规定：平凡图是欧拉图。规定：平凡图是欧拉图。2022-7-317ABCDEe1e2e3e4例例8.48.4 左下图既是左下图既是欧拉回路欧拉回路，也是，也是欧拉图欧拉图 而右下图则是而右下图则是欧拉通路欧拉通路2022-7-318推论推论 无向图无向图G G是是欧拉图欧拉图 G G是连通图，且是连通图，且G G中中没有奇度顶点没有奇度顶点。 无向图无向图G G是是半欧拉图半欧拉图 G G是连通图，且是连通图，且G G中中恰有两个奇度顶点恰有两个奇度顶点。定理定理8.48.4无向图无向图G G具有欧拉通路具有欧拉通路 G G是连通图，且是连通图，且G G中中有有零个或两个奇

14、度顶点零个或两个奇度顶点。 若无奇度顶点，则通路为欧拉回路；若无奇度顶点，则通路为欧拉回路；若有若有两个奇度顶点，则它们是每条欧拉通路的端点。两个奇度顶点，则它们是每条欧拉通路的端点。 2022-7-319例例 8.5 考察下图是否为欧拉图考察下图是否为欧拉图 或存在欧拉通路或存在欧拉通路？ 存在两个奇度顶点存在两个奇度顶点 根据定理根据定理8.4推论知推论知 不是欧拉图不是欧拉图. 存在一条欧拉通路存在一条欧拉通路2022-7-320定理定理 8.5 8.5有向图有向图D D具有欧拉通路具有欧拉通路 D D 是连通的是连通的, ,且除了且除了两个顶点外两个顶点外, ,其余顶点的入度均等于出度

15、。在其余顶点的入度均等于出度。在这两个特殊的顶点中这两个特殊的顶点中, ,一个顶点的入度比出度一个顶点的入度比出度大大1,1,另一个顶点的入度比出度小另一个顶点的入度比出度小1 1。推论推论一个一个有向图有向图D D是欧拉图是欧拉图 D D是连通的，是连通的，且所有且所有顶点的入度等于出度顶点的入度等于出度。特别提醒：特别提醒：欧拉回路要求边不能重复，结点可欧拉回路要求边不能重复，结点可以重复以重复. . 笔不离开纸，不重复地走完所有的边，笔不离开纸，不重复地走完所有的边，回到原处回到原处. . 就是所谓的一笔画就是所谓的一笔画. . 2022-7-321v0v1v2e10e12e21e00e

16、01e20e22e12e01例例8.78.7 考察考察下图是下图是欧拉通路或欧拉回路吗？欧拉通路或欧拉回路吗？三个顶点的度出度与入度相同三个顶点的度出度与入度相同 是是欧拉回路欧拉回路！ 沿着边沿着边 e00, e01, e12, e22, e21, e10, e01, e12, e20 回到出发点回到出发点2022-7-322几个问题几个问题 在一个大城市，有很多取款机，那么，如何制定出一个在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每个提款机一次就能运送完钱最优的路线，使运钞车过每个提款机一次就能运送完钱钞？钞？ 货郎担问题货郎担问题旅行商人问题旅行商人问题 (T

17、raveling Salesman Problem ,TSP) 优化算法优化算法近似解近似解演化算法演化算法8.3 8.3 哈密顿图哈密顿图2022-7-323几个问题几个问题1. 在一个大城市，有很多取款机，那么，如何制定出一个在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每个提款机一次就能运送完钱最优的路线，使运钞车过每个提款机一次就能运送完钱钞？钞？ 货郎担问题货郎担问题旅行商人问题旅行商人问题(TSP)2. 考虑在七天内安排七门课程的考试，要求同一位教师所考虑在七天内安排七门课程的考试，要求同一位教师所任教的两门课程考试不安排在接连的两天里，如果教师任教的两门课

18、程考试不安排在接连的两天里，如果教师所担任的课程都不多于四门，则是否存在满足上述要求所担任的课程都不多于四门，则是否存在满足上述要求的考试安排方案？的考试安排方案？ 时间表问题时间表问题3. 国际象棋的跳马是否可以遍历其棋盘，即从任一格出发国际象棋的跳马是否可以遍历其棋盘，即从任一格出发跳到每一格仅一次并最后回到出发的棋盘格子？跳到每一格仅一次并最后回到出发的棋盘格子？4. 在一个至少有在一个至少有5人出席的圆桌会议上（会议需要举行多人出席的圆桌会议上（会议需要举行多次），为达到充分交流的目的，会议主持者希望每次会次），为达到充分交流的目的，会议主持者希望每次会议每人两侧的人均与前次不同，这是

19、否可行？请应用图议每人两侧的人均与前次不同，这是否可行？请应用图论知识进行论证。论知识进行论证。 2022-7-324哈密尔顿图哈密尔顿图l问题问题 1859年爱尔兰数学家威廉年爱尔兰数学家威廉哈密尔顿（哈密尔顿（Sir William Hamilton）发明了一个小游戏玩具：一）发明了一个小游戏玩具：一个木刻的正十二面体，每面系正五角形，三面交个木刻的正十二面体，每面系正五角形，三面交于一角，共有于一角，共有20个角，每角标有世界上一个重要个角，每角标有世界上一个重要城市。哈密尔顿提出一个问题：要求沿正十二面城市。哈密尔顿提出一个问题：要求沿正十二面体的边寻找一条路通过体的边寻找一条路通过2

20、0个城市，而每个城市只个城市，而每个城市只通过一次，最后返回原地。哈密尔顿将此问题称通过一次，最后返回原地。哈密尔顿将此问题称为周游世界问题。为周游世界问题。游戏) l求解求解 抽象为图论问题抽象为图论问题 哈密尔顿给出了肯定回答，该问题的解是存在哈密尔顿给出了肯定回答，该问题的解是存在的的哈密尔顿回路哈密尔顿回路( (圈圈) )哈密尔顿图哈密尔顿图运筹学、计算机科学和编码理论中的很多问题都可以化为哈密尔顿图问题运筹学、计算机科学和编码理论中的很多问题都可以化为哈密尔顿图问题 William Rowan Hamilton(1805-1865)2022-7-325定义定义 8.5 8.5 经过图

21、（有向图或无向图）中所有顶经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为点一次且仅一次的通路称为哈密顿通路哈密顿通路。 经过图中所有顶点一次且仅一次的回经过图中所有顶点一次且仅一次的回路称为路称为哈密顿回路。哈密顿回路。 具有哈密顿回路的图称为具有哈密顿回路的图称为哈密顿图哈密顿图. . 具有具有哈密顿通路哈密顿通路但不具有哈密顿回路但不具有哈密顿回路的图称为的图称为半哈密顿图半哈密顿图. .注注: :平凡图是哈密顿图平凡图是哈密顿图。8.3 8.3 哈密顿图哈密顿图2022-7-326例例8.10 指出下列各图是否哈密顿图指出下列各图是否哈密顿图,有无哈密顿有无哈密顿 通路通路,

22、回路？回路？解解 (1) 容易判断容易判断, 存在哈密顿回路存在哈密顿回路, 故是哈密顿图故是哈密顿图. (2) 只有哈密顿通路只有哈密顿通路, 无哈密顿回路无哈密顿回路, 故不是哈故不是哈 密顿图密顿图. (3) 无哈密顿通路，显然不是哈密顿图无哈密顿通路，显然不是哈密顿图. (1)(2)(3)2022-7-327定理定理 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中删除中删除

23、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- V p(C- V1 1)=r )=r | V V1 1 | 一般说来一般说来, V V1 1中的中的顶点在顶

24、点在C C上既有相邻的上既有相邻的, ,又有不相又有不相邻的邻的, ,因而总有因而总有 p(C- V p(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|2022-7-328e1e2e3e4e5e6v1v2v3v4V1=v1, v4 或或V1=v2, v3 v5若若V1中的顶点在中的顶点在C上彼此相邻，则上彼此相邻，则 P(C- V1)=1 | V1 |2022-7-329e1e2e3e4e5e6e7V1=v1, v2, v3 或或 V1=v1, v4, v3 v1

25、v2v3v4v5设设V1中的顶点在中的顶点在C上存在上存在 r( 2 r | V1 | )个个 互不相邻，则互不相邻，则 P(C- V1)=r | V1 | 2022-7-330例例 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不是不是哈密顿哈密顿图图v2022-7-331定理定理 8.7 8.7 充分条件充分条件 设设 G G 是是 n

26、(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为哈密顿

27、图。为哈密顿图。2022-7-332e1e2e3e4e5e6d(vi)+d(vj)n-1 存在哈密顿通路存在哈密顿通路d(vi)+d(vj)n 存在哈密顿回路存在哈密顿回路2022-7-333(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)2022-7-334定理定理 8.8 8

28、.8 在在 n (n2)n (n2)阶有向图阶有向图 D=D=中，如果所有中，如果所有有向边均用无向边代替，所得无向图中含生成子有向边均用无向边代替，所得无向图中含生成子图图K Kn n, ,则有向图则有向图 D D 中存在哈密顿通路中存在哈密顿通路. .推论推论 n(n 3)n(n 3)阶有向完全图阶有向完全图G G为哈密顿图为哈密顿图。2022-7-335例例 8.15 已知有关人员已知有关人员a, b, c, d, e, f, g 的有关信息的有关信息 a：说英语；说英语； b：说英语或西班牙语；说英语或西班牙语； c；说英语，意大利语和俄语；说英语，意大利语和俄语； d：说日语和西班牙

29、语说日语和西班牙语 e：说德语和意大利语；说德语和意大利语； f：说法语、日语和俄语；说法语、日语和俄语； g：说法语和德语说法语和德语. 试问：上述试问：上述7人中是否任意两人都能交谈？人中是否任意两人都能交谈？ (可借助其余可借助其余5人中组成的译员链帮助人中组成的译员链帮助)2022-7-336abcdefg解解 设设7个人为个人为7个结点个结点, 将两个懂同一语言的人之将两个懂同一语言的人之间连一条边间连一条边(即他们能直接交谈即他们能直接交谈), 这样就得到一个这样就得到一个简单图简单图G, 问题就转化为问题就转化为G是否连通是否连通. 如图所示如图所示, 因因为为G的任意两个结点是

30、连通的的任意两个结点是连通的, 所以所以G是连通图是连通图. 因因此此, 上述上述7个人中任意两个人能交谈个人中任意两个人能交谈. a：说说英语英语；b：说说英语英语或或西班牙西班牙语；语；C: 说英语说英语,意大利语意大利语和和俄语俄语；d：说说日语日语和和西班牙西班牙语语e：说德语和说德语和意大利语意大利语；f：说说法语法语、日语日语和和俄语俄语；g：说说法语法语和德语和德语. 2022-7-337abcdefg如果题目改为：试问这如果题目改为：试问这7个人应如何安排座位个人应如何安排座位, 才才能使每个人都能与他身边的人交谈？能使每个人都能与他身边的人交谈？解：用结点表示人，用边表示连接

31、的两个人能将解：用结点表示人，用边表示连接的两个人能将同一种语言，够造出同一种语言，够造出哈密顿图如右上哈密顿图如右上图所示。图所示。a：说英语；说英语；b：说英语或西班牙语；说英语或西班牙语；c；说英语，意大利说英语，意大利 语和俄语；语和俄语；d：说日语和西班牙语说日语和西班牙语e：说德语和意大利语；说德语和意大利语；f：说法语、日语和俄语；说法语、日语和俄语；g：说法语和德语说法语和德语. 英英英英西西日日法法德德意意2022-7-338 对于对于平面图平面图, 先举一例先举一例, 设有一个电路它有六设有一个电路它有六个元件，三个分成一组，一个元件组的每个元个元件，三个分成一组，一个元件

32、组的每个元件都用导线与另一组的每个元件相接，是否有件都用导线与另一组的每个元件相接，是否有这样的接法使得导线互不交叉？这个问题可用这样的接法使得导线互不交叉？这个问题可用左下图表示左下图表示, 它的最少交叉点是一个，用右下图它的最少交叉点是一个，用右下图表示表示8.4.平面图平面图2022-7-339定义定义 8. 6 一个图一个图G能画在平面上，除顶点之外，再没能画在平面上，除顶点之外，再没有边与边相交有边与边相交. 则称则称G为为平面图平面图。 画出的没有边交叉的图称为画出的没有边交叉的图称为G的一个的一个平面嵌平面嵌入入或或G的的一个平面一个平面.在下图中在下图中(2)是是(1) (K4

33、)的平面嵌入的平面嵌入, 所以所以(1)是平面是平面图图, 单独看单独看(2)也是平面图也是平面图, 对于对于(3) (K5)无论怎样无论怎样画法画法,也去不掉交叉边也去不掉交叉边, 所以不是平面图。所以不是平面图。(1)(2)(3)(4)2022-7-340 例例 8.16 右下图是左下图的平面嵌入右下图是左下图的平面嵌入, 所以左下图所以左下图是平面图是平面图, 单独看右下图也是平面图。单独看右下图也是平面图。2022-7-341定义定义 8. 7 设设G是一个连通的平面图是一个连通的平面图, G的边将的边将G所在的所在的平面划分成若干个区域平面划分成若干个区域, 每个区域称为每个区域称为

34、G的一个的一个面面。其中面积无限的区域称为。其中面积无限的区域称为无限面或外部面无限面或外部面, 常记为常记为R0, 面积有限的区域称为面积有限的区域称为有限面或内部面有限面或内部面。包围每个面的所有边所构成的回路称为该面的包围每个面的所有边所构成的回路称为该面的边边界界, 边界的长度称为该面的边界的长度称为该面的次数次数, R次数记为次数记为deg(R) 对于非连通的平面图对于非连通的平面图G可以类似地定义它的面、可以类似地定义它的面、边界及次数。边界及次数。2022-7-342v1v2v3v4v5v6v1v2v3v4v5v6v7R0R1R2R1R0R2( 1 )( 2 )在下图中在下图中, 图图(1)所示为连通的平面图所示为连通的平面图, 共有共有3个面个面R0, R1, R2。 R1的边界为初级回路的边界为初级回路v1 v3 v4 v1 , deg(R1)=3。R2的边界为初级回路的边界为初级回路v1 v2 v3 v1 , deg(R2)=3。R0无限面无限面, 它的边界为复杂回路它的边界为复杂回路v1 v4 v5v6 v5 v4 v3 v2 v1 , deg(R0)=8。图图(2)所示为非所