版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
图论引言◆图论是组合数学的一个分支。图论起源于1736年欧拉关于哥尼斯堡七桥问题的研究。在19世纪和20世纪的前半期,图论中主要研究的是些游戏问题,如迷宫问题、棋盘上马的行走路线等等。其中,最著名的难题是四色问题、哈密尔顿问题。引言◆现实世界中,许多事物之间的关系都可抽象成点及它们之间的连线来描述,图论中的图是描述事物之间关系的一种手段。例如交通运输、城市规划、电路网络、工作调配等都可以用点和边连接起来的图来模拟。◆由于图论中的图只是描述事物之间关系的一种手段。对图论中的图,人们只关心点之间是否有边,而不关心点及边的位置,以及边的曲直,因此,图论中的图与几何图形有显著区别。81图的基本概念8.1.1图的定义例A、B、C、D四个班进行足球比赛,为了表示四个班之间比赛的情况,我们作出如右上图的图形。在该图中的4个小圆圈分别表示这四个班,称之为结点。如果两个班进行了比赛,则在两个结点之间用一条线连接起来,称之为边。这样,利用图形使得各班之间的比赛情况一目了然。无序积定义设A,B为任意集合,称集合A8B={(a,b)|a∈A∧b∈B为A与B的无序积,(a,b)称为无序对。与序偶不同,无论a,b是否相等,均有(a,b)=(b,a)。图的定义定义一个图是一个序偶<V,E>,记为G=<V,E>,其中1)V={v1,v2,Vv3,…,vn是一个有限的非空集合,v;(i=1,2,3,,.n)称为结点,简称点,V为结点集2)E=e,e2,e3,…,en}是一个有限的集合,e;(i=1,2,3,,m)称为边,E为边集,E中的每个元素都有V中的结点对与之对应。即对任意e∈E,都有e与<u,v>∈WxV或者(u,v)∈V&V相对应。图的分类(按边的方向)1)若边e与无序结点对(u,v)相对应,则称边e为无向边,记为e=(u,v),这时称u,v是边e的两个端点2)若边e与有序结点对<u,>相对应,则称边e为有向边或弧),记为e=<u,v>,这时称u是边e的始点(或弧尾).V是边e的终点(或弧头),统称为e的端点;3)每条边都是无向边的图称为无向图4)每条边都是有向边的图称为有向图;5)有些边是无向边,而另一些是有向边的图称为混合图。用小圆圈表示V中的结点,用由u指向v的有向线段表示u,v>,无向线段表示(u,v)例1设图G=<V,E>如右图所这里V1,V2,V3,V4,V5el,e2,e4,e5,e6,其中e1=(vv2),e2=<v1,
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论