运输配送图与网络分析(1)ppt课件
39页1、图与网络分析,问题提出 应用:生产组织,邮递员问题,通讯网络等。 哥尼斯堡七桥问题,哥尼斯堡七桥问题 在图中找一条经过每边一次且仅一次的路欧拉回路。,由点和边组成,“环球旅行”问题 在图中找一条经过每个点一次且仅一次的路哈密尔顿回路。,“中国邮路问题” 在图中找一条经过每边的最短路类似带权的欧拉回路。,“货郎担问题” 在图中找一条经过每个点一次且仅一次的最短路带权的哈密尔顿回路。,在实际的生产和生活中,人们为了反映事物之间的关系,常常在纸上用点和线来画出各式各样的示意图。 例1:图1是我国北京、上海、重庆等十四个城市之间的铁路交通图,这里用点表示城市,用点与点之间的线表示城市之间的铁路线。,一、图与网络的基本知识,例2:有六支球队进行足球比赛,我们分别用点v1v6表示这六支球队。它们之间的比赛情况,也可以用图反映出来,已知v1队战胜v2队,v2队战胜v3队,v3队战胜v5队,如此等等。这个胜负情况,可以用图2所示的有向图反映出来。,一、图与网络的基本知识,1.图的基本概念,例 1: 铁路交通图 例 2: 球队比赛图 点: 表示研究对象. 连线:表示两个对象之间的某种特定关系。 关系的对
2、称性:两对象之间的关系可互换。,边:不带箭头的联线,表示对称关系。 弧:带箭头的联线,表示不对称关系。 无向图:简称图,由点和边组成。 表示为: G=(V,E) V-点集合 E-边集合 例:右图,V=v1,v2,v3,v4 E=e1,e2,,e7 e1=v1,v2e2=v1,v2, ,e7=v4,v4,有向图:由点和弧组成。表示为: D=(V,A) V-点集合 A-弧集合 点数: p(G) 或 p(D) 边数: q(G) 弧数:q(D),例:右图 V=v1,v2,v5 A=a1,a2,a7 a1=v1,v5,a2=v5,v4,a7=v1,v4,无向图的有关概念,端点: e=u,vE, 则u,v是e的端点, 称u,v相邻. 关联边: e是点u,v的关联边. 环: 若u=v, e是环. 多重边: 两点之间多于一条边. 简单图: 无环,无多重边的图. 多重图: 无环,允许有多重边的图.,次: 以点v为端点的边的个数称为v的次. 表示为: d(v) 悬挂点: 次为1的点. 悬挂边: 悬挂点的关联边. 孤立点: 次为0的点. 奇点: 次为奇数的点. 偶点: 次为偶数的点.,孤立点,悬挂边,定理1
3、: 图G=(V,E)中,所有点的次之和是边数的两倍, 即:,定理2: 任意一图中, 奇点的个数为偶数. 证明:设 V1-奇点的集合, V2-偶点的集合,偶数,偶数,偶数,一、树及其性质 在各种各样的图中,有一类图是十分简单又非常具有应用价值的图,这就是树。树在自然科学和社会科学,特别是在计算机科学领域中有广泛的应用。 例:已知有六个城市,它们之间要架设电话线,要求任意两个城市均可以互相通话,并且电话线的总长度最短。,第二节 树,六个城市的一个电话网就作成一个图。 这个图必须是连通图。 这个图必须是无圈的。 图是一个不含圈的连通图,代表了一个电话线网。,再比如,乒乓球单打比赛抽签后的对阵形式以及企业的组织结构图等。,第二节 树,二、图的生成(支撑)树 定义15 设图K=(V,E)是图G=(V,E)的一生成(支撑)子图,如果图K=(V,E)是一个树,那么称K是G的一个生成树。 G中属于生成树的边称为树枝,不在生成树上的边称为弦。例如,图3b 是图3a 的一个生成树。,显然,如果图K=( V, E )是图G=(V, E)的一个生成树,那么K 的边数是n(G)-1,G中不属于生成树K的边数是m
《运输配送图与网络分析(1)ppt课件》由会员bin****86分享,可在线阅读,更多相关《运输配送图与网络分析(1)ppt课件》请在金锄头文库上搜索。
高考语文第一轮总复习 同步测试卷(五)实用类文本阅读课件
高考语文第一轮总复习 写作总论课件
高考语文大一轮复习 第5部分 论述类文本阅读 第一节 理解文中重要词句含意2大考点课件
高考语文大一轮复习 第3部分 古代诗文阅读 专题三 默写常见的名句名篇课件
高考语文大一轮复习 第3部分 古代诗文阅读 专题二 第四节 鉴赏诗歌的艺术技巧课件
高中物理 第四章 力与运动 第一节 伽利略的理想实验与牛顿第一定律课件 粤教版必修1
高中物理 第三章 研究物体间的相互作用 第三节 力的等效和替代课件 粤教版必修1
高中物理 第一章 运动的描述 第五节 速度变化的快慢 加速度课件 粤教版必修1
高中物理 第2章 能的转化与守恒章末复习方案与全优评估课件 鲁科版必修2
高中物理 42 实验:探究加速度与力、质量的关系课件 新人教版必修1
高中物理 31《受力分析》课件 新人教版必修1
高中物理 22 匀变速直线运动的速度与时间的关系课件 新人教版必修1
高中物理 14 用打点计时器测速度课件 新人教版必修1
高中数学第一章导数及其应用1_5_1曲边梯形的面积课件新人教a版选修2_2
高中数学 第二章 随机变量及其分布 24 正态分布课件 新人教a版选修2-31
高中数学 第四章 圆与方程 42_1 直线与圆的位置关系课件 新人教a版必修21
高中数学 第二章 随机变量及其分布 21_2 离散型随机变量的分布列(2)课件 新人教a版选修2-31
高中数学 第二章 统计 23_2 两个变量的线性相关课件 新人教a版必修3
高中数学 第二章 统计 22_1 用样本的频率分布估计总体分布课件 新人教a版必修3
高中数学 第二章 统计 21_3 分层抽样课件2 新人教a版必修31
2024-04-08 16页
2024-04-08 55页
2024-04-06 35页
2024-04-06 38页
2024-04-06 25页
2024-04-06 22页
2024-04-06 17页
2024-03-21 31页
2024-03-21 33页
2024-02-20 68页