第四篇 与 图 论 .ppt

第四篇 图 论 第八章　图论原理 §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,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)图。如果图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) ；在无向图中，结点v的次数或全次数是与v相关联的边的条数，也用deg(v)表示之。 定理1：图G=〈V，E〉是一个（n，m）图，其中V={v1,v2, …,vn}，此时有： 五、多重图和带权图： 一个结点对间有多条边，这种边称为多重边。包含多重边的图称为多重图，而不含多重边的图则叫简单图。 有时，在一个图中边的旁侧可附加一些数字以刻划此边的某些数量特性，叫做边的权，而此边叫有权边，具有有权边的图叫有权图，无有权边的图叫无权图。 §8.2 通路、回路与连通性 一、通路与回路： 1.通路： 设有有向图G=〈V，E〉，考虑G中边的序列: 这个序列由 开始至 结束，其中间每条边的终点是下一条边的起点。此边的序列可简写成： ，在此序列中可以允许多次出现相同的结点与边 在此序列中除 及 外，中间每个结点均与其前后结点相邻接，这种边的序列叫图的通路。而 与 分别叫通路的起始结点与终止结点，通路中边的数目叫通路的长度。 有向图中各边全不相同的通路叫简单通路，各点全不相同的通路叫基本通路。 2.回路： 图中一条通路如果其起始结点与终止结点相同则称此通路为回路。图中各 边全不相同的回路叫简单回路，各点全不相同的叫基本回路。 定理1：一个有向（n,m）图中任何基本通路长度均小于或等于n-1，而任何基本回路长度均小于或等于n。 3.可达性： 定义1：从有向图的结点vi到另一结点vj 间如果存在一条通路，则称从vi到vj是可达的。 两结点间长度最短的通路叫短程线。而短程线的长度则称为从vi到vj间的距 离，可用d(vi,vj)表示之。 二、连通性： 定义2：一个无向图G，如果它的任何两结点间均是可达的，则称图G为连通图；否则称为非连通图。 定义3：一个有向图，如果忽略其边的方向后得到的无向图是连通的，则称此有向图为连通图；否则称为非连通图。 定义4：一个有向连通图G如果其任何两结点间均是互相可达的则称图G是强连通的；如果其任何两结点间至少存在 一向是可达的则称图G是单向