已阅读5页,还剩64页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第十一章图与网络规划11.1图与网络的基本概念11.2树及最小树问题11.3最短路问题11.4网络最大流问题11.1图与网络的基本概念图的概念所谓图,就是顶点和边的集合,点的集合记为V,边的集合记为E,则图可以表示为:G(V,E),点代表被研究的事物,边代表事物之间的联系,因此,边不能离开点而独立存在,每条边都有两个端点。在画图时,顶点的位置、边和长短形状都是无关紧要的,只要两个图的顶点及边是对应相同的,则两个图相同。图的表示,211e,212e,413e,314e,315e,426e,437e,448e,549e),(),(987654321654321eeeeeeeeeEe1e2e3e4e5v2v3v1v4v5v6e6e7e8e9点与边顶点数集合V中元素的个数,记作p(G)。边数集合E中元素的个数,记作q(G)。若e=u,vE,则称u和v为e的端点,而称e为u和v的关联边,也称u,v与边e相关联。例如图中的图G,p(G)=6,q(G)=9,v1,v2是e1和e2的端点,e1和e2都是v1和v2的关联边。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9点边关系若点u和v与同一条边相关联,则u和v为相邻点;若两条边ei和ej有同一个端点,则称ei与ej为相邻边。例如在图中v1和v2为相邻点,v1和v5不相邻;e1与e5为相邻边,e1和e7不相邻。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9简单图若一条边的两个端点是同一个顶点,则称该边为环;又若两上端点之间有多于一条边,则称为多重边或平行边。例如图的e8为环,e1,e2为两重边,e4,e5也是两重边。含有多重边的图称作多重图。无环也无多重边的图称作简单图。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的次次点v作为边的端点的次数,记作d(v),如图中,d(v1)=5,d(v4)=6等端点次为奇数的点称作奇点;次为偶数的点称作偶点。次为1的点称为悬挂点,与悬挂点连接的边称作悬挂边;次为0的点称为孤立点。图中的点v5即为悬挂点,边e9即为悬挂边,而点v6则是弧立点。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9定理若图G中所有点都是孤立点,则称图G为空图。定理1所有顶点的次的和,等于所有边数的2倍。即qdV2)(e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9定理2在任一图中,奇点的个数必为偶数。设V1和V2分别是图G中次数为奇数和偶
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《现代通信网络技术》课件第1章
- 中考数学压轴题归类复习(十大类型附详细解答)
- 生物科技生物实验室项目环评可研资料环境影响
- 幼儿园园长安全管理制度 幼儿园园长安全管理职责(3篇)
- 环保减排措施方案
- 第二十七章《相似》小结与复习课件- 2022-2023学年九年级数学人教版下册
- 胃十二指肠护理课件
- 现代无菌技术原则课件
- 2024八年级数学上专题6 八年级数学上册期中考试重难点题型(举一反三)含答案
- 【数学】二元一次方程组章末培优专练过素养综合素养创新应用课件-2023-2024学年人教版数学七年级下册
- 【案例】新能源数字孪生智慧运维
- 体育与健康课程标准水平一.doc
- 可定时显示报警系统的设计-VB编程毕业设计
- 收费站人员配置方案21528
- 中标奖励及处罚
- 公路预制T梁梁场建设及T梁预制施工技术指南
- 学校突发事件应急预案及处置流程
- 线路隐蔽工程验收表.doc
- 教科版四年级下册综合实践活动教案主题九:清洁工具的设计和改造
- 异地就医定点医疗机构证明.doc
- 肿瘤的中医研究现状
评论
0/150
提交评论