离散数学讲义第7章

《离散数学讲义第7章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DiscreteMathematics离散数学讲义（电子版）天津财经大学信息科学与技术系王宁ninglw@163.com1第四篇图论2图论的诞生图论哥尼斯堡七桥问题1736年，瑞士数学家欧拉（Euler）证明“哥尼斯堡七桥问题”无解——图论创始年。1936年，匈牙利数学家寇尼格（Konig）出版了图论的第一部专著《有限图与无限图理论》。3图论的特点图论（续）只关心点之间是否有连线，而不关心点的位置以及连线的曲直。————与几何学的区别可直观地表示离散对象之间的相互关系。4图论的应用广泛应用于计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事

2、、国防、工农业生产等方面——异军突起，活跃非凡图论（续）518世纪时，欧洲有一个风景秀丽的小城哥尼斯堡，那里有七座桥。如图1所示：河中的小岛A与河的左岸B、右岸C各有两座桥相连结，河中两支流间的陆地D与A、B、C各有一座桥相连结。当时哥尼斯堡的居民中流传着一道难题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题…………这个问题无解哥尼斯堡七桥问题(SevenbridgesofKönigsbergproblem):RiverPregel,Kaliningrad,Russia图论（续）6“七桥问题”的图论解法17

3、36年,图论和拓扑学诞生CBADcdabfge图论（续）7LeonhardEuler(1707-1783)瑞士数学家对数学多个领域做出贡献最多产的数学家，一生发表1100多篇论著（论文）。死后47年才出版完其全部论著。图论（续）8第七章图论9第七章图论本章包括以下内容：7-1图的基本概念7-2路与回路7-3图的矩阵表示7-4欧拉图与汉密尔顿图7-5平面图7-6对偶图与着色7-7树与生成树7-8根树及其应用107-1图的基本概念图的定义三元组G=〈V(G)，E(G)，j(G)〉，称为一个图：(1)V,顶点集,其中元素称为顶点或结点(vertex/node)。(2)E(G)，

4、边集，其中元素称为边(edge/link)(3)j(G)表示V与E之间的关系，是从边集E到结点无序偶（有序偶）集合上的函数。abej(e)=(a,b)j(e)=〈a,b〉abe11一般用就G=〈V，E〉来表示图。用

5、V(G)

6、表示G的顶点数用

7、E(G)

8、表示G的边数7-1图的基本概念注：图中的边总与两个结点相关联。也就是说，不存在只有边没有结点的图。√×abeabe√×12（1）若边e与结点u,v的无序偶（记作(u,v)）相关联，则称该边为无向边，每一条边都为无向边的图称为无向图。7-1图的基本概念（2）若边e与结点u,v的有序偶（记作〈u,v〉）相关联，则称该边为有向边，每

9、一条边都为有向边的图称为有向图。（3）图中一些边为有向边，一些边为无向边，则称该图为混合图。无向图，有向图，混合图13v1v4v2v3e5e2e4e6e3e1例如：右图为无向图G=〈V,E,φ〉7-1图的基本概念（续）v1v4v2v3e6e2e5e3e4e1V={v1,v2,v3,v4}E={e1,e2,e3,e4,e5,e6}φ：e1=(v1,v1)e2=(v1,v2)e3=(v2,v3)e4=(v3,v4)e5=(v4,v1)e6=(v4,v2)例如：右图为有向图D=〈V,E,ψ〉V={v1,v2,v3,v4}E={e1,e2,e3,e4,e5,e6}ψ：e1=〈v1,v

10、1〉e2=〈v1,v2〉e3=〈v2,v3〉e4=〈v3,v4〉e5=〈v1,v4〉e6=〈v2,v4〉14邻接(adjacent)点：图中两个结点由一条有向（或无向）边关联。术语7-1图的基本概念（续）uv邻接边：关联于同一结点的两条边。n阶图(order-ngraph)：

11、V(G)

12、=n有限图(finitegraph)：

13、V(G)

14、<，且

15、E(G)

16、<空图(emptygraph)：V=E=，记作1+1-11关联次数：15环（自回路loop）：关联于同一结点的一条边。（环的方向无意义）。平凡图：仅由一个孤立点构成的图。（1阶零图,N1）孤立点(isolatedver

17、tex)：图中不与任何结点相邻接的结点。术语7-1图的基本概念（续）零图：仅由孤立点组成的图。（E=,Nn）16结点的度数：图中与结点v关联的边数，记作deg(v)。（约定，每个环在其对应结点上度数增加2）术语03347-1图的基本概念（续）入度：射入一个结点的边数。（d-(v)）出度：由一个结点射出的边数。（d+(v)）显然deg(v)=d+(v)+d-(v)（结点的度数=入度+出度）最大度：(G)=max{degG(v)

18、vV(G)}最小度：(G)=min{degG(v)

19、vV(G)}0,