第5章 图论(精品).ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《第5章 图论(精品).ppt》由会员分享,可在线阅读,更多相关《第5章 图论(精品).ppt(59页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、5.1 图的基本概念图的基本概念一、一、图的定义图的定义例例1 1 A、B、C、D四四个个班班进进行行足足球球比比赛赛,为为了了表表示示四四个个班班之之间间比比赛赛的的情情况况,我我们们作作出出如如右右上上图图的的图图形形。在在该该图图中中的的4 4个个小小圆圆圈圈分分别别表表示示这这四四个个班班,称称之之为为结结点点。如如果果两两个个班班进进行行了了比比赛赛,则则在在两两个个结结点点之之间间用用一一条条线线连连接接起起来来,称称之之为为边边。这这样样,利利用用图图形形使使得得各各班班之之间间的的比比赛赛情情况一目了然。况一目了然。定义定义2一个一个图图是一个序偶是一个序偶 ,记为,记为G,其
2、中:其中:1)Vv1,v2,v3,vn是一个有限的非空集合,是一个有限的非空集合,vi(i1,2,3,n)称为称为结点结点,简称简称点点,V为为结点集结点集;2)Ee1,e2,e3,em是一个有限的集合,是一个有限的集合,ei (i1,2,3,m)称为称为边边,E为为边集边集,E中的每中的每个元素都有个元素都有V中的结点对与之对应。中的结点对与之对应。1.若边若边e与无序结点对与无序结点对(u,v)相对应,则称边相对应,则称边e为为无向边无向边,记为记为e=(u,v),这时称,这时称u,v是边是边e e的两个的两个端点端点;2.若边若边e与有序结点对与有序结点对 相对应,则称边相对应,则称边e
3、为为有向边有向边,记为记为e=,这时称,这时称u是边是边e的的始点始点,v是边是边e的的终点终点,统称为统称为e的的端点端点;3.每条边都是无向边的图称为每条边都是无向边的图称为无向图无向图;4.每条边都是有向边的图称为每条边都是有向边的图称为有向图有向图;5.有些边是无向边,而另一些是有向边的图称为有些边是无向边,而另一些是有向边的图称为混合图混合图。图的分类图的分类(按边的方向按边的方向):例例1 设图设图G 如右图所如右图所示。这里示。这里Vv1,v2,v3,v4,v5,Ee1,e2,e3,e4,e5,e6,e1(v1,v2),e2 ,e3(v1,v4),e4(v2,v3),e5 ,e6
4、(v3,v3)。图中的图中的e1、e3、e4是无向边,是无向边,e2、e5是有向边。是有向边。其中其中1)在一个图中,关联结点在一个图中,关联结点vi和和vj的边的边e,无论是有向的,无论是有向的还是无向的,均称边还是无向的,均称边e与结点与结点vi和和vj相关联相关联,而,而vi和和vj称为称为邻接点邻接点,否则称为,否则称为不邻接的不邻接的;几个概念几个概念:2)关联于同一个结点的两条边称为关联于同一个结点的两条边称为邻接边邻接边;3)图中关联同一个结点的边称为图中关联同一个结点的边称为环环;4)图中不与任何结点相邻接的结点称为图中不与任何结点相邻接的结点称为孤立结点孤立结点;5)仅由孤立
5、结点组成的图称为仅由孤立结点组成的图称为零图零图;6)仅含一个结点的零图称为仅含一个结点的零图称为平凡图平凡图.二、二、图的矩阵表示图的矩阵表示设图设图G=,V=v1,v2,vn,E=e1,e2,em,则则G的的关联矩阵关联矩阵为为:为为 关联关联的次数的次数G的的邻接矩阵邻接矩阵为为:为联接为联接的边数的边数例例2 设设G如如图所示图所示,则则1)在有向图中,两个结点间在有向图中,两个结点间(包括结点自身间包括结点自身间)若有同始点和若有同始点和同终点的几条边,则这几条边称为同终点的几条边,则这几条边称为平行边平行边,2)在无向图中,两个结点间在无向图中,两个结点间(包括结点自身间包括结点自
6、身间)若有几条边,若有几条边,则这几条边称为则这几条边称为平行边平行边;3)两结点两结点vi,vj间相互平行的边的条数称为边间相互平行的边的条数称为边(vi,vj)或或 的的重数重数;4)含有平行边的图称为含有平行边的图称为多重图多重图;5)非多重图称为非多重图称为线图线图;6)无环的线图称为无环的线图称为简单图简单图。图的分类图的分类(按边的重数按边的重数):例例4G1、G2是多重图,是多重图,G3是线图,是线图,G4是简单图。是简单图。定义定义5 赋权图赋权图G是一个三重组是一个三重组 或四重或四重 其中其中V是结点集合,是结点集合,E是边的集合,是边的集合,f是从是从V到非负实数到非负实
7、数集合的函数,集合的函数,g是从是从E到非负实数集合的函数。非赋权到非负实数集合的函数。非赋权图称为图称为无权图无权图。图的分类图的分类(按权按权):1)在无向图在无向图G 中,与结点中,与结点v(v V)关联的边的条关联的边的条数数(有环时计算两次有环时计算两次),称为该结点的,称为该结点的度数度数,记为,记为deg(v);2)在有向图在有向图G 中,以结点中,以结点v为始点引出的边的为始点引出的边的条数,称为该结点的条数,称为该结点的出度出度,记为记为deg+(v);以结点;以结点v为为终点引入的边的条数,称为该结点的终点引入的边的条数,称为该结点的入度入度,记为记为deg-(v);而结点
8、的引出度数和引入度数之和称为该结点;而结点的引出度数和引入度数之和称为该结点的的度数度数,记为,记为deg(v),即,即deg(v)deg+(v)+deg-(v);3)对于图对于图G ,度数为,度数为1的结点称为的结点称为悬挂结点悬挂结点,它所关联的边称为它所关联的边称为悬挂边悬挂边。4)在图在图G 中,称度数为奇数的结点为中,称度数为奇数的结点为奇度数结奇度数结点点,度数为偶数的结点为,度数为偶数的结点为偶度数结点偶度数结点。2结点的度数结点的度数 deg(v1)3,deg+(v1)2,deg-(v1)1;例6deg(vdeg(v2 2)3 3,degdeg+(v(v2 2)2 2,degd
9、eg-(v(v2 2)1 1;deg(vdeg(v3 3)5 5,degdeg+(v(v3 3)2 2,degdeg-(v(v3 3)3 3;deg(vdeg(v4 4)1 1,degdeg+(v(v4 4)0 0,degdeg-(v(v4 4)1 1;deg(vdeg(v5 5)degdeg+(v(v5 5)degdeg-(v(v5 5)0 0;其中,其中,v v4 4是悬挂结点,是悬挂结点,v 为悬挂边。为悬挂边。定理定理1 1(握手定理握手定理)在无向图在无向图G 中,则所结中,则所结点的度数的总和等于边数的两倍,即:点的度数的总和等于边数的两倍,即:证:证:由于图由于图G的任一条边都有
10、的任一条边都有2 2个端点,而在计个端点,而在计算度时恰被计算两次算度时恰被计算两次(每个端点各算一次每个端点各算一次),所以,所以各点度数之和恰好为边数的两倍各点度数之和恰好为边数的两倍.推论:任意图中推论:任意图中度数为奇数的结点个数为偶数。度数为奇数的结点个数为偶数。证证设设V1v|v V且且deg(v)奇数奇数,V V2 2 v|v V且且deg(v)偶数偶数。显然,。显然,V1V2,且,且V1 1V2 2V,于是有:,于是有:由于上式中的由于上式中的2m和和 均为偶数,因而均为偶数,因而 也为偶数。于是也为偶数。于是|V1|为偶数为偶数(因为因为V1中的结点中的结点v之之deg(v)
11、都为奇数都为奇数),即奇度数的结点个数为偶数,即奇度数的结点个数为偶数三、子图与三、子图与生成子图生成子图定义定义 设有图设有图G 和图和图G 。若若V V,E E,则称,则称G是是G的的子图子图,记为,记为G G。若若G G,且,且G G(即(即V V或或V E),则,则称称G 是是G的的真子图真子图,记为,记为G G。若若V=V,E E,则称,则称G 是是G的的生成子图生成子图。1.设设G 为一个具有为一个具有n个结点的无向简单图,个结点的无向简单图,如果如果G中任一个结点都与其余中任一个结点都与其余n-1个结点相邻接,个结点相邻接,则称则称G为为无向完全图无向完全图,简称,简称G为为完全
12、图完全图,记为,记为Kn。2.设设G 为一个具有为一个具有n个结点的有向简单图,个结点的有向简单图,若对于任意若对于任意u,v V(u v),既有有向边,既有有向边 ,又有有向边又有有向边 ,则称,则称G为为有向完全图有向完全图,在不,在不发生误解的情况下,也记为发生误解的情况下,也记为Kn。5.2 路、连通性与最短路路、连通性与最短路 v图图G 中结点和边相继交错出现的序列中结点和边相继交错出现的序列=v0e1v1e2v2ekvk,若,若中边中边ei的两端点是的两端点是vi-1和和vi(G是有向图时要求是有向图时要求vi-1与与vi分别是分别是ei的始点和的始点和终点终点),则称,则称为结点
13、为结点v0到结点到结点vk的的通路通路。vv0和和vk分别称为此通路的分别称为此通路的始点始点和和终点终点,统称为通,统称为通路的路的端点端点。v通路中边的数目通路中边的数目k称为此称为此通路的长度通路的长度。v当当v0vk时,此通路称为时,此通路称为回路回路。若通路中的所有边若通路中的所有边e1,e2,ek互不相同,则称互不相同,则称此通路为此通路为简单通路简单通路或一条或一条迹迹;若回路中的所有边;若回路中的所有边e1,e2,ek互不相同,则称此回路为互不相同,则称此回路为简单回路简单回路或一条或一条闭迹闭迹;若通路中的所有结点若通路中的所有结点v0,v1,,vk互不相同(从互不相同(从而
14、所有边互不相同),则称此通路为而所有边互不相同),则称此通路为基本通路基本通路或或者者初级通路初级通路、路径路径;若回路中除;若回路中除v v0 0v vk k外的所有外的所有结点结点v v0 0,v v1 1,v vk-1k-1互不相同(从而所有边互不互不相同(从而所有边互不相同),则称此回路为相同),则称此回路为基本回路基本回路或者或者初级回路初级回路、圈圈。基本通路基本通路(或基本回路或基本回路)一定是简单通路一定是简单通路(或简单或简单回路回路),但反之则不一定。,但反之则不一定。1 简单通路与基本通路简单通路与基本通路 在图在图G1中:中:v1e2v5e3v2e6v4e8v3e9v3
15、e5v2e1v1,v5e3v2e4v5 例例1在图在图G2中:中:v1e1v2e2v3e3v4e4v5e7v6;v1e1v2e5v4e3v3e2v2e9v6。注:注:1.在不会引起误解的情况下,一条通路在不会引起误解的情况下,一条通路v0e1v1 e2v2 envn可以用边的序列可以用边的序列e1e2en来表示,这种表来表示,这种表 示方法对于有向图来说较为方便。示方法对于有向图来说较为方便。2.在简单图中,一条通路在简单图中,一条通路v0e1v1e2v2envn也可以用也可以用 结点的序列结点的序列v0v1v2vn来表示。来表示。3.在通路与回路的定义中,我们将回路定义为通路在通路与回路的定
16、义中,我们将回路定义为通路的特殊情况。因而,我们说某条通路,它可能的特殊情况。因而,我们说某条通路,它可能是回路。但当我们说一基本通路时,一般是指是回路。但当我们说一基本通路时,一般是指它不是基本回路的情况。它不是基本回路的情况。定理定理1 在一个具有在一个具有n个结点的图中,如果从结点个结点的图中,如果从结点vi到到结点结点vj(vivj)存在一条通路,则从存在一条通路,则从vi到到vj存在一条不存在一条不多于多于n-1-1条边的通路条边的通路.证证:设设vi0,vi1,vik为从为从vi到到vj的长度为的长度为k的一条通路,其的一条通路,其中中vi0=vi,vik=vj.此通路上有此通路上
17、有k+1个结点。若个结点。若kn-1-1,这条,这条通路即为所求。若通路即为所求。若kn-1,则此通路上的结点数,则此通路上的结点数k+1n,必存在一个结点在此通路中不止一次出现,设必存在一个结点在此通路中不止一次出现,设vis=vit,其中,其中,0stk。去掉。去掉vis s到到vit中间的通路,至少去掉一中间的通路,至少去掉一条边,得通路条边,得通路vi0,vi1,vis,vit+1,vik,此通路比原通路,此通路比原通路的长度至少少的长度至少少1。如此重复进行下去,必可得一条从。如此重复进行下去,必可得一条从vi到到vj不多于不多于n-1条边的通路。条边的通路。2 无向图的连通性无向图
18、的连通性:定义定义 设设u,v为无向图为无向图G=中的两个结点,若中的两个结点,若u,v之间存在通路,则称结点之间存在通路,则称结点u,v是是连通连通的,记为的,记为uv.对任意结点对任意结点u,规定,规定uu.定义定义 若无向图若无向图G=中任意两个结点都是连通的,中任意两个结点都是连通的,则称则称G是是连通图连通图,否则则称,否则则称G是非连通图是非连通图(或或分离图分离图)。定义定义 无向图无向图G中的连通的子图中的连通的子图H且不能扩充为且不能扩充为G的任的任一连通的子图一连通的子图F,称,称H为为G的一个的一个连通分支连通分支,用,用k(G)表表示示G中的中的连通分支个数连通分支个数
19、.无向图无向图G=是连通图当且仅当是连通图当且仅当k(G)=1.例例2 2G1是连通图,所以是连通图,所以k(G1)1;G2是非连通图,且是非连通图,且k(G2)4.定义定义 赋权图赋权图G是一个三重组是一个三重组 或四重或四重 其中其中V是结点集合,是结点集合,E是边的集合,是边的集合,f是从是从V到非负实数到非负实数集合的函数,集合的函数,g是从是从E到非负实数集合的函数。非赋权到非负实数集合的函数。非赋权图称为图称为无权图无权图。在在权权图图G=中中,对对 u,v V,如如果果从从vi 到到vj 存存在在通通路路,其其中中长长度度最最短短的的一一条条称称为为从从u 到到v 的的最最短短路
20、路,最短路最短路的长度称为的长度称为距离距离,记为,记为d(u,v).在在(a)中有中有:d(v2,v1)=1,d(v1,v2)=2,d(v1,v3)=4,d(v4,v1)=3;在在(b)(b)中有中有:d(v1,v3)=2,d(v3,v7)=3,d(v1,v7)=4.求距离求距离Dijkstra算法:算法:转转(3);计算计算 记达到最小值的某点,置记达到最小值的某点,置 对每个对每个转转(2).边边 权权.例例3 见教材见教材241页,例页,例5 5.3 树及其应用树及其应用定义定义1 1连通而不含回路的无向图称为连通而不含回路的无向图称为无向树无向树,简,简称称树树。树树中中度度数数为为
21、1的的结结点点称称为为树树叶叶;度度数数大大于于1的的结结点点称称为为分分支支点点或或内内部部结结点点。常常用用T 表表示示树树。不不含回路的无向图称为含回路的无向图称为森林森林。若图若图G G是森林,则是森林,则G G得到的每个连通分支都是树得到的每个连通分支都是树。例例1 显然有:显然有:(a)、(b)、(c)、(d)都是树,都是树,(e)是森林。是森林。其中其中(c)是平凡图,我们称之为是平凡图,我们称之为平凡树平凡树,它的结点度,它的结点度数为数为0。而在任何非平凡树中,都无度数为。而在任何非平凡树中,都无度数为0的结点。的结点。定理定理1设设G=是一个是一个n个个结点结点m条条边的边
22、的简单无向简单无向图。则以图。则以下关于树的命题等价:下关于树的命题等价:1)G是连通且不含回路的;是连通且不含回路的;2)G中无回路,且中无回路,且m=n-1;3)G是连通的,且是连通的,且m=n-1;4)G中无回路,但在中无回路,但在G中任何二结点之间增加一条新中任何二结点之间增加一条新边,就得到唯一的一条基本回路;边,就得到唯一的一条基本回路;5)G是连通的,但删除是连通的,但删除G中的任意一条边后,便不连中的任意一条边后,便不连通;通;6)G中每一对结点之间有唯一的一条基本通路。中每一对结点之间有唯一的一条基本通路。定义定义4若连通图若连通图G的某个生成子图是一棵树,则称的某个生成子图
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第5章 图论精品 图论 精品
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内