第七章 图与树.ppt

《第七章 图与树.ppt》由会员分享，可在线阅读，更多相关《第七章 图与树.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、欧拉简介欧拉简介 欧拉（欧拉（LeonhardEuler公元公元1707-1783年）年）1707年出生在瑞士的巴塞尔（年出生在瑞士的巴塞尔（Basel）城，）城，13岁岁就进巴塞尔大学读书，就进巴塞尔大学读书，15毕业，毕业，16获得硕士学位，得到当时最有名的数学家约翰获得硕士学位，得到当时最有名的数学家约翰伯努伯努利的精心指导，欧拉是有名的数学家和自然科学家。利的精心指导，欧拉是有名的数学家和自然科学家。欧拉从欧拉从19岁开始发表论文，直到岁开始发表论文，直到76岁，据统计他那不倦的一生，共写下了岁，据统计他那不倦的一生，共写下了886本书籍和论文，本书籍和论文，其中分析、代数、数论占其中

2、分析、代数、数论占40%，几何占，几何占18%，物理和力学占，物理和力学占28%，天文学占，天文学占11%，弹道，弹道学、航海学、建筑学等占学、航海学、建筑学等占3%，彼得堡科学院为了整理他的著作，足足忙四十七年。，彼得堡科学院为了整理他的著作，足足忙四十七年。1725年约翰年约翰伯努利的儿子丹尼尔伯努利的儿子丹尼尔伯努利赴俄国，并向沙皇喀德林一世推荐了伯努利赴俄国，并向沙皇喀德林一世推荐了欧拉，这样，在欧拉，这样，在1727年年5月月17日欧拉来到了彼得堡。日欧拉来到了彼得堡。1733年，年仅年，年仅26岁的欧拉岁的欧拉担任了彼得堡科学院数学教授。担任了彼得堡科学院数学教授。1735年，欧拉

3、解决了一个天文学的难题（计算年，欧拉解决了一个天文学的难题（计算慧星轨道），这个问题经几个著名数学家几个月的努力才得到解决，而欧拉却慧星轨道），这个问题经几个著名数学家几个月的努力才得到解决，而欧拉却用自己发明的方法，三天便完成了。然而过度的工作使他得了眼病，并且不幸用自己发明的方法，三天便完成了。然而过度的工作使他得了眼病，并且不幸右眼失明了，这时他才右眼失明了，这时他才28岁。岁。1741年欧拉应普鲁士彼德烈大帝的邀请，到柏林年欧拉应普鲁士彼德烈大帝的邀请，到柏林担任科学院物理数学所所长，直到担任科学院物理数学所所长，直到1766年，后来在沙皇喀德林二世的诚恳敦聘年，后来在沙皇喀德林二世的

4、诚恳敦聘下重回彼得堡，不料没有多久，左眼视力衰退，最后完全失明。不幸的事情接下重回彼得堡，不料没有多久，左眼视力衰退，最后完全失明。不幸的事情接踵而来，踵而来，1771年彼得堡的大火灾殃及欧拉住宅，带病而失明的年彼得堡的大火灾殃及欧拉住宅，带病而失明的64岁的欧拉被围岁的欧拉被围困在大火中，虽然他被别人从火海中救了出来，但他的书房和大量研究成果全困在大火中，虽然他被别人从火海中救了出来，但他的书房和大量研究成果全部化为灰烬了。部化为灰烬了。在他完全失明之前，还能朦胧地看见东西，他抓紧这最后的时刻，在一块大黑板上疾书他发现在他完全失明之前，还能朦胧地看见东西，他抓紧这最后的时刻，在一块大黑板上疾

5、书他发现的公式，然后口述其内容，由他的学生特别是大儿子的公式，然后口述其内容，由他的学生特别是大儿子A欧拉（数学家和物理学家）笔录。欧拉（数学家和物理学家）笔录。欧拉完全失明以后，仍然以惊人的毅力与黑暗搏斗，凭着记忆和心算进行研究，直到逝世，欧拉完全失明以后，仍然以惊人的毅力与黑暗搏斗，凭着记忆和心算进行研究，直到逝世，竟达竟达17年之久。年之久。欧拉的记忆力和心算能力是罕见的，他能够复述年青时代笔记的内容，心算并不限于简单的运欧拉的记忆力和心算能力是罕见的，他能够复述年青时代笔记的内容，心算并不限于简单的运算，高等数学一样可以用心算去完成。有一个例子足以说明他的本领，欧拉的两个学生把算，高等

6、数学一样可以用心算去完成。有一个例子足以说明他的本领，欧拉的两个学生把一个复杂的收敛级数的一个复杂的收敛级数的17项加起来，算到第项加起来，算到第50位数字，两人相差一个单位，欧拉为了确定位数字，两人相差一个单位，欧拉为了确定究竟谁对，用心算进行全部运算，最后把错误找了出来。欧拉在失明的究竟谁对，用心算进行全部运算，最后把错误找了出来。欧拉在失明的17年中；还解决了年中；还解决了使牛顿头痛的月离问题和很多复杂的分析问题。使牛顿头痛的月离问题和很多复杂的分析问题。欧拉的风格是很高的，拉格朗日是稍后于欧拉的大数学家，从欧拉的风格是很高的，拉格朗日是稍后于欧拉的大数学家，从19岁起和欧拉通信，讨论等

7、周问岁起和欧拉通信，讨论等周问题的一般解法，这引起变分法的诞生。等周问题是欧拉多年来苦心考虑的问题，拉格朗日题的一般解法，这引起变分法的诞生。等周问题是欧拉多年来苦心考虑的问题，拉格朗日的解法，博得欧拉的热烈赞扬，的解法，博得欧拉的热烈赞扬，1759年年10月月2日欧拉在回信中盛称拉格朗日的成就，并谦虚日欧拉在回信中盛称拉格朗日的成就，并谦虚地压下自己在这方面较不成熟的作品暂不发表，使年青的拉格朗日的工作得以发表和流传，地压下自己在这方面较不成熟的作品暂不发表，使年青的拉格朗日的工作得以发表和流传，并赢得巨大的声誉。他晚年的时候，欧洲所有的数学家都把他当作老师，著名数学家拉普并赢得巨大的声誉。

8、他晚年的时候，欧洲所有的数学家都把他当作老师，著名数学家拉普拉斯（拉斯（Laplace）曾说过：）曾说过：欧拉是我们的导师。欧拉是我们的导师。欧拉充沛的精力保持到最后一刻，欧拉充沛的精力保持到最后一刻，1783年年9月月18日下午，欧拉为了庆祝他计算气球上升定律的成功，请朋友们吃饭，那时天王星刚发日下午，欧拉为了庆祝他计算气球上升定律的成功，请朋友们吃饭，那时天王星刚发现不久，欧拉写出了计算天王星轨道的要领，还和他的孙子逗笑，喝完茶后，突然疾病发现不久，欧拉写出了计算天王星轨道的要领，还和他的孙子逗笑，喝完茶后，突然疾病发作，烟斗从手中落下，口里喃喃地说：作，烟斗从手中落下，口里喃喃地说：我死

9、了我死了，欧拉终于，欧拉终于停止了生命和计算停止了生命和计算。欧拉的一生，是为数学发展而奋斗的一生，他那杰出的智慧，顽强的毅力，孜孜不倦的奋斗欧拉的一生，是为数学发展而奋斗的一生，他那杰出的智慧，顽强的毅力，孜孜不倦的奋斗精神和高尚的科学道德，永远是值得我们学习的。欧拉还创设了许多数学符号，例如精神和高尚的科学道德，永远是值得我们学习的。欧拉还创设了许多数学符号，例如（1736年），年），e（1748年），年），sin和和cos（1748年），年），tg（1753年），年），x（1755年），年），（1755年），年），f(x)（1734年）等。年）等。图论起源：图论起源：哥尼斯堡七桥问题哥尼

10、斯堡七桥问题在在18世纪世纪,普鲁士的哥尼斯堡镇被普雷格尔河分成普鲁士的哥尼斯堡镇被普雷格尔河分成4个部分。个部分。包括河两岸、中心岛以及两条支流之间所夹的部分包括河两岸、中心岛以及两条支流之间所夹的部分,河上建有河上建有7座桥连接着小镇的座桥连接着小镇的4部分。部分。第七章第七章图论基础图论基础7.1 图的基本概念图的基本概念 一、图的定义及有关术语一、图的定义及有关术语1、图的定义、图的定义图是二元组图是二元组G=,其中其中V是节点集合，是节点集合，E是边集合。是边集合。2、专业术语专业术语无向边，有向边，平行边，自回路（环，其边的方向没有意义），邻接无向边，有向边，平行边，自回路（环，其

11、边的方向没有意义），邻接点，邻接边，孤立点，点，邻接边，孤立点，3、图的分类、图的分类有向图、无向图和混合图，简单图（不含平行边，自回路），完全图（每有向图、无向图和混合图，简单图（不含平行边，自回路），完全图（每对节点之间有边相连）多重图（含平行边），边权图与点权图，平凡对节点之间有边相连）多重图（含平行边），边权图与点权图，平凡图（一个点）与零图（多个点，无边）图（一个点）与零图（多个点，无边）二、节点度二、节点度1、节点度定义、节点度定义deg(vi)表示与节点表示与节点vi相关连的边的条数，其中含环节点度加相关连的边的条数，其中含环节点度加2。2、有向图节点度、有向图节点度节点入度：在

12、有向图中，射入一个节点的边数称为该节点入度，记为节点入度：在有向图中，射入一个节点的边数称为该节点入度，记为deg(vi)；节点出度：射出一个节点的边数为该节点的出度，记为节点出度：射出一个节点的边数为该节点的出度，记为deg+(vi)；节点度：节点度：deg(vi)=deg(vi)+deg+(vi)3、节点的最大度和最小度、节点的最大度和最小度4、定理定理Kn边的条数边的条数:|E|=n(n-1)/2其中其中n为节点数为节点数5、任何图中，度数为奇数的节点必定是偶数个。、任何图中，度数为奇数的节点必定是偶数个。三、补图与子图三、补图与子图1、补图定义补图定义设图设图G=，其补图，其补图，为把

13、，为把G变成完全图后所增加的边的变成完全图后所增加的边的集合。集合。2、子图定义、子图定义设图设图G=，如果有图，如果有图G=，其中，其中VV,EE，则，则称称G是是G的子图。其中，如果的子图。其中，如果V=V,EE，则称，则称G为为G的生的生成子图。成子图。7.2路、回路、图的连通性路、回路、图的连通性一、路与回路一、路与回路1、路定义、路定义 设设图图G=，v0,v1,vn,V,e0,e1,en,E,ei为为节节点点vi和和节节点点vi-1之之间间的的边边，交交替替序序列列v0e1v1e2envn，为为连连接接v0和和vn之之间间的的路路。其其中中v0为路的起点，为路的起点，vn为路的终点

14、。为路的终点。(1)回路回路如果如果v0vn，这条路称回路。，这条路称回路。(2)迹迹若一条路中所有边不同，则称为迹。若一条路中所有边不同，则称为迹。(3)通路若一条路中所有点不同，则称为通路。通路若一条路中所有点不同，则称为通路。(4)圈圈所有节点都不相同的回路叫圈。所有节点都不相同的回路叫圈。例例1v1到到v4的路：的路：v1e1v5e5v4，v1e2v2e6v3e4v42、可达、可达设图设图G=，若，若vi到到vj有路，有路，则称则称vi可达可达vj。二、图的连通性二、图的连通性connectedness1、无向图的连通性、无向图的连通性(1)节点连通性节点连通性(2)若节点若节点vi到

15、到vj有路节点有路（可达），则节点是连通的。有路节点有路（可达），则节点是连通的。例例2：无向图节点之间的连通关系是等价关系。：无向图节点之间的连通关系是等价关系。(2)把把无无向向图图节节点点划划分分成成若若干干非非空空子子集集V1,V2,Vk,称称子子图图G(V1),G(V2),G(Vk),是是原原图图G的的连连通通分分支支，令令W(G)为为原原图图的的连连通通分分支支数数。其其中中G只只有有一一个个连通分支，则图连通分支，则图G是连通图。是连通图。2有向图有向图(1)连通性连通性强连通强连通:在有向图在有向图G=中，如果任何一对节点之间相互可达，则该图中，如果任何一对节点之间相互可达，则

16、该图为强连通。为强连通。单侧连通单侧连通:若任意两个节点至少有一个可以到达，则称该图是单侧连通。若任意两个节点至少有一个可以到达，则称该图是单侧连通。弱连通弱连通:若该有向图去掉方向后仍然连通，则该图是弱连通。若该有向图去掉方向后仍然连通，则该图是弱连通。注：强连通必然单侧连通，单侧连通必然弱连通。注：强连通必然单侧连通，单侧连通必然弱连通。(2)有向图的分图有向图的分图强分图：最大的强连通子图。强分图：最大的强连通子图。单侧分图：最大的单侧连通子图。单侧分图：最大的单侧连通子图。弱分图：最大的弱连通子图。弱分图：最大的弱连通子图。例例2：强分图：强分图：v1,v2,v3,v4,v5,v6单侧

17、分图：单侧分图：v1,v2,v3,v4,v5,v6弱分图：弱分图：v1,v2,v3,v4,v5,v6(3)强连通性质强连通性质一个有向图是强连通的一个有向图是强连通的,当且仅当当且仅当G中有一个回路，它至少包含每个节点一次。中有一个回路，它至少包含每个节点一次。在一个有向图在一个有向图G=中，它的每个节点位于且只位于一个强分图中。中，它的每个节点位于且只位于一个强分图中。证明：设节点证明：设节点v在不同强分图在不同强分图S1和和S2中，则中，则S1中所有节点与中所有节点与v可以相互到达，可以相互到达，S2中所有节点与中所有节点与v可以相互到达，则可以相互到达，则S1和和S2中节点通过中节点通过

18、v可以相互到达。可以相互到达。三、无向图割集三、无向图割集1、点割集、点割集设无向联通图设无向联通图G=，若有，若有V1,V1 V，图，图G删除删除V1的所有节点后，所的所有节点后，所得子图不联通，删除得子图不联通，删除V1任何真子集后所得子图联通。其中任何真子集后所得子图联通。其中,|V1|=1,则该结则该结点称为割点。点称为割点。K(G)=min|Vi|,Vi是图点割集是图点割集为为G点的联通度。点的联通度。例例3：v1,v3 v3,v4 v1,v3,v4 K(G)=2例例4:2、边割集、边割集设无向联通图设无向联通图G=，若有，若有E1,E1 E，图，图G删除删除E1的所有节点后，所得的

19、所有节点后，所得子图不联通，删除子图不联通，删除E1任何真子集后所得子图联通。其中任何真子集后所得子图联通。其中,|E1|=1,则该边称为则该边称为割边或桥。割边或桥。(G)=min|Ei|,Ei是图边割集是图边割集为为G边的联通度。边的联通度。接上例接上例e6，e7e5，e7e1,e3,e8例例5:e4为割边，为割边，v3是割点，K(G)=17.3图的矩阵表示图的矩阵表示一、邻接矩阵一、邻接矩阵adjacencymatrix1、定义、定义设设G=是一个简单图，是一个简单图，V=v0,v1,vn，则，则n阶方阵：阶方阵：A(G)=(aij)nn为邻接矩阵。为邻接矩阵。例例1：求下图邻接矩阵（无

20、向图）：求下图邻接矩阵（无向图）A=例例2：求下图邻接矩阵（有向图）：求下图邻接矩阵（有向图）总结：总结：对于无向图，行或列中对于无向图，行或列中1的个数就是该点的度数；的个数就是该点的度数；对于有向图，行中对于有向图，行中1的个数是该节点的出度，列中的个数是该节点的出度，列中1的个数的个数是该节点的入度；是该节点的入度；简单无向图的邻接矩阵为对称的，有向图的邻接矩阵未必。简单无向图的邻接矩阵为对称的，有向图的邻接矩阵未必。2、应用、应用设设A(G)为图为图G的邻接矩阵，则的邻接矩阵，则(A(G)l中第中第i行，行，j列的元素列的元素(alij)等于等于G中连接中连接vi和和vj长度为长度为l

21、路的条数。路的条数。二、可达性矩阵二、可达性矩阵reachabilitymatrix1、定义、定义设设G=是是一一个个简简单单图图，V=v0,v1,vn，则则n阶阶方方阵阵P(G)=(pij)nn为为可达矩阵。其中：可达矩阵。其中：2、求法、求法(1)P=A+A1+A2An(2)对邻接矩阵用对邻接矩阵用warshall算法算法(3)例例3：P(G)=3、应用、应用（利用主对角线是否为（利用主对角线是否为1，判断图有无回路问题，判断图有无回路问题）OS判断死锁问题判断死锁问题设设4个进程，分别为个进程，分别为P1,P2,P3,P4,4种资源，种资源，R1,R2,R3,R4,在在t时刻，进时刻，进

22、程对资源的占有和申请情况如图所示。程对资源的占有和申请情况如图所示。P1拥有资源拥有资源R4，又去申请资源，又去申请资源R1P2拥有资源拥有资源R1，又去申请资源，又去申请资源R2P3拥有资源拥有资源R2，又去申请资源，又去申请资源R3P4拥有资源拥有资源R3，又去申请资源，又去申请资源R4递归调用递归调用设过程集合设过程集合P1,P2,P3,P4,P5调用关系为调用关系为P1调用调用P2P2调用调用P4P3调用调用P1P4调用调用P5P5调用调用P2 P=三、关联矩阵三、关联矩阵incidencematrix1、无向图的关联矩阵、无向图的关联矩阵设设G=是是一一个个简简单单无无向向图图，V=

23、v0,v1,vn，E=e0,e1,et,则则M(G)=(mij)nt为结点与边的关联矩阵。其中：为结点与边的关联矩阵。其中：例例4：M=性质：性质：边关联两个节点，所以边关联两个节点，所以M(G)中每一列只含两个中每一列只含两个1；每一行中元素的和对应该节点的度数；每一行中元素的和对应该节点的度数；一行中元素全为一行中元素全为0，则为孤立节点；，则为孤立节点；两个平行边其对应的两列相同两个平行边其对应的两列相同。2、有向图的关联矩阵、有向图的关联矩阵设设G=是是一一个个简简单单有有向向图图，V=v0,v1,vn，E=e0,e1,et,则则M(G)=(mij)nt为结点与边的关联矩阵。其中：为结

24、点与边的关联矩阵。其中：例例5：M=7.4欧拉图和汉密尔顿图欧拉图和汉密尔顿图一、一、欧拉图（欧拉图（E图）图）1、无向欧拉图、无向欧拉图(1)、定义、定义给定无孤立节点图给定无孤立节点图G，若存在一条路，经过图中每边一次且仅一次，该路称为欧，若存在一条路，经过图中每边一次且仅一次，该路称为欧拉路；若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路；拉路；若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路；具有欧拉回路的图称作欧拉图。具有欧拉回路的图称作欧拉图。(2)、判断、判断H路：无向图路：无向图G具有一条欧拉路，当且仅当具有一条欧拉路，当且仅当G是连通的，且只有两个奇

25、数度节点。是连通的，且只有两个奇数度节点。H回路：无向图回路：无向图G具有一条欧拉回路，当且仅当具有一条欧拉回路，当且仅当G是连通的，并且所有节点度数全是连通的，并且所有节点度数全为偶数。为偶数。(3)、应用、应用中国一笔画问题中国一笔画问题2、有向图欧拉路、有向图欧拉路(1)、定义、定义给定无孤立节点有向图给定无孤立节点有向图G，经过图中每边一次且仅一次的一条单向路，经过图中每边一次且仅一次的一条单向路(回路回路)，称为单向欧拉路，称为单向欧拉路(回路回路)。(2)、判断、判断有向图有向图G具有一条单向欧拉回路，当且仅当具有一条单向欧拉回路，当且仅当G是连通的，并且每节点的是连通的，并且每节

26、点的入度等于出度；具有一条单向欧拉路，当且仅当入度等于出度；具有一条单向欧拉路，当且仅当G是连通的，并且是连通的，并且有一个节点的入度比出度多一，还有一节点出度比入度多一，而其有一个节点的入度比出度多一，还有一节点出度比入度多一，而其余节点的入度等于出度。余节点的入度等于出度。(3)、应用、应用鼓风机设计问题鼓风机设计问题二、汉密尔顿图（二、汉密尔顿图（H图）图）1、定义、定义给定图给定图G，若存在一条路经过图中的每点恰好一次，这条路称作汉密尔顿路，若存在一条路经过图中的每点恰好一次，这条路称作汉密尔顿路，若存在一条回路经过图中的每点恰好一次，这回路称作汉密尔顿回路。若存在一条回路经过图中的每

27、点恰好一次，这回路称作汉密尔顿回路。2、判断、判断(1)、必要条件、必要条件若图若图G含有含有H回路，则对于结点回路，则对于结点V的每一个非空子集的每一个非空子集S均有均有W(G-S)|S|成立。成立。(2)、充分条件、充分条件设设G具有具有n个节点的简单图，如果个节点的简单图，如果G中每一对节点度数之和大于等于中每一对节点度数之和大于等于n，则在，则在G中存在一条汉密尔顿回路。中存在一条汉密尔顿回路。(充分条件充分条件)设设G具有具有n个节点的简单图，如果个节点的简单图，如果G中每一对节点度数之和大于等于中每一对节点度数之和大于等于n-1，则，则在在G中存在一条汉密尔顿路。中存在一条汉密尔顿

28、路。7.4平面图平面图planergraph一、一、基本概念基本概念1、定义、定义设设G=是一个无向图，如果能够把是一个无向图，如果能够把G的所有节点和边画在平面上，的所有节点和边画在平面上，且使得任何两条边除了端点外没有其他的交点，称图且使得任何两条边除了端点外没有其他的交点，称图G为平面图。（如为平面图。（如交通道路的设计问题）交通道路的设计问题）例例1：2、典型的非平面图、典型的非平面图(K5,K3,3)3、平面图术语、平面图术语平面图的面平面图的面（有限面，无限面）（有限面，无限面）面的次数面的次数deg(ri)例例2：r1是一个无限面，是一个无限面，r2正常的面，正常的面，r3包含一

29、个悬挂边的面，这使面次数增包含一个悬挂边的面，这使面次数增2。二、二、平面图的性质平面图的性质1、有限平面图，面的次数之和等于其边数的两倍。有限平面图，面的次数之和等于其边数的两倍。2、欧拉定理、欧拉定理一个连通的平面图一个连通的平面图G，共有，共有v个节点个节点e条边和条边和r个面，则有下面的欧拉公个面，则有下面的欧拉公式成立：式成立：v-e+r=23、平面图判定定理（非平面）、平面图判定定理（非平面）设设G是是v个节点个节点e条边的联通简单平面图，如果条边的联通简单平面图，如果v3,则则e3v-6。证明：设证明：设v=3时，时，e=2,可见可见e3v-6成立；成立；e3时，时，deg(ri

30、)3,又因为又因为v-e+r=2，所以，所以2+e-v(2e)/3，所以，所以e3v-6例3：对于K5有3*5-6=99，该图满足定理但不是平面图。7.6对偶图、图的着色对偶图、图的着色起源于地图地着色问题，地图相邻国家不上同一种颜色，最少需要多少种颜色。起源于地图地着色问题，地图相邻国家不上同一种颜色，最少需要多少种颜色。100多年前，英国地格色里提出了四色猜想，多年前，英国地格色里提出了四色猜想，1879年肯普给出了这个猜想的第年肯普给出了这个猜想的第一个证明，但是一个证明，但是1890年希五德发现这个证明是错的，他指出用五种颜色，提出年希五德发现这个证明是错的，他指出用五种颜色，提出五色

31、定理，后来四色猜想一直是当时的数学家们感兴趣的问题而未解决的难题，五色定理，后来四色猜想一直是当时的数学家们感兴趣的问题而未解决的难题，到到1976年，美国数学家阿佩尔和黑肯宣布，用计算机证明了四色猜想是成立的，年，美国数学家阿佩尔和黑肯宣布，用计算机证明了四色猜想是成立的，所以所以1976年后把四色猜想改成四色定理了。年后把四色猜想改成四色定理了。一、对偶图一、对偶图dualgraph1、定义、定义设平面图设平面图G=,若图若图G*=满足如下条件：满足如下条件：(1)在任意面在任意面ri内部取一个点内部取一个点v*iV*;(2)设边设边ek是面是面ri和和rj的公共边，则的公共边，则e*k=

32、(v*i,v*j)，并且，并且e*k与与ek相交相交,其中：其中：v*i,v*jV*。(3)如果如果ek是面是面ri内的悬挂边，内的悬挂边，在面在面ri内取点内取点v*i，则，则v*i存在一个环与存在一个环与ek相交。相交。2、性质、性质G*的节点数等于的节点数等于G的面数的面数G*的边条数等于的边条数等于G边条数边条数二、图的着色二、图的着色1、图色数、图色数图图G中对每个结点着上不同颜色，使得每对相邻接结点着的中对每个结点着上不同颜色，使得每对相邻接结点着的颜色不同，则图颜色不同，则图G中需要的最少颜色数称为该图的着色中需要的最少颜色数称为该图的着色数，记为数，记为x(G)。例例1：x(G

33、)=3例例2：对于：对于n个结点的完全图个结点的完全图Kn，有，有x(Kn)=n。图的着色相当于对其对偶图结点的着色。图的着色相当于对其对偶图结点的着色。2、韦尔奇、韦尔奇.饱威尔法饱威尔法(1)将图将图G中的节点按照度数的递减次序进行排列；中的节点按照度数的递减次序进行排列；(2)用第一种颜色对第一个点着色，并且按排列次序，对与前面着色点不用第一种颜色对第一个点着色，并且按排列次序，对与前面着色点不邻接的每一点着上同样的颜色；邻接的每一点着上同样的颜色；(3)用第二种颜色对尚未着色的点重复用第二种颜色对尚未着色的点重复2，如此反复，直到所有点均着色。，如此反复，直到所有点均着色。例3：deg

34、(v1)=5,deg(v5)=5,deg(v7)=3,deg(v3)=3,deg(v4)=3,deg(v6)=2,deg(v2)=2,7.7无向树无向树一、基本概念一、基本概念1、定义、定义一个连通且无回路的无向图称为树；一个连通且无回路的无向图称为树；树叶：度数为一的节点；树叶：度数为一的节点；分枝点或内点：度数大于一的结点分枝点或内点：度数大于一的结点2、树的等价定义、树的等价定义给定图给定图T，下面树的定义等价：，下面树的定义等价：(1)无回路的连通图；无回路的连通图；(2)无回路且无回路且e=v-1，其中，其中e是边数，是边数，v是结点数；是结点数；(3)连通且连通且e=v-1；(4)

35、无回路，但增加一条边，得到一个且仅有一个回路；无回路，但增加一条边，得到一个且仅有一个回路；(5)任意边为割边的连通图；任意边为割边的连通图；(6)每一对结点之间有一条且仅有一条路。每一对结点之间有一条且仅有一条路。3、性质、性质任一棵树中至少有两片树叶。任一棵树中至少有两片树叶。证明：因为证明：因为T是联通图，所以任意是联通图，所以任意deg(vi)1，如果图中每，如果图中每个节点度数都大于等于个节点度数都大于等于2(没有树叶没有树叶),，所以矛盾。若图中只，所以矛盾。若图中只有一个树叶，其它节点度数都大于等于有一个树叶，其它节点度数都大于等于2，则，则，也得出，也得出矛盾。矛盾。二、生成树

36、二、生成树spanningtree1、定义、定义若图若图G的生成子图是一棵树，则该树称为的生成子图是一棵树，则该树称为G的生成树。的生成树。(归纳法归纳法)2、性质、性质连通图至少有一颗生成树。连通图至少有一颗生成树。(用构造生成树的方法证明用构造生成树的方法证明)一条回路和任何一颗生成树的补至少有一条公共边。一条回路和任何一颗生成树的补至少有一条公共边。一个边割集和任何生成树至少有一条公共边。一个边割集和任何生成树至少有一条公共边。三、最小生成树三、最小生成树1、定义、定义 设设G是联通的边权图，是联通的边权图，G的某一生成树的某一生成树T有一个树权有一个树权C(T)，它是，它是T的所有边的

37、所有边权的和。权的和。2、最小生成树、最小生成树在图在图G的所有生成树中，树权最小的那棵生成树称为最小生成树。的所有生成树中，树权最小的那棵生成树称为最小生成树。3、最小生成树算法、最小生成树算法破圈法：破圈法：（普里目算法）去权值最大的边，去的时候注意保证图的联通性。（普里目算法）去权值最大的边，去的时候注意保证图的联通性。避圈法：避圈法：（Kruskal）加入权值最小的边，加的时候注意不出现回路。）加入权值最小的边，加的时候注意不出现回路。7.8有向树有向树directedtree 一、基本概念一、基本概念1、定义、定义如果一棵有向树有且只有一个结点入度为如果一棵有向树有且只有一个结点入度

38、为0，其余结点的入度为，其余结点的入度为1，称这种有向，称这种有向树为根树；入度为树为根树；入度为0的点称为根，出度为的点称为根，出度为0的点称为叶，其余点称为内点或的点称为叶，其余点称为内点或分枝点；从根到任意结点分枝点；从根到任意结点v的单向通路长度（边条数）称为的单向通路长度（边条数）称为v的层次；树的的层次；树的次序一般是从上到下、从左到右。次序一般是从上到下、从左到右。2、递归定义、递归定义树根包含一个或多个子结点，这些子结点中的某一个又可以称为根，其他所有树根包含一个或多个子结点，这些子结点中的某一个又可以称为根，其他所有结点又被分成有限个子根树。结点又被分成有限个子根树。画法：画

39、法：1、向上生长；、向上生长；2、向下生长。、向下生长。二、二、m叉树叉树1、定义、定义在根树中，若每一个结点的出度小于或等于在根树中，若每一个结点的出度小于或等于m，称这棵树为，称这棵树为m叉树；叉树；如果每一个结点的度数恰好为如果每一个结点的度数恰好为0或或m，称这棵树为完全，称这棵树为完全m叉树；叉树；若所有树叶的层次相同，称为正则若所有树叶的层次相同，称为正则m叉树。叉树。2、性质、性质完全完全m叉树，其叶结点数为叉树，其叶结点数为t，分支点数为，分支点数为i，则，则(m-1)i=t-1。3、二叉树的通路长度、二叉树的通路长度根树中，一个结点的通路长度，就是从树根到此结点的通路的边数；根树中，一个结点的通路长度，就是从树根到此结点的通路的边数；分枝点的通路长度称为内部通路长度，树叶的通路长度称为外部通路长分枝点的通路长度称为内部通路长度，树叶的通路长度称为外部通路长度。度。若完全二叉树有若完全二叉树有n个分枝点，且内部通路长度的总和为个分枝点，且内部通路长度的总和为I，外部通路长度，外部通路长度的总和为的总和为E，则，则E=I+2n。三、最优树三、最优树optimaltree这部分课件没做，按照上课讲解的最有二叉树这部分课件没做，按照上课讲解的最有二叉树