数模竞赛-图论模型
数模竞赛-图论模型
NetworkX
基本操作：
1 | import networkx |
示例：
1 | import networkx,pylab |
加边加点：
1 | import networkx |
画图：
1 | import networkx,pylab |
画赋权图：
1 | import networkx,pylab,numpy |
最短路
Dijkstra
单源最短路，从$1$到$8$。
1 | import networkx |
Floyd-Warshall
全源最短路。
1 | import networkx,numpy |
路径输出：
1 | import numpy,networkx,pylab |
最小值地址：
1 | import numpy,networkx |
最短路问题的01整数规划
略。
最小生成树
代码：
1 | import pylab,numpy,networkx |
着色问题
对图$G=(V,E)$的顶点进行着色所需最少颜色数目用$\chi(G)$表示，称为图$G$的色数。若$G=(V,E),\Delta=\max{d(v)\mid \in V}$为图$G$顶点的最大度数，则$\chi(G)\leqslant\Delta+1$。
设顶点个数为$n$，顶点最大度为$\Delta$，引入0-1变量$x_{ik}$当$v_i$着第$k$种颜色时为$1$，否则为$0$。设颜色总数为$y$，建立整数线性规划模型：
$$
\displaylines{
\min y,\\
\mathrm{s.t.}\begin{cases}
\displaystyle\sum_{k=1}^{\Delta+1}x_{ik}=1,i=1,2,\cdots,n,\\
x_{ik}+x_{jk}\leqslant1,(v_i,v_j)\in E,k=1,2,\cdots,\Delta+1,\\
\displaystyle y\geqslant\sum_{k=1}^{\Delta+1}kx_{ik},i=1,2,\cdots,n,\\
x_{ik}=0或1,i=1,2,\cdots,n,k=1,2,\cdots,\Delta+1
\end{cases}
}
$$
代码：
1 | import cvxpy,numpy |
网络流
最大流
给定一个有向图$D=(V,A)$，$A$为弧集，$V$指定一点称为发点或源$v_s$，该点只有发出的弧。指定一点称为收点或汇$v_t$，该点只有进入的弧，其余点称为中间点。对于每一条弧$(v_i,v_j)\in A$对应有一个$c(v_i,v_j)\geqslant0$称为弧的容量。把这样有向图$D$称为一个网络记作$D=(V,A,C)$，其中$C={c_{ij}}$。网络上的流指定义在弧集合$A$上的一个函数$f={f_{ij}}={f(v_i,v_j)}$，称$f_{ij}$为弧$(v_i,v_j)$上的流量。
满足下列条件的流$f$称为可行流：满足容量限制条件$\forall(v_i,v_j)\in A,0\leqslant f_{ij}\leqslant c_{ij}$。满足平衡条件有$\displaystyle\sum_{j:(v_i,v_j)\in A}f_{ij}-\sum_{k:(v_k,v_i)\in A}f_{ki}=0,\sum_{j:(v_s,v_j)\in A}f_{sj}=v,\sum_{k:(v_k,v_t)\in A}f_{kt}=v$，其中$v$为这个可行流的流量，即发点的净输出量。可行流总是存在的，如零流。
（下面这段Markdown崩了凑合着看吧。
若给定一个可行流$f={f_{ij}}$，把网络中使$f_{ij}=c_{ij}$的弧称为饱和弧，使$f_{ij}<f_{ij}$的弧称为非饱和弧。$f_{ij}=0$的弧称为零流弧，$f_{ij}>0$的弧称为非零流弧。若$\mu$是网络中联结发点$v_s$和收点$v_t$的一条路，定义路的方向是从$v_s$到$v_t$，则路上的弧被分为两类：一类是弧的方向与路的方向一致称为前向弧，前向弧全体记为$\mu^+$。另一类弧与路的方向相反称为后向弧，后向弧全体记为$\mu^-$。
最大流问题写作线性规划模型为：
$$
\displaylines{
\max v,\\
\mathrm{s.t.}\begin{cases}
\displaystyle\sum_{j:\left(v_s,v_j\right)\in A}f_{sj}=v,\\
\displaystyle\sum_{j:\left(v_i,v_j\right)\in A}f_{ij}-\sum_{k:\left(v_k,v_i\right)\in A}f_{ki}=0,i\neq s,t,\\
\displaystyle\sum_{k:\left(v_k,v_t\right)\in A}f_{kt}=v,\\
0\leqslant f_{ij}\leqslant c_{ij},\forall\left(v_i,v_j\right)\in A
\end{cases}
}
$$
设$f$是一个可行流，$\mu$时从$v_s$到$v_t$的一条路，若$\mu$满足前向弧是非饱和弧，后向弧时非零流弧，则$\mu$称为关于可行流$f$的一条增广路。
Ford-Fulkerson求最大流标号法略。
代码：
1 | import numpy,networkx,pylab |
例题：人才招聘
1 | import numpy,networkx |
最小费用流
设$b_{ij}$为弧$\left(v_i,v_j\right)$上的单位费用，最小费用流问题可写作线性规划问题：
$$
\displaylines{
\min\sum_{\left(v_i,v_j\right)\in A}b_{ij}f_{ij},\\
\mathrm{s.t.}\begin{cases}
\displaystyle\sum_{j:\left(v_s,v_j\right)\in A}f_{sj}=v,\\
\displaystyle\sum_{j:\left(v_i,v_j\right)\in A}f_{ij}-\sum_{k:\left(v_k,v_i\right)\in A}f_{ki}=0,i\neq s,t,\\
\displaystyle\sum_{k:\left(v_k,v_t\right)\in A}f_{kt}=v,\\
0\leqslant f_{ij}\leqslant c_{ij},\forall\left(v_i,v_j\right)\in A
\end{cases}
}
$$
代码：
1 | import numpy,networkx |
关键路径
设$t(i,j)$为作业$(i,j)$所需工时，$t_E(i)$为与事件$j$相邻的各紧前事件的最早时间，$t_E(n)$也为总最早完工期，有：
$$
\displaylines{
\begin{cases}
t_E(1)=0,\\
\displaystyle t_E(j)=\max_j\left{t_E(i)+t(i,j)\right}
\end{cases}
}
$$
设$t_L(i)$表示以事件$i$为始点的作业最迟必须开始时间，或以事件$i$为终点的各作业最迟必须完成时间，需要从后往前递推，有：
$$
\displaylines{
\begin{cases}
t_L(n)=t_E(n),\\
\displaystyle t_L(i)=\min_j\left{t_L(j)-t(i,j)\right}
\end{cases}
}
$$