下面考虑的最大独立数。
由于顶点与其他所有点都相邻，所以的包含顶点的独立集的顶点数为1。设为独立集，则?i?S, 都有i?1 (mod n)?S。因此，。 另外，S?{2i|i?0, 1, ... , n/2?1}为独立集，且。 从而，。
由定理2.8知，g(Gwheel(n),s)?(n?1)?n/2?n/2?1。 2. 当为奇数时
类似于上述为偶数的情形，分别计算团覆盖数和最大独立数。
中没有顶点数大于3的完全子图(团)，而且除掉顶点之后中没有顶点数大于2的完全子图(团)。
因此，Gwheel(n)???(n?1?3)/2?1???(n?1)/2。
n/2?2所以，Gwheel(n)?
?{2i,2i?1}?{n?1,n}为最大数团覆盖，即
i?0 (3.10)
设为独立集，与上述为偶数的情形类似地可以证明
(3.11)
因此，S?{2i|i?0,1,...,(n?1)/2?1}()为最大独立集，即
(3.12)
□
由定理2.8知，(n?1)/2?g(Gwheel(n),s)?(n?1)/2?1。
下面考虑时任意图上加一个顶点并与此点连接所有顶点的情形。为此，先规定如下符号。
设为无向图，用表示顶点集为、边集为的无向图。 定义3.11设为无向图，为无向图的一个猜测策略， 则称为的共轭策略，记为，其中表示维向量。 引理
证明: 对任意，记，则有
F(X)?1n?F(1n?X)?1n?F(X)?1n?X?X
(3.13)
反之，当时有，。
而且显然有当且仅当。因此，。
由引理可以知道，当为最优策略是也为最优策略。 定理3.5 设为无向图，则有
□
g(G,2)?log23?1?g(G?{vn?1},2)?g(G,2)?1
(3.14)
证明：设为最优策略，即。
记M??X?Fix(F)|F(X)?X?，并称为对称固定点集。 不妨设 (否则，以最优策略代替)。 上取如下策略,
?f(x,...,xi?1,xi?1,...,xn):xn?1?0其中hi(x1,...,xi?1,xi?1,...,xn?1)??i1 ,
?fi(x1,...,xi?1,xi?1,...,xn):xn?1?1
则对有，，
从而，Fix(H)?2Fix(F)?M?3Fix(F)/2。
故 g(G??vn?1?,2)?log2Fix(H)?log2Fix(H)?log23?1?g(G,2)?log23?1。□ 例3.1 无向轮图的猜测数为
(3.16)
?0:X?Fix(F)\\M hn?1(x1,x2,...,xn)??1:X?Fix(F)\\M?(3.15)
证明：在文[8]中介绍了无向轮图的猜测数为，并且最优策略为
，其中
(3.17)
此时，按定理3.5证明构造轮图的猜测策略，其为如下
(3.18)
??0 当x?y?x6时?0 当X?(x1,...,x5)?Fix(F)其中f(x1,...,x5)??，fi(x,y,x6)??
1 否 则 ???1 当X?15?X?Fix(F) 表示第 ()顶点所得到的信息。则由推论2.5有，
log25?1?log2Fix(F?)?g(Gwheel(5),2)?g(C5,2)?1?log25?1
(3.19)
□
故。
从例3.1可以猜想无向奇轮图的猜测数等于奇圈的猜测数加1。
定理3.6 无向轮图的猜测数为
g(Gwheel(n),s)?n/2?1 : 当n为偶数g(Gwheel(n),s)?g(Cn,s)?1 : 当n为奇数 (3.20)
证明：只需证明为奇数的情形。
设为奇圈的最优策略，其中为顶点的局部策略。 下面考虑上的策略
fi(xi?1,xi?1,xn)?fi(xi?1,xi?1) , 1?i?n?3
(3.21)
f0(x1,xn?1,xn)?f0(x1,xn?1?xn), fn?2(xn?3,xn?1,xn)?fn?2(xn?3,xn?1?xn) (3.22)
fn?1(x0,xn?2,xn)?fn?1(x0,xn?2)?xn fn(x0,x1,...,xn?1)?fn?1(x0,xn?2)?xn?1
(3.23) (3.24)
则对任意和任意有
fi(xi?1,xi?1,xn?1?a)?fi(xi?1,xi?1)?xi , 1?i?n?3
fn?2(xn?3,a,xn?1?a)?fn?2(xn?3,a?xn?1?a)?fn?2(xn?3,xn?1)?xn?2 fn?1(x0,xn?2,xn?1?a)?fn?1(x0,xn?2)?xn?1?a?xn?1?xn?1?a?a
fn(x0,x1,...,a)?fn?1(x0,xn?2)?a?xn?1?a
(3.25) (3.26) (3.27) (3.28)
因此，x??x0,x1,...,xn?2,a,xn?1?a??Fix(P)，即有
(3.29)
从而，g(Gwheel(n),s)?logsFix(P)?1?logsFix(P)?1?g(Cn?1,s)。 由推论2.5有，。
□
四．结束语
由于确定图的猜测数是NP-难问题，而且猜测数的研究起步比较晚，目前还没得到一种系统有效的计算方法。2006年S.Riis[3]提出猜测数问题之后，T.Wu等人从不同的角度出发研究了图的猜测数问题。他们用图的独立数、团覆盖数和圈填充数[5]给出了猜测数的上下界。此外，用熵[5]、猜测图[7]和编码图[8]等新的概念把猜测数问题转化为另一种问题，并且用此工具算出了一些特殊图的猜测数。但是对很多图，特别对无向奇圈尚未得到确切的猜测数值。
目前，除了奇圈之外对其他简单图的猜测数已经得到了一定的结果，因此我们需要考虑笛卡尔积等图的扩充图的猜测数问题，。对于完全图、二部图、路、有向圈和无向偶圈之间笛卡尔积的猜测数，已经得到了非常好的结论。进一步，我们还可以考虑树、Caylay图、多部图等图和上述图之间笛卡尔积的猜测数问题。
本文中所考虑的轮图为比较简单的扩充图，它是由一个圈添加一个顶点并连接所有顶点得到的图。对于有向轮图和顶点数为奇数的轮图，我们在第三章中给出了确切的猜测数，而对于顶点数为偶数的轮图，证明了其猜测数等于奇圈的猜测数加一。
猜测数方面仍然有非常大的研究空间，本人今后也将不断开拓创新，为寻求一个解决猜测数问题的系统有效的方法做出贡献。
参考文献
[1] R.W. Yeung, Z. Zhang. Distributed Source Coding for Satellite
Communications. IEEE Transactions on Information Theory, vol.45 May 1999.
[2] R. Ahlswede, N. Cai, N. Li, et al. Network information flow. IEEE Transactions on Information Theory, vol.46 July 2000.
[3] S.Riis. Utilizing public informations in network coding. General Theory of information Transfer and Combinatorics, Springer 2006.
[4] S.Riis. Information flows, graphs and their guessing numbers. Electronic Journal of Combinatorics, 14(1) R44 (2006).
[5] S.Riis. Graph entropy, network coding and guessing games. arXiv.orgpdf0711. 2007.
[6] T.Wu, P.Cameron, S.Riis. On the guessing number of shift graphs. Journal of Diserete Algorithms, vol7(2) (2009).
[7] M.Gadouleau, S.Riis. Graph-theoretical constructions for graph entropy and network coding based communications. IEEE Transactions on Information Theory, 1T-57(10) (2011).
[8] D.Christofids, K.Markstrom. The guessing number of undirected graphs. Electronic Journal of combinatorics, 18(2011).
[9] L.Pippenger, N.Valiant. Shifting graphs and their applications. JACM, 23:423–432, 1976.
[10] W.Imrich, S.Klavzar, D.F.Rall. Topics in Graph Theory: Graphs and Their Cartesian Product. A K Peters, 2008, p219.
[11] E.R.Scheinerman, D.H.Ullman. Fractional graph theory. John Wiley & Sons Inc, 1997, p240.
[12] Sun Yun. Network Coding and Graph Entropy:[PhD thesis]. Queen Mary University of London, 2009.
[13] R.Koetter, M.Medard. Beyond routing: An algebraic approach to network