【網路流最佳化(二)】圖的等價轉化與網路流最佳化問題的等價轉化

本節內容對應教材 Network Flows Theory， Algorithm and Application，作者：Ahuja R。K。， Magnant T。L。， Orlin J。B。， 1993。第二章 Path， Trees and Cycles

1 圖的簡介

1。1 圖的表示

1 有向圖（directed graph）和無向圖（undirected graph）。圖

，

表示節點的集合，

表示邊的集合。

有向圖：

$N=\{1,2,3,4,5,6\}, A=\{(1,2),(1,3),(2,3),(2,4),(2,5),(3,5),(5,4),(4,5),(5,6)\}$

無向圖：

$N=\{1,2,3,4,5,6\}, A=\{(1,2),(1,3),(2,3),(2,4),(2,5),(3,5),(5,4),(4,5),(5,6)\}$

圖

可以由 Node-Arc Incidence Matrix 和 Node-Node Adjacency Matrix 來表示，關於這兩個矩陣的定義詳情見：教材Page 32-33，我們這裡就不再贅述了。

1。2 圖的相關概念和性質描述

相鄰節點，度（Degree），環（Cycle），子圖（Subgraph），路徑（Path），有向路徑（Directed Path），二部圖（Bipartite Graph），生成樹。

無向圖的連線性（Connectivity）：從節點

到節點

至少存在一條路徑，稱之為節點

和節點

是連線的。若一個無向圖中任意兩兩節點之間都是連線的，則稱該無向圖為連線的。

有向圖的連線性（Weakly Connectivity）：若將該有向圖所有的有向邊替換為無向邊所構成的無向圖是連線的。

有向圖的強連線性（Strong Connectivity）：若從任意一個節點

可以到達任意一個節點

，則稱該有向圖是強連線的。

Cut：設圖的節點集合為

，cut 將圖中的節點分為兩部分

和

並且滿足

$S\cap S$

，

$S\cup S$

。如下圖所示紅色粗線將圖中節點分為了兩部分。其中

$S=\{1,2,3\}$

，

，圖中虛線的邊是橫跨

和

的邊。

s-t Cut：對於兩個不同的節點

和

，若

$s\in S$

，

$t\in S$

則該cut 是 s-t cut。

1。3 圖之間的轉化

無向圖轉有向圖

無向圖轉有向圖比較容易，我們可以將無向圖的任意一條不帶方向的邊都看做是兩條有方向的邊即可，如下圖所示：

2 網路流最佳化問題的轉化

考慮如下網路流最佳化問題：

$\underset{x}{\min}\sum_{\left( i,j \right) \in A}{c_{ij}x_{ij}}$

（1）

$\sum_{\left\{ j:\left( i,j \right) \in A \right\}}{x_{ij}}-\sum_{\left\{ j:\left( j,i \right) \in A \right\}}{x_{ji}}=b\left( i \right) ,\ \ \forall i\in N$

（2）

$l_{ij}\le x_{ij}\le u_{ij},\ \ \forall \left( i,j \right) \in A$

（3）

2。1 消除邊Capacity下限約束

我們要去掉約束（3）中的下限約束

$l_{ij}\le x_{ij}$

代數推導：

考慮約束（3），若

$l_{ij}\ne0$

可以考慮採用如下變數代換來消掉（3）約束中的 Lower bound 約束。對於給定的

可以令

$x_{ij}^{$

（1。1）

考慮約束（2）中含有

$x_{ij}$

的項有：

$\sum_{\left\{ i:\left( i,n \right) \in A \right\}}{x_{in}}-\sum_{\left\{ m:\left( m,i \right) \in A \right\}}{x_{mi}}=b\left( i \right)$

（1。2）

$\sum_{\left\{ n:\left( n,j \right) \in A \right\}}{x_{nj}}-\sum_{\left\{ m:\left( i,m \right) \in A \right\}}{x_{im}}=b\left( j \right)$

（1。3）

這樣就實現了將下限約束消去的目的。式（1。2）中第一項中含有

$x_{ij}$

，而式（1。3）中第二項含有

$x_{ij}$

。我們將式（1。1）分別帶入到式（1。2）和（1。3）中，即用

$x_{ij}^{$

替換掉式（1。2）（1。3）中

$x_{ij}$

可得：

$\sum_{\left\{ i:\left( i,n \right) \in A/\left( i,j \right) \right\}}{x_{in}}+x_{ij}^{$

（1。4）

$\sum_{\left\{ n:\left( n,j \right) \in A \right\}}{x_{nj}}-\sum_{\left\{ m:\left( i,m \right) \in A/\left( i,j \right) \right\}}{x_{im}}+x^{$

（1。5）

幾何解釋：

上面是一個簡單的代數推導的結果，從幾何上直觀來解釋，如下圖所示

如上圖所示，事實上剛才那個代換

$x_{ij}=x_{ij}^{$

，可以看做先讓從節點

到節點

之間有一個固定的流量即

$l_{ij}$

，如上圖所示我們只需要在原來節點

上扣除

$l_{ij}$

，在節點

上增加

$l_{ij}$

即可表示出這個固定的流量

$l_{ij}$

。這一點從式（1。4）（1。5）中也可以觀察出來。這樣我們從代數和幾何兩方面都對這個轉化有了基本的理解。

2。2 消除邊Capacity上限制約束

我們要去掉約束（3）中的上限約束

$x_{ij}\le u_{ij}$

，其實消除上限約束和前面消除下限約束的思路大同小異。

代數推導：

我們可以新增一個冗餘變數

$s_{ij}\geq0$

，這樣我們可以將上限約束等價變換為：

$x_{ij}+s_{ij}=u_{ij}$

（2。1）

對於給定的

，我們將約束（2）中含有

$x_{ij}$

這項的等式寫出來：

$\sum_{\left\{ i:\left( i,n \right) \in A \right\}}{x_{in}}-\sum_{\left\{ m:\left( m,i \right) \in A \right\}}{x_{mi}}=b\left( i \right)$

（2。2）

$\sum_{\left\{ n:\left( n,j \right) \in A \right\}}{x_{nj}}-\sum_{\left\{ m:\left( i,m \right) \in A \right\}}{x_{im}}=b\left( j \right)$

（2。3）

式（3。2）中第一項中含有

$x_{ij}$

，而式（2。3）中第二項含有

$x_{ij}$

。我們將式（2。1）帶入到式（3。3）中，即用

$u_{ij}-s_{ij}$

替換掉式（2。3）中

$x_{ij}$

可得：

$\sum_{\left\{ n:\left( n,j \right) \in A \right\}}{x_{nj}}-\sum_{\left\{ m:\left( i,m \right) \in A/\left( i,j \right) \right\}}{x_{im}}-s_{ij}=b\left( j \right) +u_{ij}$