图与网络分析本章小结课件_第1页
图与网络分析本章小结课件_第2页
图与网络分析本章小结课件_第3页
图与网络分析本章小结课件_第4页
图与网络分析本章小结课件_第5页
已阅读5页，还剩63页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第六章图与网络分析继续返回·第一节图的基本概念与模型第二节树图和图的最小部分树第三节最短路问题·第四节网络的最大流第五节最小费用流一上页下页返回§1.图的基本概念与模型·点:表示研究对象·连线:表示两个对象之间的某种特定关系。·关系的对称性:两对象之间的关系可互换。上页下页返回边:不带箭头的联线,表示对称关系。弧:带箭头的联线,表示不对称关系·无向图:简称图,由点和边组成。表示为:G=(V,E)V-点集合E-边集合有向图:由点和弧组成一表示为:D=(V,A)V-点集合A-弧集合点数:p(G)或p(D)边数:q(G)弧数:q(D上页下页返回无向图的有关概念端点:e=[u,v]∈E,则u,w是e的端点,称u,V相邻.关联边:e是点u,v的关联边环:若uu=v.e是环多重边:两点之间多于一条边简单图:无环,无多重边的图多重图:无环,允许有多重边的图.次;悬挂点;悬挂边;孤立点;奇点;偶点上页下页返回定理1:图G=(V,E)中,所有点的次之和是边数的两倍,即d(v)=2q定理2:任意一图中,奇点的个数为偶数.上页下页返回有向图的有关概念·基础图:对D=(V,A),去掉图上的箭头·始点和终点:对弧a=(u,v),u为a的始点,V一为a的终点链;圈;·道路;回路;初等路;初等回路;·简单有向图:无环,无多重弧·多重有向图:有多重弧.上页下页返回§2.树图和图的最小部分树2.1树图的性质·树图:无圈的连通无向图称为树,记作7(V,B上页下页返回树图的性质:性质1任何树图中必存在次为1的点性质2具有n个顶点的树图的边数恰好为(n-1)条→图G=(V,B),具有n个顶点,图G是树图的下列说法是等价的:(1)G连通,且恰有n-1条边(2)G无圈,且恰有n-1条边(3)G连通,但每舍去一边就不连通。(4)G无圈,但每

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论