(最新版)南开大学数学科学学院毕业论文(4)

下面考虑的最大独立数。

由于顶点与其他所有点都相邻，所以的包含顶点的独立集的顶点数为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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库(最新版)南开大学数学科学学院毕业论文(4)在线全文阅读。