重庆大学工商管理学院信息系：《运筹学》第七章 图与网络（熊中楷）

运糖 92g 图与网络(1) 运学 狼中

运筹学 熊中楷教授 图与网络（1）

第七章图与网络(1) 引例:阿富汗战后建设,30个村庄要通电话,已知两两距离,如 何用最少的电话线连通30个村庄? 村庄2 10 村庄 12 村庄1 村庄3 村庄4 村庄6 运学 狼中描教

运筹学 熊中楷教授 村庄1 引例： 阿富汗战后建设， 30个村庄要通电话，已知两两距离，如 何用最少的电话线连通30个村庄？ 村庄4 村庄3 村庄6 村庄2 村庄5 6 3 11 5 9 8 10 7 7 第七章 图与网络（1） 12

第七章图与网络(1) 网络结构 OA、EMA主机 内网WWW服务器 骨干交换机 楼层交换机 骨干交换机 外网WWW服务器 网管工作站 防火墙 楼层交换 CISCO路由器 用户工作站 PSIN Internet 移动办公 运学 其它部门 熊中

运筹学 熊中楷教授 第七章 图与网络（1） 网络结构 R Internet DNS、内网WWW服务器 外网WWW服务器 楼层交换机 防火墙 网管工作站 OA骨干交换机 楼层交换机 用户工作站 CISCO 路由器 骨干交换机 PSTN 移动办公 DCN 其它部门 OA、EMAIL主机 R

第七章图与网络(1) 网络拓扑结构 树型 混合型 狼中描教

运筹学 熊中楷教授 网络拓扑结构 树型 混合型 第七章 图与网络（1）

第七章图与网络(1) P255例1甲乙丙丁戊五个球队,用图表示他们之间比赛 V3 运学 狼中描教

运筹学 熊中楷教授 第七章 图与网络（1） P255 例1 甲 乙 丙 丁 戊五个球队，用图表示他们之间比赛： V1 V5 V4 V3 V2

第七章图与网络(1) P255例3八种化学药品有的不能够放在同一个库房里,用图表示他们 之间关系:不能放在一起的加连线。 V4 运学 狼中描教

运筹学 熊中楷教授 第七章 图与网络（1） P255 例3 八种化学药品有的不能够放在同一个库房里，用图表示他们 之间关系：不能放在一起的加连线。 V8 V4 V3 V2 V1 V5 V6 V7

第七章图与网络(1) 第七章:图与网络(1) 环:一条边两个端点相同 1.引例(P256) 多重边:两个点之间多于一条边 1.图与网络的基本概念: 简单图:无环,无多重边 边:两点间没有箭头的连线两点间有箭头的连线称为弧小多重图:无环,有多重边 无向图:由点和边构成的,无向图简称为图 次:端点的边的数目 有向图:由点和弧构成的 孤立点:次为0的点 端点:一条边vV2,V,V2称为边的端点 悬挂点:次为1的点 相邻:一条边V1V2,V1,V称为相鄰 悬挂边:与悬挂点关联边 关联边:一条边vv,称为端点V,V2的关联边 链 联通图:图中任意两个点至少 链的中间点 有一条链 初等链:链中的点都不相同 联通分图:不联通图,每个联通部分 圈:一条链首尾相同 图的支承?子图:包括图的全部顶点 初等圈:圈中的点都不相同 并且包括图的部分边 简单圈:链中的边都不相同 运学 熊中描教

运筹学 熊中楷教授 第七章 图与网络（1） 第七章：图与网络（1） 1．引例（P256） 1. 图与网络的基本概念： 边：两点间没有箭头的连线，两点间有箭头的连线称为弧。 无向图：由点和边构成的，无向图简称为图。 有向图：由点和弧构成的 端点：一条边V1V2, V1,V2 称为边的端点 相邻：一条边V1V2, V1,V2 称为相鄰 关联边：一条边V1V2, 称为端点V1,V2的关联边 环：一条边两个端点相同 多重边：两个点之间多于一条边 简单图：无环，无多重边 多重图：无环，有多重边 次：端点的边的数目 孤立点：次为0的点 悬挂点：次为1的点 悬挂边：与悬挂点关联边 链： 链的中间点： 初等链：链中的点都不相同 圈：一条链首尾相同 初等圈：圈中的点都不相同 简单圈：链中的边都不相同 联通图：图中任意两个点至少 有一条链 联通分图：不联通图，每个联通部分 图的支承?子图：包括图的全部顶点 并且包括图的部分边

第七章图与网络(1) Chapter 7: Graph and Network(1) 1. exampl 2. some basic concept of graph and network no direction graph direction graph node adjacent relating are multiple-layer arcs simple graph multiple-layer graph number of connected are with the node node without connected are node only one connected arc 运学 狼中描教

运筹学 熊中楷教授 第七章 图与网络（1） Chapter 7: Graph and Network(1) 1. example 2. some basic concept of graph and network: no direction graph direction graph node adjacent relating arc loop multiple-layer arcs simple graph multiple-layer graph number of connectedarc with the node node without connectedarc node only one connectedarc

第七章图与网络(1) Tree and the shortest path problems 树与最短路问题 the definition of Tree. (1)树的定义 (2)Property I of Tree (2)树的性质1 Property 2 of Tree 树的性质2 Property 3 of Tree 树的性质3 Property 4 of Tree 树的性质4 (3)spanning tree of graph and (3)图的支撑树及性质 (4)求图的支撑树方法 (4)method of solving the spanning 破圈法 tree of graph 避圈法 breaking loop method (5)最小支撑树及求法 avoiding loop method 破圈法 (5) minimum spanning tree and its 避圈法 solving method (6)最短路问题 breaking loop method avoiding loop method (6)shortest path problem 运学 狼中描教

运筹学 熊中楷教授 第七章 图与网络（1） 树与最短路问题 (1) 树的定义 (2) 树的性质1 树的性质2 树的性质3 树的性质4 （ 3）图的支撑树及性质 （4）求图的支撑树方法： 破圈法 避圈法 （5） 最小支撑树及求法 破圈法 避圈法 （6） 最短路问题 Tree and the shortest path problems (1) the definition of Tree. (2) Property 1 of Tree Property 2 of Tree Property 3 of Tree Property 4 of Tree (3) spanning tree of graph and its property (4) method of solving the spanning tree of graph breaking loop method avoiding loop method (5) minimum spanning tree and its solving method. breaking loop method avoiding loop method (6) shortest path problem

第七章图与网络(1) 树与最短路问题 1)树的定义:无圈的联通图 (2)树的性质1:树至少有两个悬挂点 树的性质2:是树充分必要条件:不含圈并且边数=点数 树的性质3:是树充分必要条件:联通图并且边数=点数-1 树的性质4:是树充分必要条件:任意两个点正好一条链 (3)图的支撑树及性质: 图的支撑树:图的支承?子图是树 图的支撑树性质:图有支撑树充分必要条件:图联通 (4)求图的支撑树方法: 破圈法 避圈法 运学 狼中描教

运筹学 熊中楷教授 第七章 图与网络（1） 树与最短路问题 (1) 树的定义：无圈的联通图 (2) 树的性质1：树至少有两个悬挂点 树的性质2：是树充分必要条件： 不含圈并且 边数＝点数－1 树的性质3：是树充分必要条件： 联通图并且 边数＝点数－1 树的性质4：是树充分必要条件：任意两个点正好一条链 （ 3）图的支撑树及性质： 图的支撑树：图的支承? 子图是树 图的支撑树性质：图有支撑树充分必要条件：图联通 （4）求图的支撑树方法： 破圈法 避圈法