第7章图1-4.pptVIP

  1. 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
  2. 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  3. 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  4. 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  5. 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  6. 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  7. 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第7章图1-4

第7章 图 图(Graph)是一种较线性表和树更为复杂的非线性结构。 在线性结构中,结点之间的关系是线性关系,除开始结点和终端结点外,每个结点只有一个直接前趋和直接后继。 在树形结构中,结点之间的关系实质上是层次关系,同层上的每个结点可以和下一层的零个或多个结点(即孩子)相关,但只能和上一层的一个结点(即双亲)相关(根结点除外)。 在图结构中,对结点(图中常称为顶点)的前趋和后继个数都是不加限制的,即结点之间的关系是任意的。图中任意两个结点之间都可能相关。 由此,图的应用极为广泛,特别是近年来的迅速发展,已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。 7.1 图的概念 图(Graph):G由两个集合V和E组成,记为G=(V,E),其中V是顶点的有穷非空集合,E是V中顶点偶对(称为边)的有穷集。通常,也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集,若E(G)为空,则图G只有顶点而没有边。 有向图(Digraph) :若图G中的每条边都是有方向的,则称G为有向图。在有向图中,一条有向边是由两个顶点组成的有序对,有序对通常用尖括号表示。例如<vi,vj>表示一条有向边,vi是边的始点(起点),vj是边的终点。因此,<vi,vj>和<vj,vi>是两条不同的有向边。有向边也称为弧(Arc),边的始点称为弧尾(Tail),终点称为弧头(Head)。 无向图(Undigraph): 若图G的每条边是没有方向的,即关系集合E(G)中,顶点偶对(v,w)的v和w之间是无序的,称图G是无向图。 在无向图中,若?v,w?E(G) ,有w,v?E(G) ,即E(G)是对称,则用无序对(v,w) 表示v和w之间的一条边(Edge),因此(v,w) 和(w,v)代表的是同一条边。 例1:设有有向图G1和无向图G2,形式化定义分别是: G1=(V1 ,E1) V1={a,b,c,d,e} E1={a,b,a,c, a,e,c,d,c,e ,d,a,d,b,e,d} G2=(V2 ,E2) V2={a,b,c,d} E2={(a,b), (a,c), (a,d), (b,d), (b,c), (c,d)} 它们所对应的图如图7-1所示。 有向完全图(Directed Complete Graph):对于有向图,若图中顶点数为n ,用e表示弧的数目,则e?[0,n(n-1)] 。具有n(n-1)条边的有向图称为有向完全图。 完全有向图另外的定义是: 对于有向图G=(V,E),若?vi,vj?V ,当vi ≠vj时,有vi ,vj?E∧vj , vi ?E ,即图中任意两个不同的顶点间都有一条弧,这样的有向图称为有向完全图。 邻接点(Adjacent): 对于无向图G=(V,E),若边(v,w)?E,则称顶点v和w 互为邻接点,即v和w相邻接。并称边(v,w)关联(incident)于与顶点v和w ,或称(v,w) 与顶点v和w 相关联。 对于有向图G=(V ,E),若有向弧v,w?E,则称顶点v “邻接到”顶点w,顶点w “邻接于”顶点v ,弧v,w 与顶点v和w “相关联” 。 顶点的度、入度、出度:对于无向图G=(V,E), ?vi?V,图G中关联于vi的边的数目称为顶点vi的度(degree),记为D(vi)。 显然,在无向图中,所有顶点度的和是图中边的2倍。 即 ∑D(vi)=2e i=1, 2, …, n ,e为图的边数。 对有向图G=(V,E),若?vi ?V ,图G中以vi作为起点的有向边(弧)的数目称为顶点vi的出度(Outdegree),记为OD(vi) ;以vi作为终点的有向边(弧)的数目称为顶点vi的入度(Indegree),记为ID(vi) 。顶点vi的出度与入度之和称为vi的度,记为D(vi) 。即 D(vi)=OD(vi)+ID(vi) 子图和生成子图:设有图G=(V,E)和G’=(V’,E’),若V’?V,E’?E ,且E’中的边所关联的顶点均在V’中,则称图G’是G的子图;若V’=V且E’?E,则称图G’是G的一个生成子图。 路径(Path)、路径长度、回路(Cycle) : 路径: 在无向图G=(V,E)中,若存在一个顶点序列vp ,vi1 ,vi2 ,…, vin,vq,使得 (vp ,vi1 ),(vi1 ,vi2 ),…,(vin,vq)均属于E(G),则称顶点vp和vq存在一条路径。 若在有向图G=(V,E)中,则路径也是有向的,它由E(G) 中的有向边vp ,vi1,vi1 ,vi2 ,…,vin,vq 组成。 路径长度:路径上边的数目。

文档评论(0)

xy88118 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档