《运筹学》6图论.ppt

G的点集合： （例如：图（1）中的 N=（1，2，3，4，5）是一个无向图 的点的集合） G的边集合：E={eij}且eij={ni,nj}为右图无序二元组 eij的端点：有eij={ni,nj}，则称ni和nj为 eij的端点，且称eij 连接点 ni和nj 环：两个端点重合为一点的边 （例如右图中的e11） 孤立点：不与任何边关联的点 （例如右图中的n5） 续（1） 关联：一条边的端点称为这条边的关联 邻接：与同一条边关联的端点称为是邻接的，同时如果两条边有一个公共端点，则称这两条边是邻接的 有限图：点和边都是有限集合的图 空图：没有任何边的图 平凡图：只有一个点的图 简单图：既没有环也没有两条边连接同一对点的图 度(次) 度的有关定理 续（2） 完全图：每一对点之间均有一条边相连的图 子 图 连通性 点i和j点是连通的：G中存在一条（i，j）通道 G是连通的：G中任意两点都是连通的 连通分支：G的极大连通子图 网络的基本概念 Kruskal算法（避圈法）步骤 第三节 最短路问题 只有一个新增元素 表示任意两点间的最短路长及其路径。 第四节 中国邮路问题 18世纪，在德国东普鲁士哥尼斯堡有七座桥，连接这七座桥的陆地有四块，如下图，一个散步者能否从四块陆地中的任意一块开始，通过每座桥恰好一次，最后回到出发点？ B C D 七 桥 问 题 定义：（Euler迹、Euler环游、Euler图） 解：1。模拟图：以顶点表陆地，以边表桥，得4个顶点的模拟图。 2。问题等价于：能否有一条闭迹包含模拟图的所有边，即：模拟图是Euler图吗？ 3。求解：假设图G是Euler图。因为闭迹是连通的，所以图G也连通。又因为每个顶点既能到达也能离开，所以图G的每个顶点度都是偶数。 所以，欧拉在1736年得出结论：“七桥问题”是不可能的，同时开创了图论的研究。 含图G的所有边的迹，称为Euler迹（如果此迹是闭迹，也叫Euler环游）， 把含有Euler闭迹（环游）的图称为Euler图。 一个定理 定理：图G含Euler闭迹（环游）的充要条件是G连通且没有奇度顶点，即图G是Euler图的充要条件是G连通且没有奇度顶点。 若一个邮递员在下图所示的街道上投递邮件，问如何投递才使得他走遍每一条街道，再返回邮局，且总路程最短？ 1 1 1 1 1 1 1 1 中国邮路问题 这是由中国数学家管梅谷教授于1960年提出并求解的。 问题分析：据上面定理知，若街道图中没有奇点，则他就可以从邮局出发，走过每条街道一次，且仅一次，最后回到邮局，如此他所走的路程即是最短路程。而对于有奇点的图，必须在某些街道上重复走一次或多次。（假定N1为邮局） 这样，路线可有多种，例： 总权为12 总权为11 可见，按第一条路线，在边 上各重复走了一次，而按第二条路线，在边 上各重复走了一次。 因此，我们想到，可在一个有奇点的图中，增加一些重复边，使得新图不含奇点，且要求重复边的总权最小。 注释：增加重复边使图无奇点的过程称为可行方案。 使总权最小的可行方案称为最小方案 第一步（找初始可行方案）：找到图中的奇点，把奇点两两相连，（因为，在任何图中奇点个数必为偶数）。 第二步（调整可行方案）：调整时遵循两个原则：（a）在最优方案中，图的每一条边上最多有一条重复边；（b）在最优方案中，图的每一个圈上重复边的总权不大于该圈总权的一半。（若把图中某个圈上的重复边去掉，而给原来没有重复边的的边上加上重复边，图中仍没有奇点） 第三步（判断最优方案）：检查条件（a），（b）是否满足，若是，则为最优。 得求解步骤： 例：求解下面问题。 2 5 5 9 6 4 3 4 3 4 4 4 解：奇点有： 连接 且连接 得： 2 5 5 9 6 4 3 4 3 4 4 4 因为圈 的总权为24，但重复边 的总权为14，大于该圈总权的一半，故需要调整，以 上的重复边代替 上的重复边，使重复边总长下降为17， 2 5 5 9 6 4 3 4 3 4 4 4 同理，调整圈 后，得最优方案： 2 5 5 9 6 4 3 4 3 4 4 4 注1：此法称为奇偶点图上作业法，由管梅谷给出。此法困难在于要检查所有圈，问题特复杂时应用它法。 （例如J.Edmonds等人1973年给出的算法）。 注2：此处的最优方案就是一个Euler图了，但如何找到邮递员的满足要求的具体投递路线呢？ 如果一个图G含有Euler闭迹，我们如何找到它呢？ 下面介绍一种寻找Euler图中Euler闭迹的算法－Fleury算法