[其它课程]Chapter71-72图与网络规划.ppt

  1. 1、本文档共31页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[其它课程]Chapter71-72图与网络规划

作业 P224~P225: 2,3; * * * * * * * * * * * 第7章 图与网络规划 7.1 图的基本概念 图的基本概念 1.引言 如果用节点来代表事物,用连接两个节点之间的边来表示事物之间的联系,那么现实中的许多问题都可以用图论的语言来描述。 如,互联网,电话网,供应链网络,下水管道网络,天然气管道网络,朋友之间的友谊网络,亲戚关系网络等等 Power-law distribution Scale-free Network 举例:群体中的朋友关系网络 内容框架 一、??图的基本概念(讨论思路) G=(V,E) 子图 矩阵表示 含元素的个数 点的次 边 特殊的图 点边关系 简单图 多重图 空 图 连通图 树 支撑树 空 图 不含边 G=(V,E) 矩阵表示 A 邻接矩阵 B 关联矩阵 C 割集矩阵 L 圈矩阵 M 可达矩阵 D 距离矩阵 边e=[u,v] 关联边 端点 重合 环 自回路 多重边 平行边 多于1条边 简单图 不含 多重图 含 点的次 0 1 奇数 偶数 子图 真子图 支撑子图 导出子图 孤立点 悬挂点 奇点 偶点 悬挂边 顶点数p 边数q 点边关系 各种链的概念 点边关系 真子图 支撑子图 导出子图 各种链的概念 通路 树 (6个等价定义) 连通图 支撑树 有向 、无向 图的概念 1.图的定义:图G(V, E)是顶点和边的集合。 表示顶点的集合(节点集); 表示边的集合(边集)。 图常用来描述系统的拓扑结构 节点代表具有相同属性的事物 边代表事物之间的各种关系或联系 图7-1 有关图的概念,以图7-1为例 顶点集 : 边集 : 4.端点与关联边 :若 ,则称节点 是边 的端点;而边 称为与节点 关联的边。 5.相邻点与相邻边 :若 与同一条边相关联,则称 为相邻点;若两条边 有同一个端点,则称 为相邻边。 2.图G的顶点数 :集合V中元素的个数。 3.图G的边数 : 集合E中元素的个数 。 6.环:若一条边的两个端点(起点和终点)是同一个顶点,称该边为环(loop)。 7.多重边或平行边:若两个端点之间有不止一条边,则称为多重边或平行边,包含这种边的图叫多重边图。无环也无多重边的图称为简单图。 8.次(度):节点作为边的端点的次数(或与该节点邻接的边数)叫做该节点的次或度(Degree)。 9.奇数节点(奇点)—度为奇数的节点。 偶数节点(偶点)—度为偶数的节点。 10.悬挂点与悬挂边:度为1 的点称为悬挂点,与悬挂点连接的边称为悬挂边 。 11.孤立点:度为0的点叫孤立点 12.空图:若图G中所有点都是孤立点,则称图G为空图 。 图的连通性 1.链的概念 :在图G中,由两两相邻的点 及其相关联的边 构成的点边序列 (其中 与 关联)称为链。其中 称为链的起点,称为链的终点。 2.开链与闭链 :若 ,则称该链为开链,反之称为闭链或回路。 3.若链中所含的边均不相同,则称为简单链;若点均不相同,则称为初等链或通路。除起点和终点外点均不同的闭链,称为初等回路或圈。 4.若一个图的任意两点之间均至少有一条通路(初等链)连接起来,则称这个图G是一个连通图,否则称作非连通图。如果一个问题所对应的图是一个非连通图,则该问题一定可以分解成互不相关的子问题来加以研究,即可以把不连通的图分解成连通的子图来考虑。 有向图 1. 无向图:边是没有方向的,如沟通关系 。 2. 有向图:边是有方向的, ,如谁指挥谁的关系,表示为 ,V是顶点集,A是有向边的集合 。 3. 有向图中的链:在不考虑方向时,可以与无向图一样定义链。 4. 有向图中的路与初等路:若有向图 中,P是从u到v的链,且对P中每一条弧而言,在序列中位于该弧前面的点恰好是其起点,而位于该弧后面的点恰好是其终点,这个链P就称为是D中从u到v的一条路。顶点都不相同的路称为初等路。 5. 有向图中的回路与初等回路:当有向图中路的起点和终点相同时,即 时,称作回路。除起点和终点外点均不相同的回路称为

文档评论(0)

skvdnd51 + 关注
实名认证
内容提供者

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

1亿VIP精品文档

相关文档