图论.ppt

图论 图论问题的经典例子 哥尼斯堡七桥问题和欧拉图 环球旅行问题和汉密尔顿回路 中国邮递员问题 货郎担问题 哥尼斯堡城中流过一条河，河上有2岛和7桥。18世纪的人热衷一个问题：一个人怎么连续走过所有桥仅一次回到出发点。你能想出答案么？ 欧拉将其转换为右图，并将问题归结为:能否从ABCD任一点出发，走过所有边仅一次，回到出发点。能这样被画出的图也被称为欧拉图。 左图中共有20个点,代表世界20个城市,问能否从任一城市出发，经过所有城市仅一次回到出发点。 也可归结为:能否从图中任一点出发,经过每点仅一次回到出发点。该问题由汉密尔顿提出,这样的回路也称为汉密尔顿回路。 欧拉回路:经过每边仅一次 汉密尔顿回路:经过每点仅一次 中国邮递员问题 一个邮递员从邮局出发要走遍所负责的每条街道，问如何走法路程最短。 从图中一点出发，走遍所有边回到出发点的最短路。 从图中一点出发，一笔画出该图并回到出发点的最短路。（总路权最小的欧拉图） 由山东师范大学的管梅谷在1962年首次提出，国际上称此问题为中国邮路问题。 货郎担问题 一个货郎要去各村卖货。他如何走遍所有村庄仅一次再回到他的村，并使路程最短。 一个旅行者如何走过所有目的城市仅一次回到出发地，且使总路程最短。 这显然是求总路权最小的汉密尔顿回路。 基本概念 图，边，弧，无向图，有向图 两点相邻和关联边; 环,多重边,简单图,多重图 链,圈,初等链,初等圈 连通图,不连通图 路,回路 点的次，奇点,偶点 次和偶数定理,奇点成对定理 基本概念 图：由点和点间连线组成。常用Vi表示点。 边：点间不带箭头的连线。常用(Vi,Vj)表示。 弧：点间带箭头的连线。也常用(Vi,Vj)表示。 无向图：由边组成 有向图：由弧组成 基本概念 两点相邻：边或弧的端点被称为相邻的。 关联边：有公共端点的边称为关联边。 环：端点合二为一的边称为环。 多重边： 两点间若有多于一条的边，则称所有这些边为多重边。 简单图：无环，无多重边的图。 多重图：无环，有多重边的图。 基本概念 链：首尾相连的边组成链。用点的序列V1V2…Vk表示。其中V1为始点,Vk为终点。 如图中ADBC就是链。 圈：始点和终点重合的链。 如图中ABDA就是圈。 初等链:无重复点的链 初等圈:无重复点的圈 连通图:各点间至少有一条 链相连的图(各点都连着) 否则为不连通图 基本概念 路：首尾相连的弧构成路。 图中CBAD就是路。 回路：起点,终点重合的路 图中ADBA就是回路。 基本概念 点的次：和某点相连的边数。 图中各点的次： A-3，B-5，C-3，D-3 奇点：次为奇数的点 偶点；次为偶数的点 图中所有点均为奇点 定理1:各点次和为偶数 定理2:奇点成对出现 中国邮路问题 欧拉链：过图中所有边一次且仅一次的链。 有欧拉链的图能一笔画出，但起止点不同。 欧拉圈：过图中所有边一次且仅一次的圈。 有欧拉圈的图也能一笔画出，且起止点重合。 欧拉图：有欧拉圈的图。 定理：一个图有欧拉链 图中恰有2个奇点 定理：一个图是欧拉图 图中无奇点 中国邮路问题：走遍所有街道至少一次，并回到邮局的最短路。等价于,始于某点一笔画出某图并止于该点的最短路。显然这要求图中存在欧拉圈。问题也转化为求总路权最小的欧拉圈。 中国邮路问题 如果一个图是欧拉图，那么沿各边走一遍即可。 如果一个图不是欧拉图，奇点必成对出现。 加边成对连接奇点，即可转为欧拉图。 加边原则：加边不超其圈的一半。 此法称为：奇偶点作业法 加边成对连奇点，且不过圈半。 定理：一个图是欧拉图 图中无奇点 中国邮路问题：走遍所有街道至少一次，并回到邮局的最短路。等价于,始于某点一笔画出某图并止于该点的最短路。显然这要求图中存在欧拉圈。问题也转化为求总路权最小的欧拉圈。 中国邮路问题 此法称为：奇偶点作业法 加边成对连奇点，且不过圈半。 奇偶点作业法只适用于简单的小图，因为它要求所加边不超过任何一个圈的一半，这很困难。因此该法不是求解中国邮路问题最有效的方法。 下面以P279例16为例，说明此法。 中国邮路问题 奇偶点作业法： 加边成对连奇点，且不过圈半。 中国邮路问题 奇偶点作业法：加边成对连奇点，且不过圈半。 图中奇点为V2,V4,V6,V8。 将V2,V4和V6,V8配对 观察圈V2V3V4V9V2 加边已过半,需反向调整。 观察圈V1V2V6V7V1 加边已过半,需反向调整。 经观察在任一圈内所 加边均未过半,是最优解 树的6个等价定义 无圈连通的图 连通且边数=点数-1 无圈且边数=点数-1 任何两点间有唯一链 无圈，但加