论文概览

本文第一部分介绍研究背景与部分前置知识，第二部分介绍本文主要用的方法：收缩方法；第三部分证明结论：任意简单5-连通的线图的流指数都小于3；第四部分和第五部分扩展Hakimi定理并用以刻画流指数小于3，且为6-边连通的图。

第一部分 介绍

本文研究的对象皆为有限图，且不允许有自环，但允许有重边。

给定整数$k\ge 2d\ge 0$, 图$G$的圆环$\frac{k}{d}$-流$(D,f)$满足：$f:E(G)\rightarrow \{\pm{d},\pm{(d+1)},\dots,\pm{(k-d)}\}$, 使得对于任意点$v\in V(G)$, 都有$\partial f(v)=\sum_{e\ leaving\ v}f(e)-\sum_{e\ entering\ v}f(e)=0$成立。特别地，当$d=1$时，退化成为处处非零$k$-流。

已有学者研究得出，圆环流具有单调性，即任意图若存在$t$-圆环流，则其同时存在$s$-圆环流，其中$s\ge t \ge2$.

定义流指数$\phi(G)=inf\{r|r$是有理数，且图$G$存在$r$-圆环流$\}$. 已有的结论是：对于任意有限无桥图，这样的流指数总是存在的。

Tutte最先发现了边连通性与流存在的关系，提出了著名的5-流猜想、3-流猜想。在此流指数的定义下，Tutte的5-流猜想可以被重述为：任意无桥图$G$都满足：$\phi(G)\leq5$; Seymour证明了：任意无桥图$G$都满足：$\phi(G)\leq6$; Tutte的3-流猜想：任意4-边连通图$G$都满足：$\phi(G)\leq3$; 而Jaeger证明了：任意4-边连通图$G$都满足：$\phi(G)\leq4$; Lovász, Thomassen, Wu 和 Zhang4人证明了：对于任意6-边连通图$G$, 都有$\phi(G)\leq3$成立。

Jaeger拓展了Tutte的流猜想，提出：任意$4p$-边连通图$\phi(G)\leq \frac{1}{p}+2$. 这一猜想的弱版本：任意$6p$-边连通图$\phi(G)\leq \frac{1}{p}+2$, 由Thomassen提出，且被Lovász等人证明。然而最近对于$p\ge3$的情况，Jaeger的圆环流猜想有无穷多个反例被构造出来。而$p=1,2$时的情况与Tutte的流猜想联系更为紧密，因此也更加重要，但遗憾的是，这两种情况仍未被解决。

Conj 1.1 对于任意6-边连通图$G$, $\phi(G)<3$.

众所周知，完全图$\phi(K_6)=3$, 并且5-边连通的平面图族的流指数也恰好为3. 因此在这一猜想中，边连通性的条件不能再被放宽。目前已经证明：对于任意8-边连通图，其流指数小于3.

Thm 1.2 对于任意8-边连通图，其流指数小于3.

这篇文章运用收缩方法，研究了流指数小于3的问题，并对于特定图类给出猜想1.1的证明。这一方法也与图的哈密尔顿性密切相关，具体内容将在第二部分展开。

Thm 1.3 令$G$是一个6-边连通图：

（1）若$G$至多有12个奇度点，则其流指数小于3.

（2）若$G$的独立数最多为2，则其流指数小于3.

需要注意的是：独立数至多为2的图与不含三角形（triangle-free）的图一样多，原因是独立数至多为2的图实际上是triangle-free图的补图。

称简单图为弦图，若该图每一个长度至少为4的圈都含有弦，换句话说就是弦图的每一个导出圈（induced cycle）的长度至多为3. 弦图在图的算法领域是一类很重要的图，因为大量NP难的问题在弦图上都能够找到有效的算法。

Thm 1.4 若$G$是一个简单5-连通弦图，且其不同构于$K_6$, 则其流指数小于3.

第二部分 收缩方法与定向

独立数: $\alpha(G)$; 最小度: $\delta(G)$; 邻点集: $N(v)$.

给定两个非空点集$A,B \subset V(G)$, 令$[A,B]_G=\{ab \in E(G)|a\in A, b\in B\}$. 当$AB$互补时，简记为 $\partial_G A$.

给定图$G$, 映射$\beta:\ V(G)\rightarrow \mathbb{Z}_3$, 若$\sum_{x\in V(G)}\beta(x)=0\pmod{3}$, 则称$\beta$为边界函数。记边界函数的集合为$Z(G,\mathbb{Z}_3)$.

称定向$D$为$\beta$-定向，若对于任意点$v\in V(G)$, 都有$d^+(v)-d^-(v) \equiv \beta(v)\pmod{3}$. 当$\beta\equiv 0$时，退化为图$G$的模3-定向。

Prop 2.1 若一个图的流指数小于等于3等价于该图存在模3-定向。

事实上，流指数严格小于3与强连通定向也存在类似的关系。

Thm 2.2 若一个图的流指数严格小于3等价于该图存在强连通模3-定向。

Jaeger等人于1992年提出了一个在研究处处非零3-流与模3-定向中很有力的一个工具——群连通性。称图$G$是$\mathbb{Z}_3$-连通的，若对于任意边界函数$\beta$, 都存在相应的$\beta$-定向。

Def 2.3 称图$G$为强连通$\mathbb{Z}_3$-可收缩的，若对于任意边界函数$\beta$, 都存在强连通$\beta$-定向。 记这类图为$S_3$.

为了记号方便，记强连通$\beta$-定向为$\beta-SCO$. 强连通$\mathbb{Z}_3$-可收缩图为$S_3$-图。

给定边子集$B\subset E(G)$, 图的收缩指：将$B$中的每条边的两个端点“粘”成一个点，然后再去掉由此形成的环，这样得到的新图记作$G/B$. 从定义可以验证，在图的收缩下，群连通性可以保持。

Prop 2.4 下列几条成立：

（1）$K_1\in S_3$;

（2）$G\in S_3$, 且$e\in E(G)$, 则$G/e \in S_3$;

（3）若子图$H$与$G/H$都是$S_3$的，则$G$也是$S_3$的。

Def 2.5 称图$G$是弱可收缩的，若对于任意真子图$H$, 以及任意$H$上的边界$\beta$, 任意$G/H$上的定向$\beta'-SCO$可被扩展成$G$上的$\beta-SCO$定向。类似地，记这类图为$W_3$.

Prop 2.6 令$H$是$G$的一个真$W_3$子图，则有以下成立：

（1）$\phi(G) <3$当且仅当$\phi(G/H)<3$;

（2）$G\in S_3$当且仅当$G/H \in S_3$. Prop 2.7 图$H\in W_3$, 当且仅方$H+xy \in S_3$, $x,y$是不同的点。

证明： 若$H\in W_3$, 令$G=H+xy$, 则此时$G/H=K_1$, 由Def 2.5, $k_1$上的任意$\beta'-SCO$都可扩展为$G$上的$\beta-SCO$. 根据定义图$G\in S_3$.

反过来，假设对于任意两个不同的点$x,y$, 都有$G/H\in S_3$, 令$G$是$H$的真子图。给定$\beta\in Z(G,\mathbb{Z}_3)$, 根据$G/H$上的$\beta'$-定向$D'$复制得到$G-E(H)$上的定向$D_1$（对于$E(G[V(H)]-E(H)$的边则随意定向）, 可断言：对于任意不同点$x,y$, 在$D_1$中存在$x$到$y$的有向路。

因为图$H$是图$G$的真子图，所以存在$G-E(H)$的路（注意：非有向！）$P$连接$V(H)$中的两个点$u,v$. 如果$P$中的每一条边都含于$D_1$中的某个有向圈内，则存在$u,v$之间的有向路，从而命题成立。否则，存在边$e_0\in P$, 使得这条边不被$D_1$中的任何一个有向圈所包含。

注意到$D'=D'(G/H)$是强连通定向，所以存在$D'$中的有向圈$C$包含$e_0$. 但$E(C)$不是$D_1$中的有向圈，所以一定存在连接$u,v$的有向路。（实际上这句话的意思是说，$e_0$在$D_1$下未被包含在有向圈中，而在$D'$下我们找到了一个有向圈$C$, 而$D'$中的所有有向边在$D_1$中都有，那么可以推断，在$D_1$中，$e_0$与有向路$E(C)-e_0$有同样的终点和起点，它们所下未被包含在有向圈中，）

证毕。