第七章图的基本概念PPT讲稿.ppt
《第七章图的基本概念PPT讲稿.ppt》由会员分享,可在线阅读,更多相关《第七章图的基本概念PPT讲稿.ppt(30页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第七章图的基本概念第七章图的基本概念第1页,共30页,编辑于2022年,星期一2022/9/1817.3 图的矩阵表示图的矩阵表示给给给给定定定定一一一一个个个个图图图图G G=,使使使使用用用用图图图图形形形形表表表表示示示示法法法法很很很很容容容容易易易易把把把把图图图图的的的的结结结结构构构构展展展展现现现现出出出出来来来来,而而而而且且且且这这这这种种种种表表表表示示示示直直直直观观观观明明明明了了了了。但但但但这这这这只只只只在在在在结结结结点点点点和和和和边边边边(或或或或弧弧弧弧)的数目相当小的情况下才是可行的。显然这限制了图的利用。的数目相当小的情况下才是可行的。显然这限制了图
2、的利用。的数目相当小的情况下才是可行的。显然这限制了图的利用。的数目相当小的情况下才是可行的。显然这限制了图的利用。本本本本节节节节提提提提供供供供另另另另一一一一种种种种图图图图的的的的表表表表示示示示法法法法图图图图的的的的矩矩矩矩阵阵阵阵表表表表示示示示法法法法。它它它它不不不不仅仅仅仅克克克克服服服服了了了了图图图图形形形形表表表表示示示示法法法法的的的的不不不不足足足足,而而而而且且且且这这这这种种种种表表表表示示示示可可可可以以以以充充充充分分分分利利利利用用用用现现现现代工具电子计算机,以达到研究图的目的。代工具电子计算机,以达到研究图的目的。代工具电子计算机,以达到研究图的目的
3、。代工具电子计算机,以达到研究图的目的。第2页,共30页,编辑于2022年,星期一无向图的关联矩阵无向图的关联矩阵注:自环取注:自环取2 2。第3页,共30页,编辑于2022年,星期一第4页,共30页,编辑于2022年,星期一性质性质:若第j列与第k列相同,则ej与ek为平行边第5页,共30页,编辑于2022年,星期一有向图的关联矩阵有向图的关联矩阵第6页,共30页,编辑于2022年,星期一第7页,共30页,编辑于2022年,星期一性质性质:第8页,共30页,编辑于2022年,星期一一个简单图一个简单图G=由由V中每两个结点间中每两个结点间的邻接关系唯一地确定,这种关系可以用一个的邻接关系唯一
4、地确定,这种关系可以用一个矩阵给出,而矩阵形式与图中结点的编序有密矩阵给出,而矩阵形式与图中结点的编序有密切关系,这是用矩阵表示图值得注意的一点。切关系,这是用矩阵表示图值得注意的一点。第9页,共30页,编辑于2022年,星期一有向图的邻接矩阵有向图的邻接矩阵第10页,共30页,编辑于2022年,星期一对对于于给给定定图图D,显显然然不不会会因因结结点点编编序序不不同同而而使使其其结结构构发发生生任任何何变变化化,即即图图的的结结点点所所有有不不同同的的编编序序实实际际上上仍仍表表示示同同一一个个图图。换换句句话话说说,这这些些结结点点的的不不同同编编序序的的图图都都是是同同构构的的,并并且且
5、它它们的邻接矩阵都是相似的。们的邻接矩阵都是相似的。今今后后将将略略去去这这种种由由于于V中中结结点点编编序序而而引引起起邻邻接接矩矩阵阵的的任任意意性性,而而取取该该图图的的任任一一个个邻邻接接矩矩阵阵作为该图的矩阵表示。作为该图的矩阵表示。第11页,共30页,编辑于2022年,星期一第12页,共30页,编辑于2022年,星期一性质性质:A(D)A(D)中所有元素之和为中所有元素之和为D D中长度为中长度为1 1的通路总数,其中的通路总数,其中 主对角线元素之和为主对角线元素之和为D D中长度为中长度为1 1的回路(环)的总数。的回路(环)的总数。第13页,共30页,编辑于2022年,星期一
6、邻接矩阵可展示相应图的一些性质:邻接矩阵可展示相应图的一些性质:若邻接矩阵的元素全为零,则其对应的图若邻接矩阵的元素全为零,则其对应的图是零图;是零图;若邻接矩阵的元素除主对角线元素外全为若邻接矩阵的元素除主对角线元素外全为1,则其对应的图是连通的且为简单完全图。,则其对应的图是连通的且为简单完全图。第14页,共30页,编辑于2022年,星期一第15页,共30页,编辑于2022年,星期一此外,当给定的简单图是此外,当给定的简单图是无向图无向图时,邻接时,邻接矩阵是矩阵是对称对称矩阵;反之,若给定任何对称矩阵矩阵;反之,若给定任何对称矩阵A,显然可以唯一地作出以,显然可以唯一地作出以A为其邻接矩
7、阵的简单为其邻接矩阵的简单图图G。于是,所有。于是,所有n个结点的不同编序的简单图个结点的不同编序的简单图的集合与所有的集合与所有n阶对称矩阵的集合可建立阶对称矩阵的集合可建立一一对一一对应。应。第16页,共30页,编辑于2022年,星期一当所给图是当所给图是简单有向图简单有向图时,其邻接矩阵时,其邻接矩阵并并非非一定是一定是对称对称矩阵,但所有矩阵,但所有n个结点的不同编序个结点的不同编序的简单图的集合,与所有的简单图的集合,与所有n阶邻接矩阵的集合亦阶邻接矩阵的集合亦可建立一一对应。可建立一一对应。不仅如此,通过对矩阵元素的一些计算还不仅如此,通过对矩阵元素的一些计算还可以得到对应图的某些
8、数量的特征。可以得到对应图的某些数量的特征。第17页,共30页,编辑于2022年,星期一由给定有向图由给定有向图由给定有向图由给定有向图D D的邻接矩阵的邻接矩阵A可计算出矩阵可计算出矩阵A A的的l l次幂,即次幂,即A Al。第18页,共30页,编辑于2022年,星期一在在在在一一一一些些些些实实实实际际际际问问问问题题题题中中中中,有有有有时时时时要要要要判判判判定定定定图图图图中中中中结结结结点点点点v vi i到到到到结结结结点点点点v vj j是是是是否否否否可可可可达达达达,或或或或者者者者说说说说v vi i到到到到v vj j是是是是否否否否存存存存在在在在一一一一要要要要链
9、链链链(或或或或通通通通路路路路)。如如如如果果果果要要要要利利利利用用用用图图图图D D的的的的邻邻邻邻接接接接矩矩矩矩阵阵阵阵A A,则则则则应应应应计计计计算算算算A A2 2,A A3 3,A An n,。当当当当发发发发现现现现其其其其中中中中某某某某个个个个A Ar r中中中中 1 1,就就就就表表表表明明明明v vi i可可可可达达达达v vj j或或或或v vi i到到到到v vj j存存存存在在在在一一一一条条条条链链链链(或或或或通路)。但这种计算繁琐量大,又不知计算通路)。但这种计算繁琐量大,又不知计算通路)。但这种计算繁琐量大,又不知计算通路)。但这种计算繁琐量大,又不
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第七 基本概念 PPT 讲稿
限制150内