圈算法

㈠ 图论算法及其MATLAB实现的图书目录

第1章 图论的基础知识1
1.1图论的起源1
1.2着名的图论学者——欧拉1
1.3图2
1.4特殊图类3
1.5有向图4
1.6图的矩阵表示5
1.6.1邻接矩阵5
1.6.2关联矩阵5
1.7图论的基本性质和定理6
1.8计算有向图的可达矩阵的算法及其MATLAB实现6
1.9关联矩阵和邻接矩阵的相互转换算法及其MATLAB实现7
习题一11
第2章 最短路12
2.1路12
2.2最短路问题13
2.3求连通图最短距离矩阵的算法及其MATLAB实现14
2.4求两点间最短路的Dijkstra算法及其MATLAB实现15
2.4.1 Dijkstra算法16
2.4.2 Dijkstra算法的MATLAB实现16
2.5求两点间最短路的改进的Dijkstra算法及其MATLAB实现18
2.5.1 Dijkstra矩阵算法Ⅰ18
2.5.2 Dijkstra矩阵算法Ⅱ18
2.6 求两点间最短路的WarshallFloyd算法及其MATLAB实现21
2.6.1 Floyd算法的基本思想22
2.6.2 Floyd算法的基本步骤22
2.6.3 WarshallFloyd算法的MATLAB实现22
2.7求任意两点间最短路的算法及其MATLAB实现25
2.8求从一固定点到其他所有点最短路的算法及其MATLAB实现27
2.9求必须通过指定两个点的最短路的算法及其MATLAB实现29
2.10求图的两顶点间最短路与次短路的算法及其MATLAB实现32
2.11求最大可靠路的算法及其MATLAB实现34
2.12求最大期望容量路的算法及其MATLAB实现36
习题二38
第3章 连通图40
3.1判断图的连通性算法及其MATLAB实现40
3.2连通图的中心和加权中心的算法及其MATLAB实现42
3.3连通无向图一般中心的算法及其MATLAB实现44
习题三46
第4章 树48
4.1树及其性质48
4.2割点、割边、割集50
4.3二元树与Huffman树51
4.3.1有序二元树51
4.3.2 Huffman树51
4.4求Huffman树及其MATLAB实现52
4.5广度优先搜索算法及其MATLAB实现55
4.6深度优先搜索算法及其MATLAB实现57
4.7求割点算法及其MATLAB实现61
4.8生成树及其个数65
4.9求无向图的生成树算法及其MATLAB实现67
4.10求有向图的生成树算法及其MATLAB实现69
4.11求有向连通图的外向树与内向树数目的算法及其MATLAB实现71
4.12最小生成树问题73
4.13求最小生成树的Kruskal算法及其MATLAB实现74
4.13.1 Kruskal算法的基本思想74
4.13.2 Kruskal算法的MATLAB实现74
4.14求最小生成树的Prim算法及其MATLAB实现76
4.14.1 Prim算法的基本思想76
4.14.2 Prim算法的MATLAB实现77
习题四79
第5章Euler图和Hamilton图81
5.1 Euler图81
5.2“一笔画”问题及其理论81
5.3中国邮递员问题82
5.4 Fleury算法及其MATLAB实现82
5.4.1 Fleury算法的步骤82
5.4.2 Fleury算法的MATLAB实现82
5.5 Hamilton图87
5.6旅行售货员问题88
5.7改良圈算法及其MATLAB实现89
习题五92
第6章 匹配问题及其算法93
6.1问题起源——婚配问题93
6.2二分图的有关知识93
6.3匹配、完美匹配、最大匹配93
6.4匹配的基本定理94
6.5应用案例——BernolliEuler错放信笺问题95
6.6寻求图的一个较大基数匹配算法及其MATLAB实现95
6.7人员分配问题97
6.8匈牙利算法及其MATLAB实现97
6.8.1匈牙利算法基本步骤97
6.8.2匈牙利算法的MATLAB实现98
6.8.3案例及其MATLAB实现100
6.9最优分配问题101
6.10 KuhnMunkres算法及其MATLAB实现101
6.10.1 KuhnMunkres算法的基本思想101
6.10.2利用可行顶点标记求最佳匹配的KuhnMunkras算法步骤102
6.10.3 KuhnMunkres算法的MATLAB实现102
6.10.4简单实验105
习题六107
第7章 网络流的算法108
7.1网络、流和割108
7.1.1网络和流108
7.1.2割109
7.2网络的最大流问题110
7.3最大流最小割定理110
7.4 FordFulkerson标号算法及其MATLAB实现111
7.4.1 FordFulkerson标号算法的基本步骤111
7.4.2 FordFulkerson 标号算法的MATLAB实现112
7.4.3案例及其MATLAB实现113
7.5 Dinic算法及其MATLAB实现114
7.5.1 Dinic算法的基本思想114
7.5.2 Dinic算法的MATLAB实现115
7.5.3案例

㈡ 数学建模 旅行商路线规划问题。第一问用改良圈算法已经解决，请问第二问该用什么算法（每段高速和普通公

每段高速和普通公路里程数不同
导致总费用=油费+路费不同
这个题目有点意思
要不要考虑高速和普通公路的单位油耗不同

㈢ 什么是改良圈算法

首先求一个 Hamilton 圈C ，然后适当修改C 以得到具有较小权
的另一个 Hamilton 圈。修改的方法叫做改良圈算法。

㈣ 求助：图的遍历并且路径最短的算法（vb6.0）

我汗。。。最短哈密尔顿路。。这个是np问题，没有什么好的算法。不过有几个近似算法，如“改良圈算法”，如果要精确的那就只能回溯搜索了。。。不过会很慢。

㈤ 求教有负环的最小费用最大流

我现在也没有编出来。正如你所说，这个程序需要用消圈或者单纯形。它们很难编，也非常耗时，比赛的时候写这样的程序容易吃亏。并且，这类题目基本上不会出现。
需要程序和解释的话，你可以参考王晓东写的一本书《计算机算法设计与分析》，里面非常详尽！

㈥ 用破圈法求最小生成树

感觉上你那里的“算法基本思想”实现难度很大，因为图的连通性不好维护
找圈的话，随便找个节点为根DFS整个图，然后在这样的DFS生成树中，每条非树边都对应了一个圈，每次找一条非树边，删去所在圈中最长边生成一个新树，直到不存在非树边为止，剩下的就是最小生成树了
具体实现的时候，先求出一个DFS生成树，然后递归处理每棵子树

假设要处理的子树根节点为u，对该子树破圈法的粗略伪代码如下：

void 破圈法(u)
{
for ( v是u的每个子节点 ) 破圈法(v);
for ( e是连接u与其后继的每条非树边 )
{
v=e的另一个端点;
e'=u到v之间的最长树边;
if (w[e]>=w[e']) 删除边e;//w[e]表示e的权
else
{
//用w表示原先e'的在树中较深的端点,p[v]表示v的亲节点
删除边e';
if (v!=w)
{
将v列入u的子节点列表;
将p[v]、p[p[v]]、...、w这条路径反向，并将p[v]列入v的子节点列表;
}
}
}
}

上述过程不加优化的时间复杂度为O(VE)，效率非常差
貌似其中找最长边和将v的若干祖先节点路径反向的两步优化空间比较大，或许可将整个时间复杂度下降到O(ElgV)，研究中

㈦ 生产与作业管理--破圈法的概念、步骤。

1、生产战略：是企业根据所选定的目标市场和产品特点来构造其生产系统时所遵循指导思想，以及在这种指导思想下的一系列决策规划、内容和程序。2、生产管理的任务：运用组织、计划、控制的职能，把投入生产过程的各种要素组织起来，形成有机整体，按最经记得方式，生产出满足社会需要的廉价、优质的产品。3、生产管理的内容：1.生产准备和组织 2.生产计划 3.生产控制4、生产管理的原则：1.讲求经济效益 2.坚持以销定产 3实行科学管理4.组织均衡生产 5.实施可持续发展战略5、生产按工艺特性分类：1.加工装配型 2.流程型6、生产按组织生产的特点分类：1.备货型 2.订货型：订货组装型、订货制造型、订货工程型7、备货型生产(MTS)：是指在没有接到用户订单时，按已有的标准产品或产品系列进行生产，生产目的是为了完成产品库存。8、订货型生产(MTO)：是指按用户的订单进行生产。9、生产按专业化程度分类：1.大量生产 2.单件生产 3.成批生产 4.多品种小批量生产10、多品种小批量生产组织工作的特征：1.生产品种多样性 2.生产过程复杂性 3.生产能力的适应性4.环境条件的多变性 5.生产计划的变动性 6.生产管理的动态性11、生产过程的组成：1.生产技术准备过程 2.基本生产过程 3.辅助生产过程 4.生产服务过程12、工序：是指一个工人或一组工人在同一工作上对同一劳动对象进行加工的生产环节。13、合理组织生产过程的基本要求：1.生产过程的连续性 2.生产过程的比例性3.生产过程的节奏性 4.生产过程的柔性14、生产时间计算：*P25--2815、文明生产：是指在生产现场管理中，要按照现代工业生产的客观要求，为生产现场保持良好的生产环境和生产秩序v16、“5S”活动的内容：1.整理 2.整顿 3.清扫 4.清洁 5.素养17、安全生产：是指在保持领导者生命安全和健康的前提下进行生产活动。二工作研究1、工作研究：是指在既定的工作条件下，运用系统分析的方法，研究资源的更合理利用，排除作业中不合理、不经济和混乱的因素，寻求一种更佳、更经济的工作方法，以提高系统的生产率，降低系统的运营成本。2、工作研究的内容：1.方法研究：过程分析、动作分析 2.时间研究：定额制订、工作抽样3、工作研究的步骤：1.发掘问题，选择研究项目 2.确定目标3.记录 4.分析研究记录的事实，寻求新的方法5.评价新的工作方法 6.实施新的方法7.追检与再评价4、过程分析：是指对现行作业方法予以系统的记录，这种记录采用的是一种以简明符号为基础绘制的程序图。5、过程分析基本符号：1.加工： 2.搬运： 3.储存：4.延误： 5.检验：6、过程分析的内容：1.产品工序分析 2.零件加工分析 3.平面流程分析4.搬运分析 5. 人—机联合分析7、动作分析：是把某项作业的动作分解为最小的分析单位，对作业进行定性、定量分析，省去不必要和不合理的动作，制定出最合理的动作和动作的顺序，使作业达到准化的一种科学分析方法和技术。8、动作的基本类型：1.必要动作 2.辅助动作 3.延迟动作 9、工作研究中动作经济合理的要求：1.动作应同时进行 2.动作应对称 3.动作应自如4.动作应有节奏 5.动作应考虑惯性6.能用脚完成的动作，应避免用手10、工作环境：是指人、机共处的特定条件，如温度、湿度、噪声等物理环境；有害气体等化学环境和人际关系等社会环境。11、工作环境的三类因素：1.气候状况 2.照明和色彩状况 3.噪声与振动状况三 生产计划和控制1、生产计划系统：是一个包括需要预测、中期生产计划、生产作业计划、材料计划、能力计划、设备计划、新产品开发计划等相关计划和职能，并以生产控制信息迅速反馈连接构成的复杂系统。2、生产计划的层次：1.长期生产计划。属于战略计划，任务是进行产品决策、生产能力决策以及确立何种竞争优势的决策。2.中期生产计划。属于B战术性计划，任务是对企业在计划年度内的生产任务作出统筹安排，规定企业的品种、质量、数量和进度。3.短期生产计划。任务是直接依据用户的订单，合理的安排生产活动的每个细节。3、年生产计划的主要指标：1.品种 2.产量 3.质量 4.产值 5.出产期4、生产计划的产值指标分为：1.商品产值 2.总产值 3.净产值5、生产计划编制的原则：以销定产的原则，即以产品销路来决定生产什么样的产品。6、生产计划编制的步骤：1.调查、掌握编制生产计划的依据。 2.统筹安排，初步提出生产计划指标。3.综合平衡，确B定生产计划指标。 7、滚动式计划方法的优点：1.计划是动态型的，计划的应变性和严肃性得到保证。2.提高了计划的连续性。8、生产计划主要考虑的成本项目：1.正常生产成本 2.加班成本 3.外协成本 4.库存成本

㈧ hamilton圈算法是什么意思

哈密顿图（哈密尔顿图）（英语：Hamiltonian path，或Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径。

从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。
要满足两个条件：
⒈封闭的环
⒉是一个连通图，且图中任意两点可达
经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。
经过图中所有顶点一次且仅一次的回路称为哈密顿回路。
具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。
平凡图是哈密顿图。