关于几类非完美图的猜测数

摘要

网络编码由于其可以降低网络的复杂度，增加最大吞吐量的优点，在通信领域中成为近年来研究的热点。而猜测数这一游戏中引申出的概念恰到好处地描述了网络编码的可解性问题，进而成为研究网络编码的重要工具。无向图的猜测数问题早有讨论，其中，完美图的猜测数问题已经解决，然而对于非完美图，其进展就较为缓慢。本文的工作就是在原有的基础上利用熵函数与猜测图来考虑非完美图的猜测数问题。
　　本文主要介绍了几类特殊的非完美图猜测数的估计，分别为图的笛卡尔积的猜测数、有一个公共顶点的图的猜测数，轮图的猜测数。其中，前两种图的猜测数问题借助于信息论中熵函数的性质来处理，而轮图的猜测数问题主要利用了猜测图与不动点集的一些性质。传统的估计方法主要通过计算图的独立数与团覆盖数，而通过这种方式得到的估计上下界只能为整数，而熵函数巧妙地规避了这一问题，利用熵函数中Shannon不等式等性质，可以证明猜测数的上界可以为小数，且当满足特殊条件时，我们可以证明上界可以达到。对于轮图的猜测数，我们构造了一组多维向量，可以证明这组向量在轮图的猜测图中是一组独立集，于是利用猜测图与猜测数的关系，我们可以得到轮图的猜测数。
　　本文的意义在于给出了几类特殊的非完美图猜测数的求法，其中熵函数对于许多含有奇圈的图是同样有效的。由强完美图定理可知，非完美图中含有一类重要的图，这些图的诱导子图中含有奇圈，故熵函数能够解决一些非完美图的猜测数问题，而这些图并不需要很好的性质。此外，本文建立了猜测数与猜测图的联系，并利用构造法得到轮图的猜测数，这无疑给猜测数的研究开辟了一条新的道路。

目录

声明

摘要

第一章 引言

第一节 历史回顾

第二节 本文工作

第二章 完美图的猜测数

第一节 猜测数的定义

第二节 完美图的猜测数

第三章 非完美图的猜测数

第一节 图的笛卡尔积的猜测数

第二节 有一个共同顶点图的猜测数

第三节 轮图的猜测数

第四章 结论

参考文献

致谢

个人简历