显然上述策略与一一对应。以下证明猜测策略下猜测成功的概率为当且仅当信息流问题有解。
猜测成功的概率为 Pr(xguess?xreal|ziguess?zireal,?i)?1信息流问jj题有解。
□
推论2.2 [3] 源节点和汇节点数均为的信息流问题可解当且仅当对应的有向图的猜测数满足。
（三）关于猜测数的一些结论
1. 有向图的猜测数
先考虑子图和剖分图的猜测数。 定理2.3设为有向图的子图，则有
，
(2.11)
证明：设和分别为有向图的最优猜测策略与线性猜测策略。则和可视为的猜测策略和线性猜测策略。因此，有
g(H,s)?log2Fix(F)?g(G,s),gl(H,s)?log2Fix(Fl)?gl(G,s) 定理2.4 [6] 设为有向图的子图，则有
□
g(G,s)?g(H,s)?V(G)?V(H) (2.12)
其中表示有向图和的顶点之差。
推论2.5设有向图为由图删除一顶点得到的图，即，则有
g(G?,s)?g(G,s)?g(G?,s)?1
(2.13)
定理2.6 设有向图为由图剖分一点得到的图，则有
(2.14)
证明：设且边，并设为在图的边上添加一个顶点得到的图，即
V(G?)?V(G)??w?, E(G?)?E(G)\\?(u,v)???(u,w),(v,w)?。 设为的最优策略。令，其中和为
则为的猜测策略，并且显然有。
(2.15)
因此，
反之，设为的最优策略。令
则为有向图的一个策略，且 因此，。 故。
例2.3 设为顶点数为的有向圈，则有向圈的猜测数为
(2.17)
□
(2.16)
证明：当时，可以视为的剖分图。由定理2.3有
而为完全图，因此
，
(2.18)
???????????g(Cn,s)?g(Cn?1,s)?...?g(C2,s)?1 ???????????gl(Cn,s)?gl(Cn?1,s)?...?gl(C2,s)?1
(2.19) (2.20)
□
下面考虑有向图猜测数的上下界和线性猜测数的代数表示。 定理2.7 [6] 设为有向图，对有
?(D)?gl(D,s)?g(D,s)??(D)
(2.21)
其中表示有向图中点不相交的圈数的最大值，表示有向图中把变为无圈的最小删除边数。
定理2.8 [6] 设为有向图，则有
gl(D,s)?max(n?rank(I?A))?n?minrank(I?A)
A?ADA?AD(2.22)
其中表示有向图的邻接矩阵，表示阶单位矩阵，表示当时必有。 2. 无向图的猜测数
我们可以把无向图视为双向边有向图、无向图的猜测数定义为对应双向边有向图的猜测数。下面利用图论的一些概念计算猜测数的上下界。
定义2.5 设为无向图，节点集且，则称为图的导出子图。如果其导出子图为完全图，则称此子图为图的一个团，并记为。
定义2.6 若有一团集覆盖了图的所有边，即图中每一条至少属于一个，这时我们称团集中的团的个数为团覆盖数，记为。 定理2.8 [8] 设为无向图，对任意有
n?cp(G)?g(G,s)?n??(G)
(2.23)
其中为图的独立数，为图的团覆盖数。
三．轮图的猜测数
（一）有向轮图的猜测数
在这一节中，我们考虑有向圈上添加一个顶点并与它连接所有顶点，这类图定义为轮图。为了严格定义轮图，先把有向圈用数学符号来表示，其表示如下
，其中，E??(i, i?1 mod n)|0?i?n-1? 定义3.1 设为有向图，其顶点集和边集分别为
?n?1?，E??(i, i?1 mod n)|0?i?n-1?????(i, n) 或 (n, i)??
?i?0?(3.1)
则称有向图为有向轮图，并记为。
记k?{ i|(n,i)?E, (i?1mod n, n)?E, 0?i?n?1}，它表示顶点的入出变化数。
引理 设为有向轮图，则有
(3.2)
证明：由定理2.5和例2.3有
???????????? g(Cn,s)?1?g(Gwheel(n),s)?g(Cn,s)?1?2 定理3.1 有向轮图的猜测数为当且仅当。 证明： (必要性)
反证法：假设，只需证明。 此时，易证为的子图(见图2)。
图2 有向轮图
(3.3) □
的邻接矩阵为
记，则且。
由定理2.3和定理2.,8知，
?????????????????? g(Gwheel(n),s)?g(Gwheel(4),s)?gl(Gwheel(4),s)?4?rank(A)?2
(3.4)
(3.5)
(充分性)
当时，即n点的出度或入度为0。
删除顶点0,则变成有向无圈图。由推论2.5知，。 因此，。
当时，删除顶点，其中为满足且的点。 则变成有向无圈图，因此，。 故。
□
推论3.2有向轮图的猜测数为
证明：由定理3.2和引理显然成立。 （二）无向轮图的猜测数
类似于有向轮图，我们可以考虑无向轮图的猜测数。 定义3.2 设为如下定义顶点集和边集的无向图，
，E??(i, i?1 mod n)|0?i?n-1???n?1?????(i, n)??() (3.7)
i?0?此时，称为无向轮图，记为。 定理3.3 有向轮图的猜测数为
g(Gwheel(n),s)?n/2?1 ： 当n为偶数(n?1)/2?g(Gwheel(n),s)?(n?1)/2?1 ： 当n为奇数
证明：分别当为奇数和偶数时考虑轮图的猜测数。 1. 当为偶数时
首先，中没有顶点数大于3的完全子图(团)。
除掉顶点之后，中没有顶点数大于2的完全子图(团)。 因此，的团覆盖数满足
cp(Gwheel(n))?(n?1?3)/2?1?n/2
n/2?2而
?{2i,2i?1}?{n?2,n?1,n}为的-团覆盖。
i?0从而，。
(3.6)
□(3.8)
(3.9)