【LSP】 最大流问题+最小花费问题+python(ortool
http://cdn.u1.huluxia.com/g4/M01/6D/4A/rBAAdl93-_mAWIHGAACt4WdlvYs261.jpg
基本概念
图
定义： 图G(V,E)是指一个二元组(V(G),E(G))，其中:
V(G)={v1,v2,…, vn}是非空有限集，称为顶点集，
2. E(G)是V(G)中的元素对(vi,vj)组成的集合称为边集。
举例：http://cdn.u1.huluxia.com/g4/M01/6D/4A/rBAAdl93-_uANtHlAADSOpHBnis115.jpg
V(G)={v1,v2,v3,v4}
E(G)= {e1,e2,e3,e4,e5,e6}
若图G的边是有方向的，称G是有向图，有向图的边称为有向边或弧。
与同一条边关联的两个端点称为相邻的顶点
与同一个顶点关联的两条边称为相邻的边
端点重合为一点的边称为环
若一对顶点之间有两条以上的边联结，则这些边称为重边．
既没有环也没有重边的图，称为简单图．
若图G的每一条边e 都赋以一个实数w(e)，称w(e)为边e的权， G连同边上的权称为赋权图 ,
图G的中顶点的个数， 称为图G的阶
图中与某个顶点相关联的边的数目，称为该顶点的度。
完全图：若无向图的任意两个顶点之间都存在着一条边，称此图为完全图。
邻接矩阵
以下均假设图为简单图，没有重边和环
图G的邻接矩阵是表示顶点之间相邻关系的矩阵http://cdn.u1.huluxia.com/g4/M01/6D/4A/rBAAdl93-_uAfTLPAAE0FkZwHXI222.png
举个例子：
http://cdn.u1.huluxia.com/g4/M01/6D/4A/rBAAdl93-_yAUGV6AACATcwIBMc166.jpg
http://cdn.u1.huluxia.com/g4/M01/6D/4B/rBAAdl93-_2AXI5jAABeeQ8cQPI321.jpg
最大流问题
设G(V,E)为有向图，若在每条边e上定义一个非负权c， 则称图G为一个网络，称c为边e的容量函数，记为c(e)。
若在有向图G(V,E)中有两个不同的顶点vs与vt ，
若顶点vs只有出度没有入度，称vs为图G的源，
若顶点vt只有入度没有出度， 称vt为G的汇，
若顶点v 既不是源也不是汇， 称为v中间顶点。http://cdn.u1.huluxia.com/g4/M01/6D/4B/rBAAdl93-_6AJha6AAEs-PR0skA727.jpg
如图，就是从v1到v9怎么流动，在受每一个有向边的流动最大限制下，才是最大流。大学考试的内容一般都是用手算的，这里我们还是用python来解决最大流问题。
python解决最大流问题http://cdn.u1.huluxia.com/g4/M01/6D/4B/rBAAdl93-_6AX_NqAACWk_oaPsk737.jpg
http://cdn.u1.huluxia.com/g4/M01/6D/4B/rBAAdl93-_-AFvIMAAMNVCSfaGA964.jpg
页:
[1]