资源描述：
《电子科大研究生图论课件——第1,2章基本概念,树(11.3).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图论及其应用1.1图论简介现实生活中许多问题都可归结为由点和线组成的图形的问题，例如，铁路交通图，公路交通图，市区交通图，自来水管网系统，甚至电路图在研究某些问题时也可简化为由点和线组成的图形，如：图论就是研究这些由点和线组成的图形的问题图论起源于18世纪，是一门较为年青的数学分支。但在历史上遗留了许多著名的图论问题，例如：1.七桥问题18世纪东普鲁士有一个城市称为个普尼斯堡，它位于普雷格尔河畔，河中有两个小岛，通过七座桥彼此相联（如图）。当时有人提出：能否从某个地点出发经过每个桥一次且仅一次然后返回出发点？ABCDEuler的解：2.
2、Hamilton周游世界问题1859年Hamilton提出这样一个问题：一个正十二面体有20个顶点，它们代表世界上20个重要城市。正十二面体的每个面均为五边形，若两个顶点之间有边相连，则表示相应的城市之间有航线相通。Hamilton提出“能否从某城市出发经过每个城市一次且仅一次然后返回出发点？”1840年数学家茂比乌斯（Möbius）提出一个猜想：任何平面地图，总可以把它的一个国家用四种颜色的一种着染，使相邻国家着不同色。这就是著名的四色猜想。如：1890年希五德（Heawood）指出“4换为5”猜想成立。1976年两位数学家在三台百万
3、次的电子计算机上花了1200小时证明了猜想成立。猜想成为定理。3.四色问题4.中国邮路问题1962年中国数学家管梅谷提出：一个邮递员从邮局出发递送邮件，要求对他所负责的辖区的每条街至少走一次，问如何选取路程最短的路线？这个问题称为中国邮路问题。该问题可用专门的算法来求解。图论的应用范围很广，它不但能应用于自然科学，也能应用于社会科学。它非但广泛应用于电信网络、电力网络、运输能力开关理论、编码理论、控制论、反馈理论、随机过程、可靠性理论、化学化合物的辨认、计算机的程序设计、故障诊断、人工智能、印刷电路板的设计、图案识别、地图着色、情报检索
4、，也应用于语言学、社会结构、经济学、运筹学、遗传学等。图论作为一个数学分支，有一套完整的体系和广泛的内容，在这里我们只准备介绍图论的初步知识，其目的是今后在其它有关学科的学习和研究时，可以用图论的基本知识作为工具。§1.1图和简单图一．图的定义定义1一个图G定义为一个有序对(V,E)，记为G=(V,E)，其中（1）V是一个非空集合，称为顶点集或点集，其元素称为顶点或点；（2）E是由V中的点组成的无序点对构成的集合，称为边集，其元素称为边，且同一点对在E中可出现多次。第一章图的基本概念符号说明:图G的顶点集也记为V(G),边集也记为E(G
5、)。图G的顶点数（或阶数）和边数可分别用符号n(G)(或
6、V(G)
7、)和m(G)表示。例1设V={v1,v2,v3,v4}，E={v1v2,v1v2,v2v3}，则G=(V,E)是一个4阶图。若用小圆点代表点，连线代表边，则可将一个图用“图形”来表示,如例1中的图可表为v1v2v3v4注:也可记边uv为e，即e=uv。v1v2v3v4e1e2e3e4e5例2设V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5}，其中e1=v1v2，e2=v2v3，e3=v2v3，e4=v3v4，e5=v4v4则G=(V,E)是一个图。相
8、关概念:(1)若边e=uv,此时称u和v是e的端点;并称u和v相邻，u(或v)与e相关联。若两条边有一个共同的端点，则称这两条边相邻。（2）特殊点、边孤立点：不与任何边相关联的点；环：两端点重合的边；重边：连接两个相同顶点的边的条数，叫做边的重数。重数大于1的边称为重边。(4)既没有环也没有重边的图称为简单图。其他所有的图都称为复合图。简单图非简单图例3平凡图●(3)点集与边集均为有限集合的图称为有限图，本书只讨论有限图。只有一个顶点而无边的图称为平凡图。边集为空的图称为空图。二．图的同构定义2设有两个图G1=(V1,E1)和G2=(V
9、2,E2)，若在其顶点集合之间存在双射，即存在一一对应的关系，使得边之间有如下的关系：设当且仅当，；且的重数与的重数相同，则称两图同构，记为G1≌G2。，对应为：例如≌说明：(1)两个同构的图均有相同的结构，没有本质上的差异,差异只是顶点和边的名称不同。（2）图同构的几个必要条件：①顶点数相同；②边数相同；③度数相等的顶点个数相同。定义设v为G的顶点，G中与v为端点的边的条数（环计算两次）称为点v的度数，简称为点v的度，记为dG(v)，简记为d(v)。图中d(v1)=5d(v2)=4d(v3)=3d(v4)=0d(v5)=2v1v2v3
10、v4v5例注：该图中各点的度数之和等于14，恰好是边数7的两倍(3)易证，图的同构关系是一个等价关系。该关系将所有的图的集合，划分为一些等价类，即相互同构的图作成同一个等价类。（3）在图的图形表示中我们可以
