第四篇 图 论

《第四篇 图 论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四篇图论第八章　图论原理§8.1图的基本概念§8.2通路、回路与连通性§8.3欧拉图§8.4汉密尔顿图§8.5图的矩阵表示法第九章常用图§9.1树§9.2平面图§9.3两步图第八章图论原理§8.1图论基本概念一、图远在18世纪就出现图论问题，如著名的哥尼斯堡桥问题。二、图的基本概念：图可由两部分组成：一部分是一些点，称其为结点；另一部分是连接这些点的线，称其为边。定义1：图G是由非空结点集合V={v1,v2,…,vn}以及边集合E={l1,l2,…,lm}所组成。其中每条边可用一个结点对表示之，这样的一个图G可用G=＜V，E＞表示。例1：有四个城市：v1,v2

2、,v3,v4，其中v1与v2间；v1与v4间；v2与v3间有直达长话线路相连，试将此事实用图的方法表示之。例2：有四个程序p1,p2,p3,p4，它们间有一些调用关系：p1能调用p2；p2能调用p3；p2能调用p4，试将此事实用图的方法表示之。利用图中边的有向和无向可将图分成两种类型：有向图和无向图。图G=〈V，E〉与G’=〈V’，E’〉间如果有V’V及E’E，则称G’是G的子图，如果进一步有E’E，则称G’是G的真子图。图G=〈V，E〉与G’=〈V’，E’〉间如果有V’=V，E’E，则称G’是G的生成子图。一个具有n个结点、m个边所组成的图称为(n,m)图。如

3、果图G是一个(n,0)图则称此图为零图。特别地，G是一个(1,0)图则称为平凡图。一(n,m)图G如果其n个结点（n≥2）中的每个点均与其余n-1个结点邻接，则这样的图称为完全图。在完全图中：m=n(n-1)/2。可由完全图引出一个图的补图的概念：设有一图G=〈V，E〉，对图G’=〈V，E’〉如果有G’’=〈V，E∪E’〉是完全图且E∩E’=φ，则称G’是G的补图。三、图的同构：四、图中结点的次数：定义3：在有向图中的结点v，以v为起点的边的条数叫v的引出次数，以v为终点的边的条数叫v的引入次数，v的引入次数与引出次数之和称为v的次数或全次数，记以：deg(v)

4、；在无向图中，结点v的次数或全次数是与v相关联的边的条数，也用deg(v)表示之。定理1：图G=〈V，E〉是一个（n，m）图，其中V={v1,v2,…,vn}，此时有：五、多重图和带权图：一个结点对间有多条边，这种边称为多重边。包含多重边的图称为多重图，而不含多重边的图则叫简单图。有时，在一个图中边的旁侧可附加一些数字以刻划此边的某些数量特性，叫做边的权，而此边叫有权边，具有有权边的图叫有权图，无有权边的图叫无权图。§8.2通路、回路与连通性一、通路与回路：1.通路：设有有向图G=〈V，E〉，考虑G中边的序列:这个序列由开始至结束，其中间每条边的终点是下一条边的

5、起点。此边的序列可简写成：，在此序列中可以允许多次出现相同的结点与边在此序列中除及外，中间每个结点均与其前后结点相邻接，这种边的序列叫图的通路。而与分别叫通路的起始结点与终止结点，通路中边的数目叫通路的长度。有向图中各边全不相同的通路叫简单通路，各点全不相同的通路叫基本通路。2.回路：图中一条通路如果其起始结点与终止结点相同则称此通路为回路。图中各边全不相同的回路叫简单回路，各点全不相同的叫基本回路。定理1：一个有向（n,m）图中任何基本通路长度均小于或等于n-1，而任何基本回路长度均小于或等于n。3.可达性：定义1：从有向图的结点vi到另一结点vj间如果存在一

6、条通路，则称从vi到vj是可达的。两结点间长度最短的通路叫短程线。而短程线的长度则称为从vi到vj间的距离，可用d(vi,vj)表示之。二、连通性：定义2：一个无向图G，如果它的任何两结点间均是可达的，则称图G为连通图；否则称为非连通图。定义3：一个有向图，如果忽略其边的方向后得到的无向图是连通的，则称此有向图为连通图；否则称为非连通图。定义4：一个有向连通图G如果其任何两结点间均是互相可达的则称图G是强连通的；如果其任何两结点间至少存在一向是可达的则称图G是单向连通的；如果忽略边的方向后其无向图是连通的，则称图G是弱连通的。§8.3欧拉图定义1：图G的一个回路

7、，若它通过G中的每条边一次，这样的回路称为欧拉回路，具有这种回路的图叫欧拉图。定理1：无向连通图G是欧拉图的充分必要条件是G的每个结点均具有偶次数。定义2：通过图G中每条边一次的通路（非回路）称为欧拉通路。定理2vi与vj间存在欧拉通路的充分必要条件是G中vi与vj的次数均为奇数而其他结点的次数为偶数。§8.4哈密尔顿图所谓哈密尔顿回路，起源于一种游戏，它是由英国数学家哈密尔顿于1859年提出，这种游戏叫周游世界游戏。定义1：图G的一个回路若它通过G中每个点一次，这样的回路称为哈密尔顿回路。具有这种回路的图叫哈密尔顿图。定义2：通过图G中每结点一次的通路（非回路

8、）称为哈密尔顿通路。§8