matlab图与网络分析模型选讲课件_第1页
matlab图与网络分析模型选讲课件_第2页
matlab图与网络分析模型选讲课件_第3页
matlab图与网络分析模型选讲课件_第4页
matlab图与网络分析模型选讲课件_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

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

文档简介

第七章图与网络分析模型选讲一、图论的基本知识1.图的概念定义图G(V,E)是指一个二元组(V(G),E(G))，其中:

(1)V(G)={v1,2v,…,nv}是非空有限集，称为顶点集，(2)E(G)是V(G)中的元素对(vi

j,v)组成的集合称为边集。图G：V(G)={v,1v2

3,4v,v}E(G)=

{e

1,2e3,4e5

6,e

,e

,e

}e3=(v1,3v

)若图G是的边是有方向的，称G是有向图，有向图的边称为有向边或弧。常用术语

e6

v2边和它的两端点称为互相关联.

e3

e1e2与同一条边关联的两个端点称

v4为相邻的顶点，与同一个顶点

e4

v3点关联的两条边称为相邻的边.

v53)端点重合为一点的边称为环.e5若一对顶点之间有两条以上的边联结，则这些边称为重边．既没有环也没有重边的图，称为简单图．v16)若图G的每一条边e都赋以一个实数w(e)，称w(e)为边e的权，G连同边上的权称为赋权图,记为：G(V,E,W)，W={w(e)|

e∈E}v27)图G的中顶点的个数，352v4v1v3称为图G的阶；图中与某个顶点相关联的边的数目，称为该顶点的度。8）完全图：若无向图的任意两个顶点之间都存在着一条边，称此图为完全图。2.图的矩阵表示邻接矩阵:(以下均假设图为简单图).图G的邻接矩阵是表示顶点之间相邻关系的矩阵：A=(a

i)j，或权值，若vi与vj

相邻其中：或∞，若vi与vj不相邻无向图G邻接矩阵A=(aij)v2v4v1v3v2543v4v11v3有向图G邻接矩阵A=(aij)v2v4v1v3v2543v4v11v3二、最大流问题定义：设G(V,E)为有向图，若在每条边e上定义一个非负权c，则称图G为一个网络，称c为边e的容量函数，记为c(e)。若在有向图G(V,E)中有两个不同的顶点vs与vt，若顶点vs只有出度没有入度，称vs为图G的源，若顶点vt只有入度没有出度，称为G的汇，若顶点v既不是源也不是汇，称为v中间顶点。v1

v284335vtvs777v4v3设u,v网络G(V,E)的相邻顶点，边(u,v)上的函数f(u,v)称为边(u,v)上的实际流量；若对网络G(V,E)的任意相邻顶点u,v均成立：0≤

f(u,v)

≤

c(u,v)

，v3v1

v28称该网络为相容网络。若v为网络G(V,E)的中间顶点，4vs有：335vt777v4网络的总流量为从源vs流出的总流量：流入汇vt总流量：v1v284335vtvs777v4v3定义：设网络G(V,E)为相容网络，u,v是G的相邻顶点，

G的容量函数为c(u,v)，实际流量函数为f(u,v)，s

v和t

v分别为G(V,E)的源和汇，V(f)为从源vs

流出的总流量，若：则称该网络称为守恒网络。守恒网

人人文库> 全部分类> 图纸下载 > 毕业设计

温馨提示

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

最新文档

评论

0/150

提交评论