图论与网络流问题的LINGO求解技巧
LINGO11教程
LINGO 是用来求解线性和非线性优化问题的简易工具。LINGO 内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO 高效的求解器可快速求解并分析结果。 §1 LINGO 快速入门 当你在windows 下开始运行LINGO 系统时，会得到类似下面的一个窗口： 外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。在主窗口内的标题为LINGO Model – LINGO1的窗口是LINGO 的默认模型窗口，建立的模型都都要在该窗口内编码实现。下面举两个例子。 例1.1 如何在LINGO 中求解如下的LP 问题： ,6002100 350. .32min 21211 212 1≥≤+≥≥++x x x x x x x t s x x 在模型窗口中输入如下代码： min =2*x1+3*x2; x1+x2>=350; x1>=100; 2*x1+x2<=600; 然后点击工具条上的按钮 即可。 例1.2 使用LINGO 软件计算6个发点8个收点的最小费用运输问题。产销单位运价如
model: !6发点8收点运输问题; sets: warehouses/wh1..wh6/: capacity; vendors/v1..v8/: demand; links(warehouses,vendors): cost, volume; endsets !目标函数; min=@sum(links: cost*volume); !需求约束; @for(vendors(J): @sum(warehouses(I): volume(I,J))=demand(J)); !产量约束; @for(warehouses(I): @sum(vendors(J): volume(I,J))<=capacity(I)); !这里是数据; data: capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3; enddata end 然后点击工具条上的按钮即可。 为了能够使用LINGO的强大功能，接着第二节的学习吧。 §2 LINGO中的集 对实际问题建模的时候，总会遇到一群或多群相联系的对象，比如工厂、消费者群体、交通工具和雇工等等。LINGO允许把这些相联系的对象聚合成集（sets）。一旦把对象聚合成集，就可以利用集来最大限度的发挥LINGO建模语言的优势。 现在我们将深入介绍如何创建集，并用数据初始化集的属性。学完本节后，你对基于建模技术的集如何引入模型会有一个基本的理解。 2.1 为什么使用集 集是LINGO建模语言的基础，是程序设计最强有力的基本构件。借助于集，能够用一个
lingo教程
lingo入门教程之一--- 初识lingo lingo对于一些线性或者非线性的规划，优化问题非常有效 首先介绍一下，在lingo中运行程序时出现的页面（在工具栏点击类似靶子一样的图标便可运行） Solver status:求解器(求解程序)状态框 Model Class:当前模型的类型:LP，QP，ILP，IQP，PILP，PIQP，NLP，INLP，PINLP（以I开头表示IP，以PI开头表示PIP） State:当前解的状态: "Global Optimum", "LocalOptimum", "Feasible", "Infeasible“(不可行), "Unbounded“(无界), "Interrupted“(中断), "Undetermined“(未确定) Object:解的目标函数值
Infeasibility:当前约束不满足的总量(不是不满足的约束的个数):实数（即使该值=0，当前解也可能不可行，因为这个量中没有考虑用上下界命令形式给出的约束） Iteration:目前为止的迭代次数 Extend solverstatus:扩展的求解器(求解程序)状态框 Solver type:使用的特殊求解程序: Bestobj :目前为止找到的可行解的最佳目标函数值 Objbound:目标函数值的界 Steps:特殊求解程序当前运行步数： Active:有效步数 Variables（变量数量）： 变量总数（Total）、 非线性变量数（Nonlinear）、 整数变量数（Integer）。
Constraints（约束数量）： 约束总数（Total）、 非线性约束个数(Nonlinear)。 Nonzeros（非零系数数量）： 总数（Total）、 非线性项系数个数(Nonlinear)。 GeneratorMemory Used (K) (内存使用量) ElapsedRuntime (hh:mm:ss)（求解花费的时间） 运行之后页面介绍（这里的运行界面并不是与上面的运行过程中出现界面一致，即并非来自于同一个程序运行出现）
lingo软件使用教程
lingo软件使用教程 一般来说，一个优化模型将由以下三部分组成： 1. 目标函数（Objective Function）：要达到的目标。 2. 决策变量（Decision variables）：每组决策变量的值代表一种方案。在优化模型中需要确定决策变量的最优值，优化的目标就是找到决策变量的最优值使得目标函数取得最优。 3. 约束条件（Constraints）：对于决策变量的一些约束，它限定决策变量可以取的值。 在写数学模型时，一般第一行是目标函数，接下来是约束条件，再接着是一些非负限制等。在模型窗口输入如下代码: Max = 2*x1+3*x2; X1+2*x2<=8; 4*x1<16; 4*x2<12; 注意：1.每一个lingo表达式最后要跟一个分号; 2.多数电脑中没有符号，lingo中<=代替；为了方便可以用<代替小于等于，用>代替大于等于。 3.我们可以添加一些注释，增加程序的可读性。注释以一个！（叹号必须在英文状态下输入，它会自动变为绿色）开始，以；（分号）结束。 4．Lingo中不区分变量名的大小写。变量名必须以字母（A-Z）开头，后面的字符可以是字母、数字、下划线。变量名不能超过32个字符。 Lingo程序的一些规则： 1. 在Lingo中最开始都是“MAX=”或者“MIN=”开始表示求目标函数的最大或者最小值。 2. 变量和它前面的系数之间要用“*”连接，中间可以有空格。 3. 变量名不区分大小写，但必须以字母开始，不超过32个字符。 4. 数学表达式结束时要用分号“；”表示结束。表达式可以写在多行上，但是表达式中间不能用分号。 5. 在电脑系统中一般没有“小于等于”符号，在Lingo采用“<=”来表示“小于等于”，用“>=”表示“大于等于”。小于等于也可以用更简单的“<”表示，大于等于用“>”表示。 集合段： 在我们已经得到的程序里有一些量没有定义，如WAREHOUSES( I)，DEMAND( J)， LINKS( I, J)。这些量将在Lingo中的集合段定义。 集合段以SETS:表示开始，以ENDSETS表示结束。 如果一个集合的元素都已经定义过，就可以用一些循环函数（如@for）. 注：1. 集合的属性相当于以集合的元素为下标的数组。Lingo中没有数组的概念，只有定义在集合上的属性的概念。 2 集合的定义语法： set_name[/set_member/:][attribute_list]; 集合的名称在左边，右边是这个集合上的属性，他们之间用冒号“：”分割开，最后由分号表示结束。如果在同一个集合上有多个属性时，不同的属性之间用逗号“，”隔开，如本例的cost和volume属性。如果要特别列出集合的元素时，在集合的名称后把元素写在两条斜线之间，如本例中的仓库可以写为 WAREHOUSES/WH1, WH2, WH3, WH4, WH5, WH6/: CAPACITY;
图论基础知识
图论基本知识 对于网络的研究，最早是从数学家开始的，其基本的理论就是图 论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献[1-5]。 本章只给出非平凡的定理的证明，过于简单直观的定理的证明将 留给读者。个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。 图的基本概念 图G 是指两个集合(V ，E)，其中集合E 是集合V×V 的一个子集。 集合V 称为图的顶点集，往往被用来代表实际系统中的个体，集合E 被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。若{,}x y E ，就称图G 中有一条从x 到y 的弧（有向边），记为x→
y ，其中顶点x 叫做弧的起点，顶点y 叫做弧的终点。根据定义，从任意顶点x 到y 至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。如果再假设图G 中不含自己到自己的弧，我们就称图G 为简单图，或者更精确地叫做有向简单图。以后如果没有特殊的说明，所有出现的图都是简单图。记G 中顶点数为()||G V ν=，边数为()||G E ε=，分别叫做图G 的阶和规模，显然有()()(()1)G G G ενν≤-。图2.1a 给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。 图2.1：网络拓扑结构示意图。图a 是10阶有向图，顶点集为 {1,2,3,4,5,6,7,8,9,10}，边集为{1→2,1→3,1→4,2→5,2→6,2→7,3→6,4→7,4→8,6→9,7→9,8→10}；图b 是6阶无向图，顶点集为{1,2,3,4,5,6}，边集为{13,14,15,23,24,26,36,56}。 从定义中可以看到，从任意顶点x 到y 不能连接两条或以上 边，本文所讨论的图，均符合上述要求，既均为不含多重边的图。如
图论-网络流
网络流网络流
1532Drainage Ditches Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9885 Accepted Submission(s): 4695 Problem Description Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch. Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network. Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle. Input The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch. Output For each case, output a single integer, the maximum rate at which water may emptied from the pond.
lingo9.0详细使用教程
LINGO 使用教程 LINGO 是用来求解线性和非线性优化问题的简易工具。LINGO 内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO 高效的求解器可快速求解并分析结果。 §1 LINGO 快速入门 当你在windows 下开始运行LINGO 系统时，会得到类似下面的一个窗口： 外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。在主窗口内的标题为LINGO Model – LINGO1的窗口是LINGO 的默认模型窗口，建立的模型都都要在该窗口内编码实现。下面举两个例子。 例1.1 如何在LINGO 中求解如下的LP 问题： ,6002100 350. .32min 21211 2121≥≤+≥≥++x x x x x x x t s x x 在模型窗口中输入如下代码： min =2*x1+3*x2; x1+x2>=350; x1>=100; 2*x1+x2<=600; 然后点击工具条上的按钮 即可。 例1.2 使用LINGO 软件计算6个发点8 个收点的最小费用运输问题。产销单位运价如
model : !6发点8收点运输问题; sets : warehouses/wh1..wh6/: capacity; vendors/v1..v8/: demand; links(warehouses,vendors): cost, volume; endsets !目标函数; min =@sum (links: cost*volume); !需求约束; @for (vendors(J): @sum (warehouses(I): volume(I,J))=demand(J)); !产量约束; @for (warehouses(I): @sum (vendors(J): volume(I,J))<=capacity(I)); !这里是数据; data : capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3; enddata end 然后点击工具条上的按钮 即可。 Global optimal solution found. Objective value: 664.0000 Total solver iterations: 20
lingo教程
LINGO是Linear Interactive and General Optimizer的缩写，中文名称为“交互式的线性和通用优化求解器”，是由美国LINDO系统公司（Lindo System Inc.）开发的一套专门用于求解最优化问题的软件包，用于求解线性规划和二次规划问题，LINGO可以求解非线性规划问题，也可以用于一些线性和非线性方程（组）的求解等。此外，LINGO还允许优化模型中的决策变量为整数（即整数规划），其执行速度很快，是求解优化模型的最佳选择。 1软件介绍 其特色在于内置建模语言，提供十几个内部函数，可以允许决策变量是整数（即整数规划，包括0-1整数规划），方便灵活，而且执行速度非常快。能方便与EXCEL，数据库等其他软件交换数据。最新版本LINGO14.0已经发布。 2操作步骤 一般地，使用LINGO求解运筹学问题可以分为以下两个步骤来完成：1）根据实际问题，建立数学模型，即使用数学建模的方法建立优化模型； 2）根据优化模型，利用LINGO来求解模型。主要是根据LINGO软件，把数学模型转译成计算机语言，借助于计算机来求解。 例题：在线性规划中的应用maxZ=5X1+3X2+6X3, s.t.X1+2X2+X3≤18 2X1+X2+3X3=16 X1+X2+X3=10
X1,X2≥0,X3为自由变量 应用LINGO来求解该模型，只需要在lingo窗口中输入以下信息即可： max=5*x1+3*x2+6*x3; x1+2*x2+x3<=18; 2*x1+x2+3*x3=16; x1+x2+x3=10; @free(x3); 然后按运行按钮，得到模型最优解，具体如下：Objectivevalue:46.00000 VariableValueReducedCost x114.000000.000000 x20.0000001.000000 x3-4.0000000.000000 由此可知，当x1=14,x2=0,x3=-4时，模型得到最优值，且最优值为46。 说明：在利用LINGO求解线性规划时，如自变量都为非负的话，在LINGO中输入的信息和模型基本相同；如自变量为自由变量，可以使用函数@free来把系统默认的非负变量定义自由变量，如实例一中的x3。 3软件详述 LINGO全称是LinearINteractiveandGeneralOptimizer的缩写---
Lingo教程
LINGO教程 LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。 §1 LINGO快速入门 ●安装：实验室的所有电脑都已经事先安装好了Lingo 8（或者9， 10， 11）。 如果要在自己的电脑上安装这个软件，建议从网上下载一个破解版的，按照提示一步一步地安装完毕。 ●简单例子：当你在windows系统下开始运行LINGO时，会得到类似于下面的 一个窗口： 外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。在主窗口内的标题为LINGO Model –LINGO1的窗口是LINGO的默认模型窗口，建立的模型都要在该窗口内编码实现。下面举两个例子。 例 1某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示。
该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排生产计划使该厂获利最多？ 我们用下面的数学模型来描述这个问题。 设x_1、x_2分别表示在计划期内产品I、II的产量。因为设备的有效台时是8，这是一个限制产量的条件，所以在确定产品I、II的产量时，要考虑不超过设备的有效台时数，即可用不等式表示为 x_1 + 2x_2 <=8 同理，因原材料A、B的限量，可以得到以下不等式 4x_1 <=16 4x_2 <=12 该工厂的目标是在不超过所有资源限量的条件下，如何确定产量x_1、x_2以得到最大的利润。若用z表示利润，这时z=2x_1+3x_2.综合上述，该计划问题可用数学模型表示为： 目标函数 max z=2x_1+3x_2 约束条件 x_1 + 2x_2 <=8 4x_1 <=16 4x_2 <=12 x_1、x_2 >=0 一般来说，一个优化模型将由以下三部分组成： 1.目标函数（Objective Function）：要达到的目标。 2.决策变量（Decision variables）：每组决策变量的值代表一种方案。在优化模 型中需要确定决策变量的最优值，优化的目标就是找到决策变量的最优值使得目标函数取得最优。 3.约束条件（Constraints）：对于决策变量的一些约束，它限定决策变量可以取 的值。 在写数学模型时，一般第一行是目标函数，接下来是约束条件，再接着是一些非负限制等。 在模型窗口输入如下代码: Max = 2*x1+3*x2; ！This is a linear program. X1+2*x2<=8;
lingo教程
Lingo是一套由美国Lindo系统公司开发的专门用于求解最优化问题的软件包，包括用于表达优化模型的强大语言，用于构建和编辑问题的全功能环境，以及能够高效解决大多数优化模型的快速内置解算器。 该软件提供强大的语言和快速的求解引擎来阐述和求解最佳化模型。他具有功能强、计算效果好等优点，不过其最大特色在于他可以允许优化模型中的决策变量是整数(即整数规划)，且执行速度非常快，是使建立和求解线性、非线性和整数最佳化模型更快更简单更有效率的综合工具。 Lingo可应用的范围包含生产线规划、运输、财务金融、投资分配、资本预算、混合排程、库存管理、资源配置等，在国外运筹学类的教科书中也被广泛用做教学软件。 LINGO优点：（1）简单的模型表示，（2）方便的数据输入和输出选择，（3）强大的求解引擎，（4）交互式模型或创建Turn-key应用程序，（5）广泛的文件和HELP功能。 LINGO是用来求解线性和非线性优化问题的简易工具。LINGO 内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。
一般来说LINGO多用于解决大规模数学规划。 用时要注意以下几点： 1.每条语句后必须使用分号“；”结束。问题模型必须由MODEL 命令开始，END结束。 2.用MODEL命令来作为输入问题模型的开始，格式为MODEL：statement （语句）。 3.目标函数必须由“min =”或“max =”开头。 建模时需要注意的几个基本问题 1.尽量使用实数优化，减少整数约束和整数变量。 2.尽量使用光滑优化，减少非光滑约束的个数。如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等。 3.尽量使用线性模型，减少非线性约束和非线性变量的个数。 4.合理设定变量上下界，尽可能给出变量初始值。 5.模型中使用的参数数量级要适当，否则会给警告信息，选择适当单位改变相对尺度。
网络流基本概念
对于交通网、管道网，都有物质流动的问题，在交通网中，有人、车辆的流动；在管道网中有流体（水、油等）的流动等等。这种网络中的物质流动称为网络流。 下面介绍与网络流有关的一些基本概念。 （1）流量：表示某时间内通过弧（j i v v ）的物质数量，记为ij f ，他是网络流问题中待求解的变量。网络中的总流量用v(f)表示。 （2）容量：弧的最大允许流通量，一般用ij c 表示。 （3）可行流：在实际的网络中，网络流应满足下面两个条件： 1) 容量限制条件：对于没一个弧{j i v v }∈A ，A 为弧集来说，ij c f ≤≤ij 0。即通过每条弧 的流量不能超过该弧的容量。 2) 平衡条件：对于始点s v ，流入始点的流量等于网络中的总流量，即 ()f v f f A v v js A v v sj s j j s =-∑∑∈∈)()( 对于终点t v ，流出终点的流量等于网络中的总流量，即 ()f v f f A v v jt A v v tj t j j t -=-∑∑∈∈)()( 对于仍以中间的顶点()t s i i ,≠，流进某中间顶点的流量等于流出盖顶点的流量。即 0)()(=-∑∑∈∈A v v ji A v v ij i j j i f f 在网络分析中，满足上面两个条件的流动，称为可行流。 （4）零弧与非零弧：满足 的弧称为零弧。由于 ，所以弧的流量不能减小；满足 的弧称为非零弧。弧的流量可以被减小，但要满足 0。 （5）饱和弧和非饱和弧：网络中流量等于容量（即ij f =ij c ）的弧称为饱和弧。流量小于容量（即ij f
图论与强连通网络流-练习题
一般图论与连通性-练习题 Problem A. 老乡 问题描述 “老乡见老乡两眼泪汪汪，问一问老乡你过得怎么样？心情好不好啊做工忙不忙？其实我和你一样夜夜梦故乡。 老乡见老乡两眼泪汪汪，问一问老乡你又要去何方？吃过多少苦啊受过几回伤？其实我和你一样总想闯一闯。 他乡的话你你你会不会讲，他乡的歌你你你爱不爱唱？习不习惯飘泊的生活，想不想念自己的家乡？他乡的话你你你会不会讲，他乡的歌你你你爱不爱唱？有没有钱寄给你爹娘，想没想过何时回故乡？……” 《老乡》唱出了很多20世纪九十年代打工创业者的心声，歌曲一经发行，便传遍大江南北。 其实，老乡的范围可大可小。比如在省里看到同一县的人，在市里看到同一区的人，在全国看到同一省的人，都可以算做老乡。在农村或小县城的日常口语中，老乡一般也能用作关系亲密的兄弟之间的一种称呼。 现在给定称作老乡的若干人员对，请您做出判断给定任何两人是否是老乡。 输入 有若干组测试数据。每组测试数据的第一行是2个整数n，q (0 ≤ n ≤ 10000，q<10) ，即是老乡的人数对。接下来有n行，每行是一个用空格隔开的数对A 和B，表示A和B是老乡，(A ≠ B, 1 ≤ A, B ≤ 100000) 。接下来有q行，每行有两个整数x和y。 两组数据之间有一个空行。 输出 对每组测试数据，先输出“Case #”，换行，其中#是测试数据序号（从1开始）。接着对q组整数x和y，一行输出x与y是否是老乡的结论：如是，则输出“YES”，否则输出“NO”。 输入样例 4 2 1 2 3 4
5 6 1 6 1 4 1 5 4 2 1 2 3 4 5 6 7 8 1 4 1 5 输出样例Case 1 NO YES Case 2 NO NO Case 3 NO YES
图论总结(超强大)
1.图论Graph Theory 1.1.定义与术语Definition and Glossary 1.1.1.图与网络Graph and Network 1.1. 2.图的术语Glossary of Graph 1.1.3.路径与回路Path and Cycle 1.1.4.连通性Connectivity 1.1.5.图论中特殊的集合Sets in graph 1.1.6.匹配Matching 1.1.7.树Tree 1.1.8.组合优化Combinatorial optimization 1.2.图的表示Expressions of graph 1.2.1.邻接矩阵Adjacency matrix 1.2.2.关联矩阵Incidence matrix 1.2.3.邻接表Adjacency list 1.2.4.弧表Arc list 1.2.5.星形表示Star 1.3.图的遍历Traveling in graph 1.3.1.深度优先搜索Depth first search (DFS) 1.3.1.1.概念 1.3.1. 2.求无向连通图中的桥Finding bridges in undirected graph 1.3. 2.广度优先搜索Breadth first search (BFS) 1.4.拓扑排序Topological sort 1.5.路径与回路Paths and circuits 1.5.1.欧拉路径或回路Eulerian path 1.5.1.1.无向图 1.5.1. 2.有向图 1.5.1.3.混合图 1.5.1.4.无权图Unweighted 1.5.1.5.有权图Weighed —中国邮路问题The Chinese post problem 1.5. 2.Hamiltonian Cycle 哈氏路径与回路 1.5. 2.1.无权图Unweighted 1.5. 2.2.有权图Weighed —旅行商问题The travelling salesman problem 1.6.网络优化Network optimization 1.6.1.最小生成树Minimum spanning trees 1.6.1.1.基本算法Basic algorithms 1.6.1.1.1.Prim 1.6.1.1. 2.Kruskal 1.6.1.1.3.Sollin（Boruvka） 1.6.1. 2.扩展模型Extended models 1.6.1. 2.1.度限制生成树Minimum degree-bounded spanning trees 1.6.1. 2.2.k小生成树The k minimum spanning tree problem(k-MST) 1.6. 2.最短路Shortest paths 1.6. 2.1.单源最短路Single-source shortest paths 1.6. 2.1.1.基本算法Basic algorithms
图论里面的重要概念(一)
1、支配集： 设D集合是无向图G的一个顶点子集，对于G中的任意顶点u，要么在D里，要么与D集合的一个顶点相邻，那么称我们集合D的G的一个支配集。如果去掉D中任何一个顶点，D不在是支配集，则支配集是极小支配集。G中所有支配集中顶点个数最小的支配集称为最小支配集，即是极小支配集。最小支配集的顶点个数为支配数。 2、独立集： 设I集合无向图G的一个顶点子集，对于集合I中任意两点都不相邻，则我们称集合I为G 的一个独立集。如果在I中加入一个非I集合的顶点后，I集合不在是独立集，则称集合I 为极大独立集。G中所有独立集中顶点个数最多的独立集称为最大独立集，即是极大独立集。最大独立集的顶点个数为独立数。 3、覆盖集： 设K集合是无向图G的一个顶点子集，对于G中的任意一条边e，至少有一个端点属于K，那么我们称集合K是G的一个覆盖集。如果去掉K中的任意一个顶点，K不在是覆盖集，则称集合K是极小覆盖集。在G中所有覆盖集中顶点个数最少的覆盖集称为最小覆盖集。即是极大覆盖集。最小覆盖集的顶点个数为覆盖数。 4、网络流： a、网络与流： 网络D=(V,A,C） 设D是一个简单有向图，V是顶点集，A是边集，C弧容量集。 网络流F F(i,j)=集合A上的一个函数，为弧(vi,vj)的流量。 b、可行流与最大流： 可行流 （1）容量限制 对于每条弧(vi,vj)属于A，则0<=|F(i,j)|<=c(i,j)。 （2）平衡条件 对于V里的每个顶点i!=s,t;(源点和汇点) 都有流入量=流出量 对顶点s的流出量-s的流入量=-1*（顶点t的流出量-t的流入量） 最大流 求最大流问题即是求顶点s的流出量-流入量的最大值或者求顶点t的流出量-流入量的最小值。 c、可改进路P 如果|F(i,j)|=C(i,j)，称该弧为饱和弧 如果|F(i,j)|