版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、HomeHomeOperational Research2Operational Research3哥尼斯堡七桥问题哥尼斯堡七桥问题CBADBCAD从岸上某点出发,能否从岸上某点出发,能否恰好经过每座桥一次又回到出发点?经过每座桥一次又回到出发点?如果可以,路线如何?如果可以,路线如何?Operational Research4哥尼斯堡七桥问题哥尼斯堡七桥问题CBADBCAD问:从岸上某点出发,能否问:从岸上某点出发,能否恰好经过每座桥一次又回到出发点?如果可经过每座桥一次又回到出发点?如果可以,路线如何?以,路线如何?答:欧拉(答:欧拉(17361736)认为图中每个点都是奇数连线,因此无法
2、完成)认为图中每个点都是奇数连线,因此无法完成Operational Research5 用点描述事物; 用连线表示事物与事物之间的联系; 点和连线的集合称为Operational Research6 无向连线称“边”(Edge),记为u,v 有向连线称“弧”(Arc),记为(u,v)无向图,GV,E有向图,DV,Ax1x2y1y2v1v2v3BCADOperational Research7如果一个点是某条连线的端点,则称这个点与这条连线关联。若两条连线有一个共同的端点,则这两条线是相邻的;若两个顶点分别是一条线的两个端点,则这两个顶点也是相邻的。请注意,线包括边和弧BCADOperatio
3、nal Research8连接同一顶点的边是环。两点之间有多于一个的边。无环且无平行边的图。BCADOperational Research9以点v为端点的边或弧的个数称为点v的度或次,记作d(v)。其中环计数两次。奇点、偶点:奇数次的点称奇点,偶数次的点称偶点。一个图如果边集(或弧集)为空集,则称该图为空图。比如一些孤立点组成的图。即:没有边的图是空图。 孤立点:空图的点,或次为零的点,称为孤立点。仅与一条边或弧相关联(即相连)的点,称为悬挂点。悬挂点的关联边称为悬挂边 一个有向图,如果某个顶点只做弧的起始点,则称该点为发点或源点;如果某个顶点只做弧的终点,则称该点为收点或沉点。 Opera
4、tional Research10设G1=V1 , E1,G2 =V2 ,E2。如果 V2 V1 , E2 E1,则称 G2 是G1 的子图。设G1=V1 , E1,G2 =V2 ,E2。如果 V2 V1 , E2 E1 称 G2 是G1 的真子图。 G1=V1 , E1,G2 =V2 ,E2。如果 V2V1 , E2 E1 称 G2 是G1 的部分图或支撑子图、生成子图。 Operational Research11v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)(真)子图v1v2v3v4v5v6v7e1e6e7
5、e9e10e11(c)支撑子图原图Operational Research12在无向图G=V, E中,由两两相邻的点及其相关联的边构成的点边序列称为链。如:(v0,e1,v1,e2,v2,e3,v3 ,vn-1, en,vn),可简单记作(v0,v1,v2,v3 ,vn-1,vn)。其链长为 n ,其中v0,vn分别称为链的起点和终点。若链中所含的边均不相同,即无重复边,则称此链为简单链;所含的点均不相同的链称为初等链。初等链一定是简单链,但反之则不一定。即:无重复点一定无重复边,反之不一定Operational Research13在一个有向图中,从起点开始沿着弧的正向前进,经过一系列的点、
6、弧交替到达终点,形成的这个序列称为路。如:(v0,a1,v1,a2,v2,a3,v3 ,vn-1, an,vn),其中a1的起点是终点是,其它弧类似。路也可简单记作(v0,v1,v2,v3 ,vn-1,vn)。其中v0,vn分别称为路的起点和终点。 非正向前进的弧的序列也称链和圈。Operational Research14任意两点之间均至少有一条链或路,则称此图为连通图,否则称为不连通图。以下哪些是连通图?Operational Research15树:无向图,记为“T”生成树: 若T=(V,E)是无向图,是G=(V,E)的生成子图,且T=(V,E)是一个树,则称T是G的生成树。 v2v1v
7、3v4v5e1e6e5e7v2v1v3v4v5e1e6e5e7Operational Research16一个连通图N(V,E),若在集合V中,指定了起点、终点和中间点;在边的集合E中,任意一边都赋予权bij,这样的图称为网络。V1V2V4V3432143210110101111010110,vvvvAvvvvGOperational Research17一个连通图N(V,E),若在集合V中,指定了起点、终点和中间点;在边的集合E中,任意一边都赋予权bij,这样的图称为网络。V1V2V4V3432143210000100011000110,vvvvAvvvvDOperational Resea
8、rch18V1V2V3V443215432111000101100110100011,vvvvAeeeeeGe1e2e3e4e5Operational Research19V1V2V3V4e1e2e3e4e543215432111000101100110100011,vvvvAeeeeeGOperational Research20Operational Research21顶点已知,顶点间设置通道的长度已知,如何才能使总长度最小Operational Research22最短路问题简单地说就是找出图或网络中两个顶点之间的最短距离,的提法较多,但实质是一致的。一般提法为:设G为连通图(有向或无向),已知图中各边的权值lij,要求找出这两点之间权值之和最小的链(或路)。v1v2v3v4v6v5352242421Operational Research232v1v3v4v5v6v7v13 (5)9 (3)4 (1)5 (3)6(3)5
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 二零二五版港口工程保险合同3篇
- 二零二五版涵洞工程环保监测合同3篇
- 二零二五版反担保合同模板:供应链金融3篇
- 二零二五年计时工劳动合同管理与心理关怀协议3篇
- 二零二五年度软件开发项目合同及其廉洁规定2篇
- 二零二五版教育SaaS平台软件服务合同3篇
- 二零二五版粉煤灰运输安全规范与应急预案编制合同3篇
- 二零二五年度特种饲料原料采购合同模板2篇
- 二零二五年防火墙安全防护系统集成与维护合同3篇
- 二零二五年度大数据中心建设与运营劳务分包合同3篇
- 2024版塑料购销合同范本买卖
- 二年级下册加减混合竖式练习360题附答案
- 大三上-诊断学复习重点
- 应收账款的管理培训课件
- 2021年道路交通安全法期末考试试题含答案
- 股东变更情况报告表
- 自带药物治疗告知书
- 房产中介门店6S管理规范
- 吞咽解剖和生理研究
- TSG11-2020 锅炉安全技术规程
- 异地就医备案个人承诺书
评论
0/150
提交评论