云南大学报告问题、模型与算法.ppt

内容摘要 基础知识 最小支撑树问题 最短路问题 匹配问题 欧拉问题 中国邮递员问题 一些可计算性为NP-完备的组合最优化问题及数学模型 一、基础知识 1.1 图与支撑子图 定义1.1 所谓一个（无向）图是指给了 一个集合V，以及V中的不同元素的无序对构 成的集合E，并记图为G =(V，E)。称V中的 元素为图G的顶点，称E中的元素为图G的边 。连接两顶点u和v的边记作uv（或者vu）， 也称边uv（或者vu）与顶点u,v相关联，同时 称两顶点u和v是相邻的。 定义1.2 所谓一个有向图是指给了一个 集合V，以及V中的不同元素的有序对构成的 集合A，并记有向图为D =(V，A)。称V中的 元素为有向图D的顶点，称A中的元素为有向 图D的弧。以顶点u为起点和以顶点v为终点 的弧记作（u，v），也称与弧（u，v）与顶 点u, v相关联。 定义1.3给定两个图G=(V, E)和H=(V*, E*) ，称H是G的一个支撑（生成）子图，如果 V*=V和E* E。 1.2 图的连通性 定义1.4 （路）给定图G=(V, E)，一个点 、边交错的序列P=（v0 ,e1 ,v1 , e2 , v2 ，e3 , v3 , …,vk-1, ek,vk)，如果满足ei=vi-1vi, i=1,2,…,k,则 称P为一条连结v0和vk的路，简记为P=v0 v1v2v3 …vk-1vk；称v0 ，vk分别称为路P的起点和终点，其余称为中间点。 定义1.5（回路）设P为一条连结v0和vk的 路，如果v0 = vk，称该路P为回路；如果v0≠ vk，称该路P为(严格的)路。 定义1.6（圈）如果路P除起点和终点相 同，中间所含的点均不相同，称这样的回路P 为圈。 定义1.7（连通图）如果图G中任意两点 之间均至少有一条路相连，称G为连通图； 否则称图为不连通图。 问题1.1：给定图G，问G是连通的吗？ 二、最小支撑树问题 2.1 树 定义2.1 一个无圈的连通图称为树。 树具有如下一些性质： 性质2.1 设图G=（V，E）是一棵树，n≥2， 则图G中至少有两个悬挂点。 性质2.2 图G=（V，E）是一棵树的充要条件 是G不含圈，并且有且仅有n-1条边。 性质2.3 图G=（V，E）是一棵树的充要条件 是G是连通图，并且有且仅有n-1条边。 性质2.4 图G是一棵树的充分必要条件是任意 两个顶点之间有且仅有一条路。 2.2 支撑树 定义2.2 设图T=(V,E)是图G=(V,E)的一 个支撑子图，如果图T=(V,E‘)是一棵树，那 么称T是G的一棵支撑树。 2.3 最小支撑树问题 定义2.3 设有图G =（V，E；w），如果 对于G中的每一条边vivj，相应地有一个数wij ，那么称这样的图G为赋权图，wij称为边vivj 的权。 这里所指的权，是具有广义的数量值。 根据实际研究问题的不同，可以具有不同的 含义。例如长度，费用、流量等等。 定义2.4 如果图T =（V，E）是赋权图G 的一棵支撑树，那么E‘中所有边的权重之和 称为支撑树T 的权重，记作w(T)。 如果图G 中支撑树T* 的权重w(T*)是在G 的所有支撑树T中的权重达到最小者，即 w(T*) = min{w(T) | T为G的支撑树}，那么称 T*是G 的一棵最小支撑树。 类似可定义最大支撑树问题。 问题2.1：给定图G，如何求G的一棵最 小支撑树？ 常用的有破圈算法和避圈算法： Algorithm 破圈算法 Input: 赋权图 G =（V，E；w） Output: G的最小支撑树T Begin ① 在图中寻找一个圈。若不存在圈，则已经得到最小支撑树或说明该图不连通，后者不存在支撑树（当然没有最小支撑树）； ② 若存在圈，去掉该圈中权数最大的边； ③ 反复重复①、②两步，直到找到最小支撑树或说明该图不连通（故没有最小支撑树）。 End 避圈算法： 从图中依次寻找权重较小的边，寻找过 程中，节点不得重复，即不得构成圈。注意 在找较小权重边时不考虑已选过的边和可能 造成圈的边。如此反复进行，直到得到最小 支撑树或者说明该图不连通，后者不存在支 撑树（当然没有最小支撑树）。 2.4 顶点加细限制性的最小支撑树问题 定义 2.5 给定图G =（V，E），在G的 某些边