第七章特殊图

1、第七章第七章 特殊图特殊图引言引言7.1 欧拉图欧拉图7.2 哈密尔顿图哈密尔顿图7.3 二部图二部图7.4 平面图平面图7.5 无向树无向树7.6 根树根树7.7 图的应用图的应用引引 言言 在第六章中，我们定义了图及图论中的基本概念。在第六章中，我们定义了图及图论中的基本概念。图实际上是一个抽象的系统，是从现实中各种各样的图实际上是一个抽象的系统，是从现实中各种各样的具体的系统出发，具体的系统出发， 经过高度概括而形成的。经过高度概括而形成的。 在本章，在本章，我们将在第六章的基础上，进一步讨论一些结构特殊我们将在第六章的基础上，进一步讨论一些结构特殊的图。这些图反映了某些特殊系统的最根本

2、的系统特的图。这些图反映了某些特殊系统的最根本的系统特性，它们在物理学、化学、建筑学、电子学、人文学、性，它们在物理学、化学、建筑学、电子学、人文学、系统科学、计算机科学等诸多学科中有着广泛的应用。系统科学、计算机科学等诸多学科中有着广泛的应用。图论中主要讨论欧拉图、哈密尔顿图、二部图、平面图论中主要讨论欧拉图、哈密尔顿图、二部图、平面图、无向树和树等六种特殊图。图、无向树和树等六种特殊图。 7.1 欧拉图欧拉图一、问题的提出一、问题的提出 欧拉图的概念来源于欧洲一个古老的难题欧拉图的概念来源于欧洲一个古老的难题-哥尼斯堡七哥尼斯堡七桥问题。哥尼斯堡（桥问题。哥尼斯堡（Konicberg）是东

3、普鲁士的一座城，第二）是东普鲁士的一座城，第二次世界大战后划归苏联，现名加里宁格勒，属俄罗斯。普雷次世界大战后划归苏联，现名加里宁格勒，属俄罗斯。普雷格尔（格尔（Pregel）河流经这个城市，具体如下图（左）所示。）河流经这个城市，具体如下图（左）所示。其中其中A，B是河的两岸，是河的两岸，C，D是河中的两个孤岛。是河中的两个孤岛。C，D两岛两岛与两岸以及彼此之间由七座桥连接。与两岸以及彼此之间由七座桥连接。 针对哥尼斯堡城的地理情况，有人提出了这样一个问题：针对哥尼斯堡城的地理情况，有人提出了这样一个问题：能否从该城的某片陆地开始行走，要求不重复地通过每座桥能否从该城的某片陆地开始行走，要求

4、不重复地通过每座桥一次，最后刚好回到出发点？显然，要解决这个问题，若问一次，最后刚好回到出发点？显然，要解决这个问题，若问题有解，就必须确切指出一条满足要求的行走路线来，否则题有解，就必须确切指出一条满足要求的行走路线来，否则则要严格地证明这样的路线不存在。最终，这个问题被瑞典则要严格地证明这样的路线不存在。最终，这个问题被瑞典数学家欧拉（数学家欧拉（L.EulerL.Euler）于）于17361736年解决了。在他的著名的论文年解决了。在他的著名的论文“哥尼斯堡七桥问题哥尼斯堡七桥问题”中，把每片陆地抽象成一个点，每座中，把每片陆地抽象成一个点，每座桥抽象成一条边，得到上图（右）。由此，哥尼

5、斯堡七桥问桥抽象成一条边，得到上图（右）。由此，哥尼斯堡七桥问题就变为上图（右）中是否存在从一个点出发，不重复地经题就变为上图（右）中是否存在从一个点出发，不重复地经过每条边一次，最终回到出发点的回路的问题过每条边一次，最终回到出发点的回路的问题。 除了哥尼斯堡七桥问题以外，还有许多问题，它们都可以抽除了哥尼斯堡七桥问题以外，还有许多问题，它们都可以抽象为判断一个图中是否存在不重复地经过每条边的的回路（通路）象为判断一个图中是否存在不重复地经过每条边的的回路（通路）的问题。例如，一笔画问题，路线考察问题，最优化问题等都具的问题。例如，一笔画问题，路线考察问题，最优化问题等都具有与哥尼斯堡七桥问

6、题相类似的特点。这些特点，可以利用下面有与哥尼斯堡七桥问题相类似的特点。这些特点，可以利用下面的定义来描述。的定义来描述。二、定义二、定义 1.欧拉通路：不重复地经过其中每条边的通路的图。欧拉通路：不重复地经过其中每条边的通路的图。 2.欧拉回路：不重复地经过每条边的回路的图。欧拉回路：不重复地经过每条边的回路的图。 3.半欧拉图：存在欧拉通路的图。半欧拉图：存在欧拉通路的图。 4.欧拉图：存在欧拉回路的图。欧拉图：存在欧拉回路的图。 显然，欧拉图必然是半欧拉图，但半欧拉图不一定是欧拉图。显然，欧拉图必然是半欧拉图，但半欧拉图不一定是欧拉图。 例如，例如， 在下图中，（在下图中，（1）不是欧拉

7、图，但是是半欧拉图；（）不是欧拉图，但是是半欧拉图；（2）和（和（3）既是欧拉图，也是半欧拉图；（）既是欧拉图，也是半欧拉图；（4）既不是欧拉图，也不）既不是欧拉图，也不是半欧拉图。是半欧拉图。 （1） （2） （3） （4）三、判定问题三、判定问题 有了欧拉图的概念之后，哥尼斯堡七桥问题是否有解，有了欧拉图的概念之后，哥尼斯堡七桥问题是否有解，就变成了上述右图是不是欧拉图的问题了。一个图形能否一笔就变成了上述右图是不是欧拉图的问题了。一个图形能否一笔画出，就看这个图形是不是半欧拉图了。为了解决欧拉图和半画出，就看这个图形是不是半欧拉图了。为了解决欧拉图和半欧拉图的判定问题，经过研究，欧拉找到

8、了相应的欧拉图和半欧拉图的判定问题，经过研究，欧拉找到了相应的欧拉图和半欧拉图的充分必要条件。欧拉图的充分必要条件。 定理定理1 对任何无向连通图对任何无向连通图G=，有：，有： （1）G是欧拉图，当且仅当是欧拉图，当且仅当G中每个结点的的度都是偶数；中每个结点的的度都是偶数； （2）G是半欧拉图，当且仅当是半欧拉图，当且仅当G中每个结点的的度都是偶数，中每个结点的的度都是偶数，或者或者G中有且仅有两个度为奇数的结点。中有且仅有两个度为奇数的结点。 说明：定理说明：定理1的结论只对无向连通图成立。例如，在下图中，的结论只对无向连通图成立。例如，在下图中，由于（由于（1）不是连通图，所以虽然其中

9、每个点的度都是偶数，但）不是连通图，所以虽然其中每个点的度都是偶数，但它仍然不是欧拉图；由于（它仍然不是欧拉图；由于（2）不是无向图，虽然其中每个点的）不是无向图，虽然其中每个点的度都是偶数，但它也不是半欧拉图。度都是偶数，但它也不是半欧拉图。 （1） （2） 对于有向欧拉图的判定，也有类似定理对于有向欧拉图的判定，也有类似定理1的结论。的结论。定理定理2 对任何有向图对任何有向图G=，有：，有： （1）G是欧拉图，当且仅当它是弱连通的，而且其中每个结是欧拉图，当且仅当它是弱连通的，而且其中每个结点的入度和出度都相同；点的入度和出度都相同； （2）G是半欧拉图但不是欧拉图，当且仅当它是弱连通的

10、，是半欧拉图但不是欧拉图，当且仅当它是弱连通的，而且其中只有两个结点的入度与出度不同，同时在这两个结点中，而且其中只有两个结点的入度与出度不同，同时在这两个结点中，一个结点的入度比出度大一个结点的入度比出度大1，另一个结点的入度比出度小，另一个结点的入度比出度小1。 例如，在下图中，（例如，在下图中，（2）和（）和（4）是欧拉图，（）是欧拉图，（1）是半欧拉图，）是半欧拉图，（3）既不是欧拉图，也不是半欧拉图。）既不是欧拉图，也不是半欧拉图。 （1） （2） （3） （4） 7.2 哈密尔顿图哈密尔顿图 一、问题的提出一、问题的提出 1859年，英国数学家威廉年，英国数学家威廉哈密尔顿（哈密尔

11、顿（W.Hamilton）提出提出了一种了一种“周游世界周游世界”问题，如图所示。图中共有问题，如图所示。图中共有20个结点，每个结点，每个结点表示一个城市，两结点有边相连表示该两城市之间有交个结点表示一个城市，两结点有边相连表示该两城市之间有交通可直达。现要求在图中寻找这样一种旅行路线，使经过每个通可直达。现要求在图中寻找这样一种旅行路线，使经过每个城市一次，且每个城市只经过一次，最终刚好回到出发的城市。城市一次，且每个城市只经过一次，最终刚好回到出发的城市。哈密尔顿证明了这样的旅行路线是存在的，具体的旅行次序见哈密尔顿证明了这样的旅行路线是存在的，具体的旅行次序见下图中各城市所标的序号。这

12、个问题是由哈密尔顿提出的，所下图中各城市所标的序号。这个问题是由哈密尔顿提出的，所以又称为哈密尔顿回路问题。对哈密尔顿回路问题进行抽象，以又称为哈密尔顿回路问题。对哈密尔顿回路问题进行抽象，可得到一类特殊图可得到一类特殊图-哈密尔顿图哈密尔顿图。 二、定义二、定义 1. 哈密尔顿通路：不重复地经过图中每个结点的通路。哈密尔顿通路：不重复地经过图中每个结点的通路。 2. 哈密尔顿回路：不重复地经过图中每个结点的回路。哈密尔顿回路：不重复地经过图中每个结点的回路。 3. 哈密尔顿图：含有哈密尔顿回路的图。哈密尔顿图：含有哈密尔顿回路的图。 4. 半哈密尔顿图：含有哈密尔顿通路的图。半哈密尔顿图：含

13、有哈密尔顿通路的图。 由于平行边和环的存在与否均不影响图中是否存在哈密由于平行边和环的存在与否均不影响图中是否存在哈密尔顿回路（通路），而且非连通的无向图中必不存在哈密尔尔顿回路（通路），而且非连通的无向图中必不存在哈密尔顿回路（通路），所以只须考虑简单连通图。顿回路（通路），所以只须考虑简单连通图。 三、判定问题三、判定问题 虽然哈密尔顿图看起来与欧拉图很类似，但判断一个图是否虽然哈密尔顿图看起来与欧拉图很类似，但判断一个图是否是哈密尔顿图比判断是否是欧拉图要困难得多。是哈密尔顿图比判断是否是欧拉图要困难得多。 事实上，到目前事实上，到目前为止，还没有找到一个简明的条件作为一个图是哈密尔顿图

14、的充为止，还没有找到一个简明的条件作为一个图是哈密尔顿图的充分必要条件，分必要条件， 寻找这种条件是图论中尚未解决的主要问题之一。寻找这种条件是图论中尚未解决的主要问题之一。 虽然如此，目前还是得到了一些充分条件和一些必要条件，下面虽然如此，目前还是得到了一些充分条件和一些必要条件，下面对它们作简单介绍。对它们作简单介绍。1. 必要条件必要条件定理定理1 若无向图若无向图G=是哈密尔顿图，则对是哈密尔顿图，则对V的任意非空子的任意非空子集集V1 ，都有，都有 P(G - V1) V1其中，其中，p(G - V1) 是从是从G中删除中删除V1中的所有结点后，剩下的图中的所有结点后，剩下的图G -

15、 V1的连通分支数。的连通分支数。 定理定理1给出了哈密尔顿图的一个必要条件，但它不是哈密尔顿给出了哈密尔顿图的一个必要条件，但它不是哈密尔顿图充分条件，我们常用它来判定一个图不是哈密尔顿图。图充分条件，我们常用它来判定一个图不是哈密尔顿图。例例. . 在下图中，在在下图中，在(1)中令中令V1=1,7，删除，删除V1中的两个结点后得图中的两个结点后得图(4)；此；此时，由于时，由于 V1 = 2，p(G - V1) =3， p(G - V1) V1 不成立，故不成立，故(1)不是不是哈密尔顿图。哈密尔顿图。 在在(2)中令中令V1=2，删除，删除V1中的一个结点后得图中的一个结点后得图(5)

16、；由于；由于 V1 =1， p(G - V1) =2，显然显然 p(G - V1) V1 不成立，故不成立，故(2)不是哈密尔顿图不是哈密尔顿图。 (3)图称为彼得森图。不难看出，删除其中任意一个或两个结点，剩下的图图称为彼得森图。不难看出，删除其中任意一个或两个结点，剩下的图仍连通；删除任意三个结点后，剩下的图至多被分成两个分支；删除任仍连通；删除任意三个结点后，剩下的图至多被分成两个分支；删除任意四个结点后，剩下的图至多被分成三个分支；删除五个以上的结点后，意四个结点后，剩下的图至多被分成三个分支；删除五个以上的结点后，剩下的图的结点数将小于等于剩下的图的结点数将小于等于5，其连通分支数自

17、然不会超过，其连通分支数自然不会超过5。所以，。所以，对彼得森图对彼得森图G= 来说，对来说，对V的任意非空子集的任意非空子集V1 ，都有，都有p(G - V1) V1 ，定理定理1的条件是满足的。但是，的条件是满足的。但是，彼得森图是一个典型的非哈密彼得森图是一个典型的非哈密尔顿图（用穷举法可证明其中不存在哈密尔顿回路）。尔顿图（用穷举法可证明其中不存在哈密尔顿回路）。2. 充分条件充分条件定理定理2 设设G=是结点个数是结点个数n 22的无向简单图，如果的无向简单图，如果G中每对结点中每对结点u, v都满足都满足 d(u)+ d(v)n n，则则G是哈密尔顿图。是哈密尔顿图。定理定理3 3

18、 设设G=是结点个数是结点个数n 22的无向简单图，如果的无向简单图，如果G中每对结中每对结点点u, v都满足都满足 d(u)+ d(v)n n -1-1，则则G是半哈密尔顿图。是半哈密尔顿图。 上述定理中的前提条件是不可少的。如下图中，上述定理中的前提条件是不可少的。如下图中，(1 1) 的每对结点的每对结点u u, v v的度数之和都的度数之和都44，满足定理，满足定理2 2中的条件，但中的条件，但(1)(1)显然不是哈密尔顿图，显然不是哈密尔顿图，这是因为该图不是无向图的缘故；而满足定理这是因为该图不是无向图的缘故；而满足定理2 2的条件的图的条件的图(2)(2)也不是哈也不是哈密尔顿图

19、，则是因为它不是简单图的原因。密尔顿图，则是因为它不是简单图的原因。 另外，定理另外，定理2 2 给出的条件只是哈密尔顿图的充分条件，但不是必要给出的条件只是哈密尔顿图的充分条件，但不是必要条件。如下图，该图是哈密尔顿图，但它并不满足定理条件。如下图，该图是哈密尔顿图，但它并不满足定理2 2的条件。的条件。 利用哈密尔顿图的概念和结论，可以帮助我们解决实际中的许利用哈密尔顿图的概念和结论，可以帮助我们解决实际中的许多问题。多问题。例例. 某次会议有某次会议有20人参加，其中每个人都至少有人参加，其中每个人都至少有10个朋友。当这个朋友。当这20人人围一圆桌入席时，要想使与每个人相邻的两位都是他

20、的朋友，是否有围一圆桌入席时，要想使与每个人相邻的两位都是他的朋友，是否有可能？可能？ 解：可能。首先构造图解：可能。首先构造图G，其中用一个结点代表一个参会人员，如果，其中用一个结点代表一个参会人员，如果两人是朋友，就将代表此二人的结点用一条边连接。根据已知情况，两人是朋友，就将代表此二人的结点用一条边连接。根据已知情况，G是个含有是个含有n =20个结点的无向简单图。个结点的无向简单图。 又由于每个人都至少有又由于每个人都至少有10个朋友，所以个朋友，所以G中每个结点的度都不小中每个结点的度都不小于于10，从而任意两个结点的度数之和都不小于，从而任意两个结点的度数之和都不小于10+10=2

21、0。因此，。因此，G满满足定理足定理2的条件，它是个哈密尔顿图。的条件，它是个哈密尔顿图。 设设L是是G中的任何一条哈密尔顿回路（必存在），然后按照各人中的任何一条哈密尔顿回路（必存在），然后按照各人在在L中的次序来安排他们的座席，即可得到一种满足要求的入席方案。中的次序来安排他们的座席，即可得到一种满足要求的入席方案。例例. 某学校要为七门课程安排考试。考试日程要求满足以下条件：所某学校要为七门课程安排考试。考试日程要求满足以下条件：所有课程须在连续的七天内完成；每天只能安排一门课程；同一位教师有课程须在连续的七天内完成；每天只能安排一门课程；同一位教师所担任的课程不能安排在连续的两天中。所

22、担任的课程不能安排在连续的两天中。 证明如果没有教师担任的课证明如果没有教师担任的课程数超过程数超过4门，门， 则符合上述要求的考试日程总是可能的。则符合上述要求的考试日程总是可能的。证明：构造图证明：构造图G，其中每个结点对应一门考试课程，如果两个结点对，其中每个结点对应一门考试课程，如果两个结点对应的考试课程是由不同的教师担任的，就将这两结点连一条边。因为应的考试课程是由不同的教师担任的，就将这两结点连一条边。因为每个教师所担任的课程都不超过每个教师所担任的课程都不超过4门，故每个结点的度都大于等于门，故每个结点的度都大于等于3，即任意两个结点的度数之和都大于等于即任意两个结点的度数之和都

23、大于等于6。由定理。由定理3 3知，知，G中必存在哈中必存在哈密尔顿通路。按这条哈密尔顿通路来安排，就可以得到符合要求的考密尔顿通路。按这条哈密尔顿通路来安排，就可以得到符合要求的考试日程。试日程。7.3 二部图二部图 一、问题的提出一、问题的提出 在现实生活和工作中，经常需要将两个集合中的对象进行在现实生活和工作中，经常需要将两个集合中的对象进行搭配，这些搭配成对的对象可以是两类对象，也可以是同一类搭配，这些搭配成对的对象可以是两类对象，也可以是同一类对象。比如，学校给教师安排课程、单位领导给其部属分派任对象。比如，学校给教师安排课程、单位领导给其部属分派任务、民政部门给新婚夫妇登记结婚、航

24、空旅行时飞机旅客与飞务、民政部门给新婚夫妇登记结婚、航空旅行时飞机旅客与飞机座位的配对、舞会上某时刻的舞伴安排等，都面临搭配问题机座位的配对、舞会上某时刻的舞伴安排等，都面临搭配问题的解决。图论中从最基本的概念出发，逐步构造出二部图、匹的解决。图论中从最基本的概念出发，逐步构造出二部图、匹配等描述和解决搭配问题的有效方法。配等描述和解决搭配问题的有效方法。 二、定义二、定义1. 1. 二部图的概念二部图的概念定义：设定义：设G=是无向简单图，如果能将结点集合是无向简单图，如果能将结点集合V划分成划分成V1 和和V2，并且使，并且使G中的每条边的两个端点，一个在中的每条边的两个端点，一个在V1中

25、，另一中，另一个在个在V2中，则称中，则称G是个二部图，并称是个二部图，并称V1 , ,V2是是G的互补点集。的互补点集。 二部图二部图G=有时记为有时记为G=。 例例. 在下面的图中，（在下面的图中，（1），（），（3），（），（4）是二部图，（）是二部图，（2）不是二部）不是二部图。图。 请读者自己写出（请读者自己写出（1），（），（3），（），（4）的互补点集。）的互补点集。 （1） （2） （3） （4） 一般，画一个二部图的图形时，常以分层的形式画出。如上例一般，画一个二部图的图形时，常以分层的形式画出。如上例的图中，（的图中，（1），（），（3），（），（4）分别画成图）分别画成图

26、7.10中的（中的（a），（），（b），），（c）。）。 （a） （b） （c）2. 2. 完全二部图完全二部图定义定义：对二部图对二部图G=，如果，如果V1中每个结点都与中每个结点都与V2中的所有中的所有结点相邻，则称结点相邻，则称G是完全二部图。是完全二部图。 特别地，如果特别地，如果V1和和V2中分别含有中分别含有n个结点和个结点和m个结点，则完全二个结点，则完全二部图部图G记为记为Kn, m。 显然，显然，Kn, m与与Km, n互相是同构的。互相是同构的。 例例. 下图中给出了完全二部图下图中给出了完全二部图K3, 3和和K2, 3，其中，其中K3, 3在讨论平面图在讨论平面图的时候

27、非常有用。的时候非常有用。 K3, 3 K2, 3 二、判定问题二、判定问题定理定理1 对任何无向简单图对任何无向简单图G=，有，有G是二部图当且仅当是二部图当且仅当G中不含长中不含长度为奇数的回路。度为奇数的回路。证明：先证充分性。证明：先证充分性。 设设G是二部图，则它必可以按分层形式画出。因为从任何一个结点出是二部图，则它必可以按分层形式画出。因为从任何一个结点出发的通路要回到出发点，必须刚好经过偶数条边，所以发的通路要回到出发点，必须刚好经过偶数条边，所以G中的任何一条回中的任何一条回路的长度都是偶数，亦即路的长度都是偶数，亦即G中不含长度为奇数的回路。中不含长度为奇数的回路。 再证必

28、要性（用反证法）。再证必要性（用反证法）。 设设G中不含长度为奇数的回路，则中不含长度为奇数的回路，则G中的任何一条回路的长度都是偶中的任何一条回路的长度都是偶数。数。 下面分两种情况来考虑：下面分两种情况来考虑： 如果如果G是连通图，则找出是连通图，则找出G中一条经过每个结点的回路中一条经过每个结点的回路L，在，在L上任上任取一个结点，将它放入取一个结点，将它放入V1中，然后沿着中，然后沿着L向外依次取结点来考察。若考察向外依次取结点来考察。若考察的结点在的结点在V1或或 V2中已存在，就跳过它；若考察的结点在中已存在，就跳过它；若考察的结点在V1或或 V2中不存在，中不存在，就将它放入就将

29、它放入V1或或 V2中（在确保同一集合中的点互不相连的前提下）。这中（在确保同一集合中的点互不相连的前提下）。这样一直做下去，直到每个结点都已放入样一直做下去，直到每个结点都已放入V1或或 V2中。此时的中。此时的 V1， V2就是就是G的互补点集。的互补点集。 如果如果G不是连通图，则不是连通图，则G的每个连通分支中的每条回路的长度也都的每个连通分支中的每条回路的长度也都是偶数。是偶数。 在每个连通分支里，在每个连通分支里， 类似第一种情况的处理方法，将其中的结类似第一种情况的处理方法，将其中的结点可以逐个放入点可以逐个放入V1或或 V2中，并使中，并使V1， V2成为成为G的互补点集。的互

30、补点集。 综合综合，所以，所以G是二部图。是二部图。推论：任何一个图，如果它含有不是二部图的子图，则它必定不推论：任何一个图，如果它含有不是二部图的子图，则它必定不是二部图。是二部图。 三、匹配的概念三、匹配的概念 1. 一般无向图中的匹配一般无向图中的匹配定义定义1 设有无向图设有无向图G=，若，若M是是E的非空子集，且的非空子集，且M中不存中不存在相邻的边，则称在相邻的边，则称M是是G中的一个匹配。与中的一个匹配。与M中的边关联的点称为中的边关联的点称为M饱和点。饱和点。 有了匹配的概念以后，还可以进一步定义图中的特殊匹配。有了匹配的概念以后，还可以进一步定义图中的特殊匹配。定义定义2 2

31、 设设M是无向图是无向图G=中的一个匹配，中的一个匹配， 若往若往M中添加任中添加任何一条新边后，何一条新边后，M就不是就不是G中的匹配了，则称中的匹配了，则称M是是G中的一个极大中的一个极大匹配；匹配；G中含有的边数最多的匹配称为中含有的边数最多的匹配称为G中的一个最大匹配。若中的一个最大匹配。若G中每个结点都是中每个结点都是M饱和点，则称饱和点，则称M是是G中的一个完美匹配。中的一个完美匹配。例例. . 在（在（1）中，）中，e1， e1，e7， e5， e4，e6等都是图中的匹等都是图中的匹配，其中配，其中 e1， e1，e7， e4，e6是极大匹配，是极大匹配， e1，e7， e4，e

32、6是最大匹配；图中不存在完美匹配。是最大匹配；图中不存在完美匹配。 在（在（2）中，）中， e2， e5， e3， e6， e1， e7， e4都是极大匹配，都是极大匹配，其中其中 e1， e7， e4是最大匹配，同时也是完美匹配。是最大匹配，同时也是完美匹配。 （1） （2）2. 二部图中的匹配二部图中的匹配定义定义3 3 设设G=是二部图，是二部图，M为为G中的一个匹配，若中的一个匹配，若M= minV1,V2，则称，则称M是是G中的一个完备匹配；此中的一个完备匹配；此时若时若V1V2，则称，则称M是从是从V1到到V2的一个完备匹配。若的一个完备匹配。若M还满足还满足M= V1=V2，则称

33、，则称M是是G中的一个完美匹配。中的一个完美匹配。例例. . 在下面的图中，在下面的图中， e e1 1，e e2 2 是（是（1 1）中的一匹配，但不是完备）中的一匹配，但不是完备匹配，更不是完美匹配。匹配，更不是完美匹配。 (1) (2) (3) 在（在（2）中，）中，e1，e2，e3是完备匹配，但不是完美匹配。是完备匹配，但不是完美匹配。在在（3）中，）中，e1，e2，e3是完美匹配，当然也是完备匹配。是完美匹配，当然也是完备匹配。 3. 完备匹配的存在性完备匹配的存在性定理定理2（Hall定理）定理） 设有二部图设有二部图G=，V1V2，则，则G中存在从中存在从V1到到V2 的完备匹配

34、当且仅当的完备匹配当且仅当V1中中任意任意k个结点（个结点（k=1, ,2, ,V1）至少邻接）至少邻接V2中的中的k个结点。个结点。 Hall定理给出了一个二部图中含有完备匹配的充分必要条件，定理给出了一个二部图中含有完备匹配的充分必要条件，其中的条件称为其中的条件称为 “相异性条件相异性条件”。除此以外，还有下面的充分条。除此以外，还有下面的充分条件。件。定理定理3 设有二部图设有二部图G=， V1 V2 ，如果存在一个，如果存在一个正整数正整数t，使，使 （1）V1中每个结点至少关联中每个结点至少关联t条边；条边； （2）V2中每个结点至多关联中每个结点至多关联t条边，条边， 则则G中必

35、存在从中必存在从V1到到V2的完备匹配。的完备匹配。 定理定理3中的条件称为中的条件称为“t条件条件”，它是二部图中含有完备匹配，它是二部图中含有完备匹配的充分条件，但不是必要条件。的充分条件，但不是必要条件。 例例 在下面的图中，图（在下面的图中，图（1）不满足相异性条件（）不满足相异性条件（u1, u2, u3中的中的u2和和u3两个点只关联两个点只关联 v1, v2, v3中的一个点中的一个点v2），所以（），所以（1）中不）中不存在从存在从u1, u2, u3到到v1, v2, v3的完备匹配。图（的完备匹配。图（2）满足相异性）满足相异性条件，所以其中存在从条件，所以其中存在从u1,

36、 u2, u3到到v1, v2, v3, v4的完备匹配。的完备匹配。图（图（3）也满足相异性条件，所以其中存在从）也满足相异性条件，所以其中存在从u1, u2, u3到到v1, v2, v3的完备匹配。的完备匹配。 特别地，图（特别地，图（3）不满足任何）不满足任何t条件，但它仍含有从条件，但它仍含有从u1, u2, u3到到v1, v2, v3的完备匹配，这说明的完备匹配，这说明t条件只是图中含有完备匹配的条件只是图中含有完备匹配的充分条件，而不是必要条件。充分条件，而不是必要条件。 （1） （2） （3） 例例. 现有现有4名教师：张、王、李、赵，要求安排他们去教名教师：张、王、李、赵，

37、要求安排他们去教4门课程：数门课程：数学、物理、电工和计算机科学。已知张能教数学和计算机科学；王能学、物理、电工和计算机科学。已知张能教数学和计算机科学；王能教物理和电工；李能教数学、物理和电工；而赵只能教电工。教物理和电工；李能教数学、物理和电工；而赵只能教电工。 问：如问：如何安排才能使何安排才能使4位教师都能教课，位教师都能教课， 并且每门可都有人教？共有几种方并且每门可都有人教？共有几种方案？案？解：设解：设V1=张，王，李，赵张，王，李，赵，V2=数学，物理，计算机科学，电工数学，物理，计算机科学，电工。若某人能教某门课程，就在相应的结点之间连一条边，得二部图如下若某人能教某门课程，

38、就在相应的结点之间连一条边，得二部图如下图所示。图所示。 此二部图满足此二部图满足“相异性条件相异性条件”，因而其中存在，因而其中存在V1到到V2的完备匹配的完备匹配（此匹配也是完美匹配）。但因赵只能教电工，因而王只能教物理，（此匹配也是完美匹配）。但因赵只能教电工，因而王只能教物理，李就只能教数学，最终张就只能教计算机科学了。即满足要求的方案李就只能教数学，最终张就只能教计算机科学了。即满足要求的方案只有一种。只有一种。 7.4 平面图平面图一、问题的提出一、问题的提出 图的可平面化问题，无论在关于图的理论上，还是在实际应用图的可平面化问题，无论在关于图的理论上，还是在实际应用中都具有重要意

39、义。它在印制电路板、集成电路的布线问题中，在中都具有重要意义。它在印制电路板、集成电路的布线问题中，在通讯、交通、城市建设等领域方面都有广泛的应用。本节将从图论通讯、交通、城市建设等领域方面都有广泛的应用。本节将从图论的角度讨论无向图的可平面性。的角度讨论无向图的可平面性。二、定义二、定义 1. 平面图的基本概念平面图的基本概念 （1）可平面图：能把所有结点和边画在平面上，且使任意两条）可平面图：能把所有结点和边画在平面上，且使任意两条边除端点外没有其它交点的无向图。可平面图有时简称为平面图。边除端点外没有其它交点的无向图。可平面图有时简称为平面图。 （2）平面嵌入：可平面图）平面嵌入：可平面

40、图G的画出的边不交叉的图形。的画出的边不交叉的图形。 显然，一个平面图可画出无穷多个形状不同的平面嵌入。显然，一个平面图可画出无穷多个形状不同的平面嵌入。 例例1. 在下面的图中，（在下面的图中，（1）、（）、（2）、（）、（5）是可平面图，其中）是可平面图，其中（1）的平面嵌入就是自身，（）的平面嵌入就是自身，（2）和（）和（5）的一个平面嵌入分别是）的一个平面嵌入分别是（6）和（）和（7）。（）。（3）即）即K3，3图，（图，（4）即）即K5图，它们都是非平面图。图，它们都是非平面图。这两个非平面图是这两个非平面图是“最小的最小的”的非平面图，它们在考察一个无向图的非平面图，它们在考察一个

41、无向图的可平面化问题时占有非常重要的地位。的可平面化问题时占有非常重要的地位。 显然，若一个无向图显然，若一个无向图G是可平面图，则它的每个连通分支都是可是可平面图，则它的每个连通分支都是可平面图；若平面图；若G是一个平面嵌入图形，则它的每个连通分支也都是平面是一个平面嵌入图形，则它的每个连通分支也都是平面嵌入图形。嵌入图形。2.2. 平面图的面平面图的面 设设G是一个连通的平面图，则是一个连通的平面图，则G的边将的边将G所在的平面划分成若干个所在的平面划分成若干个连通区域，每个连通区域连通区域，每个连通区域R称为称为G的一个面。面积有限的面称为有限面，的一个面。面积有限的面称为有限面，面积无

42、限的面称为无限面。面积无限的面称为无限面。 每个平面图的面的数目必是有限的，并且其中有且仅有一个无限每个平面图的面的数目必是有限的，并且其中有且仅有一个无限面。另外，每个面面。另外，每个面R都是由都是由G中的一条回路围成的，这条回路称为该面中的一条回路围成的，这条回路称为该面的边界，边界的长度称为该面的次数，记为的边界，边界的长度称为该面的次数，记为deg( (R) )。如果两个面至少。如果两个面至少有一条公共边，就称这两个面是相邻的面。有一条公共边，就称这两个面是相邻的面。 例例2 在下面的图中，（在下面的图中，（1）共有）共有3个面个面R0，R1，R2，其中，其中R0是无是无限面，限面，R

43、1和和R2是有限面；是有限面； R0的边界为的边界为abcda，deg（R0）=4；R1的的边界为边界为acda，deg（R1）=3；R2的边界为的边界为abca， deg（R3）=3。 （2）共有）共有3个面个面R0，R1，R2，其中，其中R0是无限面，是无限面，R1和和R2是有是有限面；限面；R0的边界为的边界为 abdefgeda ，deg（R0）=8；R1的边界为的边界为abdaca，deg（R1）=5；R2的边界为的边界为 efge， deg（R3）=3。 （1 1） （2 2）三、三、 平面图的性质平面图的性质1. 面数与边数的关系面数与边数的关系定理定理1 任何一个平面图中，所有

44、面的次数之和等于边数的两倍。任何一个平面图中，所有面的次数之和等于边数的两倍。证明：平面图证明：平面图G G的每条边，如果它在两个面的边界中各出现一次，则在的每条边，如果它在两个面的边界中各出现一次，则在计算计算G的各面次数之和时，这条边被计算两次；如果它只在一个面的边的各面次数之和时，这条边被计算两次；如果它只在一个面的边界中出现，在计算该面的次数时，也被计算了两次。因此，所有面的次界中出现，在计算该面的次数时，也被计算了两次。因此，所有面的次数之和必等于边数的两倍。数之和必等于边数的两倍。 2.2.欧拉公式欧拉公式定理定理2 2 设设G= 是含有是含有n个结点，个结点，m条边，条边，r个面

45、的连通的平面图，个面的连通的平面图，则必有则必有 n m + r = 2 直接应用定理直接应用定理2，可得下列推论。，可得下列推论。推论推论1 任一给定的连通平面图任一给定的连通平面图G的所有平面嵌入都有相同的面数。的所有平面嵌入都有相同的面数。推论推论2 若若G是结点数是结点数n 3的简单连通平面图，则的简单连通平面图，则m 3 n 6 。 利用推论利用推论2可以判定某些图不是平面图，只须说明它满足推论可以判定某些图不是平面图，只须说明它满足推论2的前的前提条件，但使提条件，但使m 3 n 6不成立就可以了。不成立就可以了。 例例3 求证求证K5不是平面图。不是平面图。证明：显然，证明：显然

46、，K5是结点数是结点数n 33的的简单连通图，且简单连通图，且n=5，m=10。若。若K5是平面图，则由推论是平面图，则由推论7.10.2，有，有m 3 3 n 6 6，即即1035-61035-6，亦即，亦即109109，矛盾。，矛盾。例例4 求证求证 K3，3不是平面图。不是平面图。证明：证明：K3，3是结点数是结点数n 33的的简单连通图，且简单连通图，且n=6，m=9。 设设K3，3是平面图，是平面图， 因为因为K3，3中每个回路的长度都不小于中每个回路的长度都不小于4，故有故有4r 22 m =18，即，即r44。由欧拉公式有。由欧拉公式有 2 =2 = n m + r 6 9 +

47、4 = 1 6 9 + 4 = 1 ，矛盾。，矛盾。四、图的可平面性四、图的可平面性 首先介绍对图的一种操作方法首先介绍对图的一种操作方法-初等收缩。初等收缩。 定义：对一个无向简单图定义：对一个无向简单图G，删除掉，删除掉G中的一条边（中的一条边（vi，vj），并将该），并将该边的两个端边的两个端vi，vj合并成一个点合并成一个点w，这样的操作称为对，这样的操作称为对G进行了一次初等进行了一次初等收缩。收缩。 对对G进行了若干次初等收缩得到的图称为进行了若干次初等收缩得到的图称为G的初等收缩图。的初等收缩图。 例例5 在下面图中，将（在下面图中，将（1）中的边（）中的边（1，2）删除，两端点

48、合并成）删除，两端点合并成w1，即得（即得（2）；将（）；将（2）中的边（）中的边（3，4）删除，两端点合并成）删除，两端点合并成w2，即得，即得（3）。（）。（2）和（）和（3）都是（）都是（1）的初等收缩图，同时（）的初等收缩图，同时（3）也是（）也是（2）的初等收缩图。的初等收缩图。 （1） （2） （3） 下面给出判定图的可平面性的最重要的一个结论。下面给出判定图的可平面性的最重要的一个结论。 定理定理3 3（库拉托夫斯基定理）（库拉托夫斯基定理） 一个图一个图G是平面图，当且仅当它没有可以初等收缩成是平面图，当且仅当它没有可以初等收缩成K5 或或K3,3的子图。的子图。 库拉托夫斯基

49、定理的另一个等价描述是：一个图库拉托夫斯基定理的另一个等价描述是：一个图G是是非平面图，当且仅当它含有可以初等收缩成非平面图，当且仅当它含有可以初等收缩成K K5 5 或或K K3 3, 3 3的子的子图。图。 下面举例判定图的可平面性。下面举例判定图的可平面性。 例例6 判断下图中的（判断下图中的（1）图与（）图与（2）图的可平面性。）图的可平面性。 （1） （2） 解：对图（解：对图（1），依次删除边），依次删除边e1, e2, e3, e4, e5，端点分别合并为，端点分别合并为w1, w2, w3, w4, w5，得（，得（1）的一个初等收缩图见下图中的（）的一个初等收缩图见下图中的（

50、a）。此图即）。此图即K5，所以，所以（1）图是个非平面图。）图是个非平面图。 对图（对图（2），因为它含有子图（见下图中的（），因为它含有子图（见下图中的（b），此图即），此图即K3,3，所，所以（以（2）图是个非平面图。）图是个非平面图。 （a a） （b b） 7.5 无向树无向树7.5.1 7.5.1 无向树的概念及性质无向树的概念及性质一、无向树的概念一、无向树的概念 1.无向树：连通且不含简单回路的无向图。无向树：连通且不含简单回路的无向图。 2.树叶：无向树中的度为树叶：无向树中的度为1的结点。的结点。 3.分支点：无向树中度大于分支点：无向树中度大于1的结点。的结点。 4.树枝

51、：无向树中的边。树枝：无向树中的边。 5.无向森林：每个连通分支都是无向树的图。无向森林：每个连通分支都是无向树的图。 6.平凡树：平凡图是无向树，称为平凡树。平凡树：平凡图是无向树，称为平凡树。例例1 在下图中，（在下图中，（1）是无向树，其中含有）是无向树，其中含有4片树叶，片树叶，7根树枝。（根树枝。（1）同时也是一片森林，同时也是一片森林， 是由一棵树组成的森林。是由一棵树组成的森林。 （2）不是无向树（因）不是无向树（因为它不是连通图），但是是森林，为它不是连通图），但是是森林， 是由两棵树组成的森林。（是由两棵树组成的森林。（3）不）不是无向树（因为是无向树（因为 其中含有简单回路

52、），也不是森林。其中含有简单回路），也不是森林。 （1） （2） （3）二、无向树的性质二、无向树的性质定理定理1 对任何一个含有对任何一个含有n个结点，个结点，m条边的无向图条边的无向图G=，下，下列命题互相等价。列命题互相等价。 （1）G是无向树。是无向树。 （2）G不含简单回路且连通。不含简单回路且连通。 （3）G不含简单回路，且不含简单回路，且n=m+1。 （4）G连通，且连通，且n=m+1。 （5）G中不含简单回路，但往中不含简单回路，但往G中添加任何一条新边后，将中添加任何一条新边后，将出现一条简单回路。出现一条简单回路。 （6）G连通，但删除连通，但删除G中的任何一条边后，将变成

53、一个非连中的任何一条边后，将变成一个非连通图。通图。 （7）G的任何一对结点之间，有且仅有一条简单通路。的任何一对结点之间，有且仅有一条简单通路。 定理定理2 2 任何一棵非平凡的无向树中至少含有两片树叶。任何一棵非平凡的无向树中至少含有两片树叶。 7.5.2 最小生成树最小生成树 无向树的直接应用，就是最小生成树。无向树的直接应用，就是最小生成树。一、生成树一、生成树 1. 生成树的概念生成树的概念定义：定义： （1）若无向图）若无向图G的生成子图是无向树，则称该无向树为的生成子图是无向树，则称该无向树为G的一的一棵生成树。棵生成树。 （2）设）设T是无向图是无向图G的一棵生成树，则的一棵生

54、成树，则G的在的在T中存在的边称为中存在的边称为T的的树枝，树枝，G的不在的不在T中存在的边称为中存在的边称为T的弦。所有弦组成的集合称为的弦。所有弦组成的集合称为T的补。的补。 例如，在下面的图中，（例如，在下面的图中，（2）是（）是（1）的一棵生成树，）的一棵生成树，e2, e3, e4, e5, e8 是是该生成树的树枝，该生成树的树枝，e1, e6, e7是该生成树弦，是该生成树弦，e1, e6, e7是该生成树补。是该生成树补。 （1） （2） 2. 生成树的存在性生成树的存在性定理定理3 3 对任何一个无向图对任何一个无向图G，其中含有生成树，当且仅当，其中含有生成树，当且仅当G是

55、是连通图。连通图。证明：先证充分性证明：先证充分性 设设T是无向图是无向图G的一棵生成树，则的一棵生成树，则T是一个连通图，因而是一个连通图，因而T中中任意两结点之间都有通路。任意两结点之间都有通路。 又由于又由于T是是G的生成子图，的生成子图， 其中含有其中含有G的所有结点，并且每条边都是的所有结点，并且每条边都是G的边，所以，的边，所以，G的任意两结点的任意两结点之间都有通路，即之间都有通路，即G是个连通图。是个连通图。 再证必要性再证必要性 设设G是连通图。若是连通图。若G中无简单回路，则中无简单回路，则G本身是无向树；又本身是无向树；又因为每个图都是自身的生成子图，所以因为每个图都是自

56、身的生成子图，所以G就是就是G的生成树。若的生成树。若G中有简单回路，就任意找出一条来，删除这条回路上的任意一中有简单回路，就任意找出一条来，删除这条回路上的任意一条边，此时剩下的图仍是连通的。重复上述操作，直到不再含条边，此时剩下的图仍是连通的。重复上述操作，直到不再含有简单回路为止，就可以得到有简单回路为止，就可以得到G的一棵生成树。的一棵生成树。 二、最小生成树二、最小生成树1. 带权图带权图 在一个无向图在一个无向图G中，用一个正实数中，用一个正实数表示边表示边e e的的“长度长度”，称为边，称为边e e所带的权。所带的权。 如果如果G的每条边都带权，就称的每条边都带权，就称G是一个带

57、权图。是一个带权图。 在实际中不同的带权图里，权的含义不尽相同。例如，根据一个图在实际中不同的带权图里，权的含义不尽相同。例如，根据一个图描述的系统情况，图中的边的权值可以用来表示公路里程、票价（费描述的系统情况，图中的边的权值可以用来表示公路里程、票价（费用）、运行时间、最大车流量、收益等度量指标。用）、运行时间、最大车流量、收益等度量指标。 有时，还需要汇总一有时，还需要汇总一个系统的总度量，这在图论中用带权图的图权来概况。个系统的总度量，这在图论中用带权图的图权来概况。2. 图权图权 设设G是一个带权图，称图中所有边的权和为是一个带权图，称图中所有边的权和为G的图权，记为的图权，记为W（

58、G）。）。 从生成树和带权图的定义可知，连通的带权图的任何生成树仍是带从生成树和带权图的定义可知，连通的带权图的任何生成树仍是带权图。权图。3. 3. 最小生成树最小生成树（1）定义）定义 设设G是一个带权连通图，在是一个带权连通图，在G的所有生成树中，图权最小的的所有生成树中，图权最小的那一棵称为那一棵称为G 的最小生成树。的最小生成树。（2）最小生成树求法）最小生成树求法定理定理4 4 对任何带权连通图对任何带权连通图G，通过下述步骤可求出它的一棵最小生成树，通过下述步骤可求出它的一棵最小生成树，但不唯一。但不唯一。 第第1步步 将将G中的边按权作非降序排列，记为中的边按权作非降序排列，记

59、为E。 第第2步步 画出画出G的每个结点，记为的每个结点，记为T。 第第3步步 取取E中第一条边中第一条边e来考察。若将来考察。若将e加入加入T中不会出现简单回路，中不会出现简单回路， 就将此边加入就将此边加入T中，然后转中，然后转；若会出现简单回路，则；若会出现简单回路，则 直接转直接转。 第第4步步 在在E中删除中删除e。 第第5步步 若若T已是连通图，则已是连通图，则T就是要求的最小生成树；否则转就是要求的最小生成树；否则转。 例例2 2 用用Kruskal算法求出下图的一棵最小生成树。算法求出下图的一棵最小生成树。 解：解：Kruskal 算法的求解过程见下图。算法的求解过程见下图。

60、7.6 根树根树7.6.1 根树的概念根树的概念 一、定义一、定义 1. 有向树：看作无向图时它是一棵无向树的有向图。有向树：看作无向图时它是一棵无向树的有向图。2.根树：满足下述两条件的有向树。根树：满足下述两条件的有向树。（1）其中有且仅有一个入度为）其中有且仅有一个入度为0的结点；的结点；（2）其它每个结点的入度都为）其它每个结点的入度都为1。3.树根：根树中，入度为树根：根树中，入度为0的那个结点。的那个结点。4.树叶：出度为树叶：出度为0的结点称为树叶。的结点称为树叶。5.内点：出度大于内点：出度大于1的非根结点。的非根结点。6.分枝点：所有内点和根的统称。分枝点：所有内点和根的统称