第八章图论方法§1 图论中图的概念在人们从事的各种活动中，为了反映事物之间的关系，常在纸上用点和线画出各种各样的示意图。
例如，为了反映某地区的铁路交通、公路网分布情况，画出铁路、公路交通图。
在这些图中以点表示城镇，用点与点之间的连线表示城镇之间的铁路或公路的沟通情况。
诸如此类的图还有电缆线分布图、供水道及下水道分布图、航空线图等等。
再如，在一场有5支球队参加的球类比赛中，比赛情况也可以用图表示出来，如图6-1，我们用点代表各个球队，某两个队比赛过一次，就在两个点之间画一条箭线。
从图中可以看出A队与其他各队都比赛过，只有一场败给C 队。
而B队和E队各比赛过两场，成绩都是一胜一负，等等。
图6-1从上述例子中可以看出，图的最基本要素是：点、以及点与点之间的一些连线。
通常用点表示我们所要研究的对象（如城市、运动队、状态等等），用线表示研究对象间的某种特定关系（如两个城市之间有铁路，两个运动队之间已经比赛过等）。
因此可以说，图是反映对象之间关系的一种工具。
如果两个对象之间有某种特定关系，那么就用一条线连接这两个点。
必须指出：上述图中点的相对位置如何，点与点之间连线的长短曲直，对于反映研究对象之间的关系并不很重要，因此，图论中的图与几何图、工程图本质上是不同的。
另外在许多情况下，我们要研究的“关系”只用一条线反映还是不够完全。
比如说比赛，我们关心的如果不只是两个队是否比赛过，还要了解比赛的胜负情况，我们可以用一条箭线（有向线）来表示，如果A队胜了B队，就表示为A→B。
如图6-1所示，从图中可以看出A队三胜一负，D队三场全负等。
类似的情况在生产和生活中也是常见的，例如交通运输中的“单行线”、部门之间的领导与被领导关系、一项生产活动中各工序之间的先后次序关系等等。
图论中把不带箭头的连线叫做边，把带箭头的连线叫做弧。
如果一个图是由点和边所构成的，则称之为无向图，记作G=（V，E），其中V表示图G中的所有点组成的点集合，E表示图G中所有边组成的边集合。
一些经典的对偶问题解决原问题的例子【原创实用版】目录1.引言2.对偶问题的定义和性质3.经典对偶问题解决原问题的例子3.1 最大流问题与最小割问题3.2 线性规划问题与对偶线性规划问题3.3 旅行商问题与旅行商问题对偶问题4.对偶问题的应用价值5.结论正文一、引言在数学和计算机科学中，对偶问题是一种重要的问题类型。
对偶问题与原问题相对应，它们之间存在着紧密的联系。
通过解决对偶问题，有时可以更方便地解决原问题。
本文将介绍一些经典的对偶问题解决原问题的例子，以展示对偶问题在实际应用中的价值。
二、对偶问题的定义和性质对偶问题是指与原问题相对应的问题，它们的解相互关联。
给定一个原问题，可以通过构造其对偶问题来求解原问题。
对偶问题具有以下性质：1.原问题和对偶问题的解集合相等。
2.原问题和对偶问题的最优解值相等。
三、经典对偶问题解决原问题的例子1.最大流问题与最小割问题最大流问题是图论中的一个经典问题，要求在给定有向图中找到从源节点到汇节点的最大流量。
最小割问题则是在给定有向图中找到源节点到汇节点的最小割集。
这两个问题具有对偶关系，可以通过解决最小割问题求解最大流问题。
2.线性规划问题与对偶线性规划问题线性规划问题是优化理论中的一个基本问题，要求在给定线性约束条件下，找到使得线性目标函数最大化或最小化的变量值。
对偶线性规划问题是线性规划问题的对偶问题，要求在给定线性约束条件下，找到使得对偶目标函数最大化或最小化的变量值。
线性规划问题和对偶线性规划问题具有对偶关系，可以通过解决对偶线性规划问题求解线性规划问题。
3.旅行商问题与旅行商问题对偶问题旅行商问题（Traveling Salesman Problem，TSP）是组合优化中的一个经典问题，要求在给定城市之间距离的情况下，找到访问所有城市并返回出发点的最短路径。
旅行商问题对偶问题是 TSP 的对偶问题，要求在给定城市之间距离的情况下，找到一个哈密顿回路，使得沿着该回路的总距离最小。
数学建模中的图论方法一、引言我们知道，数学建模竞赛中有问题A和问题B。
一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。
由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。
因此很多人有这样的感觉，A题入手快，而B题不好下手。
另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。
但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。
命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。
这样增加了建立数学模型的难度。
但是这也并不是说无法求解。
一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。
图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。
应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。
图论方法已经成为数学模型中的重要方法。
许多难题由于归结为图论问题被巧妙地解决。
而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如：AMCM90B－扫雪问题；AMCM91B－寻找最优Steiner树；AMCM92B－紧急修复系统的研制(最小生成树)AMCM94B－计算机传输数据的最小时间(边染色问题)CMCM93B－足球队排名(特征向量法)CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性)CMCM98B－灾情巡视路线(最优回路)等等。
这里面都直接或是间接用到图论方面的知识。
要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。
