基本概念
图、路、环
一个有向图由
G=(N,A)
<script type="math/tex" id="MathJax-Element-1">\mathbb G=(\mathcal N, \mathcal A)</script>表示，其中
N
<script type="math/tex" id="MathJax-Element-2">\mathcal N</script>表示节点集，
A
<script type="math/tex" id="MathJax-Element-3"> \mathcal A</script>表示边集。边
(i,j)
<script type="math/tex" id="MathJax-Element-4">(i,j)</script>为一有序对，
i
<script type="math/tex" id="MathJax-Element-5">i</script>为出发节点，j<script type="math/tex" id="MathJax-Element-6">j</script>为终止节点。在无向图中
(i,j)与(j,i)
<script type="math/tex" id="MathJax-Element-7">(i,j)与(j,i)</script>一致。
路
P
<script type="math/tex" id="MathJax-Element-8">P</script>是由节点及其对应的边依次相连构成。
环是出发节点和终止节点相同的路。
如果一条路不含重复边和重复节点，就被称做简单路，出发节点和终止节点相同的简单路就被称为简单环。
流和散度
流是用来衡量流过边的某种量，用xi,j表示<script type="math/tex" id="MathJax-Element-9">x_{i,j}表示</script>。并将流的集合
{xi,j|(i,j)∈A}
<script type="math/tex" id="MathJax-Element-10">\{ x_{i,j} | (i,j)\in \mathcal A\}</script>称为流向量(注意流可正可负)。
散度则表示离开节点
i
<script type="math/tex" id="MathJax-Element-11">i</script>的总流量和进入节点i<script type="math/tex" id="MathJax-Element-12">i</script>的总流量之差，其定义如下：
yi=∑{j|(i,j)∈A}xij−∑{j|(j,i)∈A}xji
<script type="math/tex; mode=display" id="MathJax-Element-13">
y_i=\sum_{\{j|(i,j)\in \mathcal A\}}x_{ij}-\sum_{\{j|(j,i)\in \mathcal A\}}x_{ji}
</script>
若
yi>0
<script type="math/tex" id="MathJax-Element-14">y_i \gt 0</script>可以称为源点，
yi<0
<script type="math/tex" id="MathJax-Element-15">y_i \lt 0</script>可以称为汇点，而且可以得到以下等式：
∑i∈Nyi=0
<script type="math/tex; mode=display" id="MathJax-Element-16">
\sum_{i\in\mathcal N }y_i=0
</script>
共轭分解
共轭定义
将一个流向量分解为若干个简单路流之和往往便于处理。由此得到了共轭实现的概念。
路
P
<script type="math/tex" id="MathJax-Element-17">P</script>和流向量x<script type="math/tex" id="MathJax-Element-18">x</script>共轭，即满足以下条件：对于所有
P
<script type="math/tex" id="MathJax-Element-19">P</script>的前向边(i,j)<script type="math/tex" id="MathJax-Element-20">(i,j)</script>有
xij>0
<script type="math/tex" id="MathJax-Element-21">x_{ij}\gt 0</script>,对于所有
P
<script type="math/tex" id="MathJax-Element-22">P</script>的后向边(i,j)<script type="math/tex" id="MathJax-Element-23">(i,j)</script>有
xij<0
<script type="math/tex" id="MathJax-Element-24">x_{ij}\lt 0</script>，并且，或者
P
<script type="math/tex" id="MathJax-Element-25">P</script>是环，或者P<script type="math/tex" id="MathJax-Element-26">P</script>的出发节点和终止节点分别是
x
<script type="math/tex" id="MathJax-Element-27">x</script>的源点和汇点。
共轭实现定理
非零流向量x<script type="math/tex" id="MathJax-Element-28">x</script>可以分解为和
x
<script type="math/tex" id="MathJax-Element-29">x</script>共轭的t<script type="math/tex" id="MathJax-Element-30">t</script>个简单路流向量
x1,x2,...,xt
<script type="math/tex" id="MathJax-Element-31">x^1,x^2,...,x^t</script>，其中
t
<script type="math/tex" id="MathJax-Element-32">t</script>不大于边和节点数目之和A+N<script type="math/tex" id="MathJax-Element-33">A+N</script>。如果
x
<script type="math/tex" id="MathJax-Element-34">x</script>是整数向量，那么x1,x2,...,xt<script type="math/tex" id="MathJax-Element-35">x^1,x^2,...,x^t</script>也可以选为整数向量。如果
x
<script type="math/tex" id="MathJax-Element-36">x</script>是一个循环向量，那么x1,x2,...,xt<script type="math/tex" id="MathJax-Element-37">x^1,x^2,...,x^t</script>也可以选为简单环流，且
t≤A
<script type="math/tex" id="MathJax-Element-38">t\le A</script>。
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可
0
0
已为社区贡献3条内容
所有评论(0)