江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析(1/2)

CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第六章图与网路分析 图是最直观的模型
©管理与人文学院 忻展红 1999,4 第六章 图与网路分析 图是最直观的模型

图论 Graph Theory 哥尼斯堡七桥问题( Konigsberg bridge problem) Leonhard euler(1707-1783)在1736年发表第一篇图论 方面的论文,奠基了图论中的一些基本定理 很多问题都可以用点和线来表示,一般点表示实体 线表示实体间的关联 A
2 B A C D 图论 Graph Theory • 哥尼斯堡七桥问题 (Königsberg Bridge Problem) • Leonhard Euler (1707-1783) 在1736年发表第一篇图论 方面的论文,奠基了图论中的一些基本定理 • 很多问题都可以用点和线来表示,一般点表示实体, 线表示实体间的关联 A B C D

6图与网路的基本概念 611图与网路 网路( Network) 节点( ertex) 边上具有表示连接强度 物理实体、事物、概念 的权值,如w 一般用v表示 又称加权图( Weighted 边(Ege) graph 节点间的连线,表示有 关联 一般用e;表示 图( Graph) 12 节点和边的集合 一般用G(V,E)表示 点集v{v1,2y,wn} 边集E={en} 图61
3 6.1 图与网路的基本概念 6.1.1 图与网路 • 节点 (Vertex) – 物理实体、事物、概念 – 一般用 vi 表示 • 边 (Edge) – 节点间的连线,表示有 关联 – 一般用 eij 表示 • 图 (Graph) – 节点和边的集合 – 一般用 G(V,E) 表示 – 点集 V={v1 ,v2 ,…, vn } – 边集E={eij } v 1 v 5 v 4 v 3 v 2 e 12 e 34 e13 e 24 e22 e'13 e 45 图 6.1 网路 (Network) 边上具有表示连接强度 的权值,如 wij 又称加权图(Weighted graph)

612无向图与有向图 所有边都没有方向的图称为无向图,如图61 在无向图中e1="n,或(v以=(v 当所有边都有方向时,称为有向图,用G(V,4)表示 在有向图中,有向边又称为弧,用a表示,i的顺序 是不能颠倒的,图中弧的方向用箭头标识 图中既有边又有弧,称为混合图
4 6.1.2 无向图与有向图 • 所有边都没有方向的图称为无向图,如图6.1 • 在无向图中 eij=eji,或 (vi , vj )=(vj , vi ) • 当所有边都有方向时,称为有向图,用G(V,A)表示 • 在有向图中,有向边又称为弧,用 aij表示,i, j 的顺序 是不能颠倒的,图中弧的方向用箭头标识 • 图中既有边又有弧,称为混合图

6.13端点,关联边,相邻,次 图中可以只有点,而没有边;而有边必有点 若节点v"之间有一条边,则称v是en的端点 ( end vertex),而t是节点v,v的关联边( incident edge) 同一条边的两个端点称为相邻 adjacent)节点,具有共同 端点的边称为相邻边 条边的两个端点相同,称为自环(se!lop);具有两个 共同端点的两条边称为平行边( parallel edges) 既没有自环也没有平行边的图称为简单图( simple graph) 在无向图中,与节点相关联边的数目,称为该节点的 次"( degree),记为d;次数为奇数的点称为奇点 (od)次数为偶数的点称为偶点(even);图中都是偶点的 图称为偶图( even graph)
6.1.3 端点,关联边,相邻,次 • 图中可以只有点,而没有边;而有边必有点 • 若节点vi , vj 之间有一条边 eij,则称 vi , vj 是 eij 的端点 (end vertex),而 eij 是节点 vi , vj 的关联边(incident edge) • 同一条边的两个端点称为相邻(adjacent)节点,具有共同 端点的边称为相邻边 • 一条边的两个端点相同,称为自环(self-loop);具有两个 共同端点的两条边称为平行边(parallel edges) • 既没有自环也没有平行边的图称为简单图(simple graph) • 在无向图中,与节点相关联边的数目,称为该节点的 “次”(degree),记为 d ;次数为奇数的点称为奇点 (odd),次数为偶数的点称为偶点(even);图中都是偶点的 图称为偶图(even graph)

6.13端点,关联边,相邻,次 有向图中,由节点向外指的弧的数目称为正次数,记为 dr,指向该节点的弧的数目称为负次数,记为d 次数为0的点称为孤立点( Isolated vertex),次数为1的 点称为悬挂点( pendant vertex) 定理1:图中奇点的个数总是偶数个 6.1.4链,圈,路径,回路,欧拉回路 相邻节点的序列{v1,v2,vn}构成一条链(link),又称 为行走(wk);首尾相连的链称为圈(op),或闭行走 在无向图中,节点不重复出现的链称为路径(pth);在 有向图中,节点不重复出现且链中所有弧的方向一致, 则称为有向路径( directed path) 首尾相连的路径称为回路( circuit);
6 6.1.3 端点,关联边,相邻,次 • 有向图中,由节点向外指的弧的数目称为正次数,记为 d +,指向该节点的弧的数目称为负次数,记为 d – • 次数为 0 的点称为孤立点(isolated vertex) ,次数为 1 的 点称为悬挂点(pendant vertex) 定理 1:图中奇点的个数总是偶数个 6.1.4 链,圈,路径,回路,欧拉回路 • 相邻节点的序列 {v1 ,v2 ,…, vn } 构成一条链(link),又称 为行走(walk);首尾相连的链称为圈(loop),或闭行走 • 在无向图中,节点不重复出现的链称为路径(path);在 有向图中,节点不重复出现且链中所有弧的方向一致, 则称为有向路径(directed path) • 首尾相连的路径称为回路(circuit);

走过图中所有边且每条边仅走一次的闭行走称为欧拉 回路 定理2:偶图一定存在欧拉回路(一笔画定理) 61.5连通图,子图,成分 设有两个图G1(V1,E1),G2(V2E2),若V2cV,E2E1, 则G2是G1的子图 无向图中,若任意两点间至少存在一条路径,则称为 连通图 connected graph),否则为非连通图( discon nected graph);非连通图中的每个连通子图称为成分 (component) 链,圈,路径简称路),回路都是原图的子图 平面图 planar graph),若在平面上可以画出该图而没 有任何边相交
7 • 走过图中所有边且每条边仅走一次的闭行走称为欧拉 回路 定理 2:偶图一定存在欧拉回路(一笔画定理) 6.1.5 连通图,子图,成分 • 设有两个图 G1 (V1 , E1 ), G2 (V2 , E2 ), 若V2 V1 , E2 E1, 则 G2 是 G1 的子图 • 无向图中,若任意两点间至少存在一条路径,则称为 连通图(connected graph),否则为非连通图( disconnected graph);非连通图中的每个连通子图称为成分 (component) • 链,圈,路径(简称路),回路都是原图的子图 • 平面图(planar graph),若在平面上可以画出该图而没 有任何边相交

62树图与最小生成树 一般研究无向图 树图:倒置的树,根(r00n在上,树叶(leug在下 多级辐射制的电信网络、管理的指标体系、家谱、分 类学、组织结构等都是典型的树图 CQ根 C2 8 C3 C4 d叶
8 6.2 树图与最小生成树 • 一般研究无向图 • 树图:倒置的树,根(root)在上,树叶(leaf)在下 • 多级辐射制的电信网络、管理的指标体系、家谱、分 类学、组织结构等都是典型的树图 C1 C2 C3 C4 根 叶

621树的定义及其性质 任两点之间有且只有一条路径的图称为树(re),记为T 树的性质 最少边的连通子图,树中必不存在回略 任何树必存在次数为1的点 具有n个节点的树T的边恰好为n-1条,反之,任何有 n个节点,n-1条边的连通图必是一棵树 622图的生成树 树T是连通图G的生成树( spanning tree),若T是G的 子图且包含图G的所有的节点;包含图G中部分指定节 点的树称为 steiner tree 每个节点有唯一标号的图称为标记图,标记图的生成树 称为标记树( Labeled tree) Caylay定理:n(≥2)个节点,有m-2个不同的标记树
9 6.2.1 树的定义及其性质 • 任两点之间有且只有一条路径的图称为树(tree),记为T 树的性质: • 最少边的连通子图,树中必不存在回路 • 任何树必存在次数为 1 的点 • 具有 n 个节点的树 T 的边恰好为 n−1 条,反之,任何有 n 个节点, n−1 条边的连通图必是一棵树 6.2.2 图的生成树 • 树 T 是连通图 G 的生成树(spanning tree),若 T 是 G的 子图且包含图 G 的所有的节点;包含图 G 中部分指定节 点的树称为 steiner tree • 每个节点有唯一标号的图称为标记图,标记图的生成树 称为标记树(labeled tree) Caylay 定理:n (2)个节点,有n n−2个不同的标记树

622图的生成树 ④④ ④④ ③①⑧①⑧①③① ·如何找到一棵生成树 深探法( depth first search):任选一点标记为0点开始搜 索,选一条未标记的边走到下一点,该点标记为1,将 走过的边标记;假设已标记到i点,总是从最新标记的 点向下搜索,若从i点无法向下标记,即与i点相关联 的边都已标记或相邻节点都已标记,则退回到i-1点继 续搜索,直到所有点都被标记 广探法( breadth first search):是一种有层级结构的搜索, 一般得到的是树形图
10 6.2.2 图的生成树 • 如何找到一棵生成树 – 深探法(depth first search):任选一点标记为 0 点开始搜 索,选一条未标记的边走到下一点,该点标记为 1,将 走过的边标记;假设已标记到 i 点,总是从最新标记的 点向下搜索,若从 i 点无法向下标记,即与 i 点相关联 的边都已标记或相邻节点都已标记,则退回到 i −1 点继 续搜索,直到所有点都被标记 – 广探法(breadth first search):是一种有层级结构的搜索, 一般得到的是树形图 A C B D A C B D A C B D A D C B
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析(2/2).ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第八章 标准服务系统(M/M/n系统).ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第五章 动态规划 Dynamic programming.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第九章 特殊随机服务系统.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第三章 运输问题——数学模型及其解法.ppt
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.4)随机变量函数的分布.ppt
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.3)连续型随机变量.ppt
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.2)离散型随机变量.ppt
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.1)随机变量的定义.ppt
- 《数学史》数学物理.ppt
- 《数学史》世界数学点点.ppt
- 浙江大学:《数学史》廿一世纪的数学展望.ppt
- 香港中文大学:《数学史》几何三十载.ppt
- 《数理统计和质量保证》教学资源(参考书籍)PDF电子版——目录.pdf
- 《数理统计和质量保证》教学资源(参考书籍)PDF电子版——正文(共十章).pdf
- 《线性代数智能CAI》电子教案:线性方程组的解.ppt
- 西南交通大学数学系:《数学模型与LINGO软件》.pdf
- 《统计分布》教学资源(书籍文献)目录.doc
- 《统计分布》教学资源(书籍文献)目录.pdf
- 《统计分布》教学资源(书籍文献)正文(共六章).pdf
- 江西财经大学:《运筹学》课程教学资源_作业题集.doc
- 江西财经大学:《运筹学》课程教学资源_教学大纲.doc
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第二章 线性规划的对偶理论及其应用(2/2)2.4 线性规划的灵敏度分析 2.5 参数线性规划.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第十章 存储理论 Inventory Theory.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第四章 整数规划.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第二章 线性规划的对偶理论及其应用(1/2)2.1 线性规划的对偶理论 2.2 线性规划的对偶定理 2.3 对偶单纯型算法.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析 6.1 图与网路的基本概念 6.2 树图与最小生成树 6.3 最短路问题 6.4 网路的最大流和最小截.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析 6.1 图与网路的基本概念 6.2 树图与最小生成树 6.3 最短路问题 6.4 网路的最大流和最小截 6.5 欧拉回路和中国邮递员问题 6.6 哈密尔顿回路及旅行推销员问题 6.7 选址问题.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第七章 随机服务理论概述.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)绪论(忻展红).ppt
- 江西财经大学:《运筹学》课程教学资源(案例)DEC 的短期制造问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)SYTECH 公司的生产优化问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)里尤尼亚的外购问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)投资基金最佳使用计划.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)项目选择问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)跨国投资问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)两辆铁路平板车的装货问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)建筑方案决策问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)建厂对策问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)匹配问题.pdf