南开大学生命科学学院研究生招生简介

第一篇：南开大学生命科学学院研究生招生简介

南开大学生命科学学院研究生招生简介

南开大学生物系始建于1922年，在此基础上于1993年成立生命科学学院。学院现设有微生物学系、生物化学与分子生物学系、遗传学和细胞生物学系、植物生物学和生态学系、动物生物学和发育生物学系，建有分子生物学研究所和昆虫学研究所，泰达功能基因组学研究中心、生物基础教学实验中心和艾滋病研究中心，形成了“五系、二所、三中心”的教学科研布局。现有微生物学和动物学两个国家重点学科，植物学被确定为国家重点建设学科，另外作物遗传育种和细胞生物学是天津市重点学科。学院建有生物活性材料教育部重点实验室、分子微生物学与技术教育部重点实验室、天津市微生物功能基因组学重点实验室和蛋白质科学重点实验室四个省部级重点实验室。

学院现有教职工170人（专职教师106人），其中中国科学院院士1人，长江学者11人，国家杰出青年基金获得者9人，教授59人，副教授35人，形成了一支实力强、水平高、学科齐全、结构合理的学术队伍。

近年来，学院科研条件不断完善，建有动物转基因平台、蛋白质组学与基因组学平台、细胞分离及细胞成像平台、结构生物学平台及公共服务平台等。

五年来，生命科学学院共承担国家和省部级科研项目250余项，到位科研总经费过两亿元，发表SCI论文近500篇，并获得多项国家及天津市大奖。

学院在微生物学、动物学、植物学、遗传学、细胞学、生态学、生物信息学、生物化学与分子生物学8个二级学科招收和培养博士、硕士研究生。目前，在校硕士生391人，博士生239人。欢迎优秀的本科毕业生来南开大学生命科学学院学习深造！

南开大学生命科学学院网址：http://sky.nankai.edu.cn/script/sky/Chinese/index.asp联系地址：南开大学生命科学学院研究生办公室（生物站A103）300071 电话：022－23503593

Email: chenchen@nankai.edu.cn

第二篇：南开大学生命科学学院本科生

南开大学生命科学学院本科生 到校外做毕业论文协议书

根据南开大学本科生到校外做毕业论文的有关规定，南开大学生命科学学院同意本科生到校外相关应邀单位做毕业论文，但应遵守以下协议：

1.校外指导教师承担因学生到校外做毕业论文产生的必要费用，并负责学生在校外做毕业论文期间的学习和生活管理，为学生提供学习和生活的便利条件，对学生进行必要的管理和安全教育，确保学生的人身安全。

2.校外指导教师原则上应具有副高级及以上职称，对学生毕业论文给予及时地指导和检查，确保学生本科毕业论文的进度和质量。

3.学生应与校内指导教师保持联系，汇报工作进展，按照学校要求进行中期检查，切实加强学生毕业论文的过程管理。

4.学生到校外做毕业论文不得影响校内的正常学习，同时应按照学校规定回校参加毕业论文答辩，学生毕业论文成绩以南开大学生命科学学院答辩委员会最终成绩为准。

5.学生本人应遵纪守法，严格遵守校外单位的规章制度。学生在校外单位的安全由学生本人和校外指导教师负责；其他时间学生的安全责任由学生本人负责。

本协议一式两份，由南开大学生命科学学院和校外导师各留一份，未尽事宜，由双方另行协商解决。

南开大学生命科学学院（盖章）

年 月 日

校外指导导师： 校外单位（盖章）

年 月 日

学生本人：

年 月 日

第三篇：生命科学学院.

生命科学学院

长江大学生命科学学院设有生物技术系、生物工程系和食品科学系，拥有遗传学硕士学位点，现有生物技术、生物工程和食品科学与工程3个本科专业及食品生物技术、食品营养与检测和生物制药技术3个专科专业，在读各类全日制学生达1500余人。学院师资力量雄厚，现有教职工56人，专任教师中有教授8人，副教授9人，高级职称教师占教师总数的40%，教师中13人具有博士学位，21人具有硕士学位，高学位教师占专任教师总数的81%。设有生物化学、分子生物学、细胞生物学、微生物学、发酵工程、食品化学与安检和农产品加工与贮藏7个实验室及植物与微生物基因工程重点实验室，仪器设备总值达800余万元。全院承担有国家及省部级各类科研项目30余项，并取得了一批科研成果。生命科学学院将与农学、医学、石油等相关学科相结合，构筑新的更高、更宽的生命科学发展平台，建成国内有特色、省内有地位的生命科学高级人才培养与学科建设基地。

生物技术专业（本科）

培养目标：本专业培养掌握生命科学的基本理论和较系统的生物技术基本理论、基本知识，具备良好的科学素养及实践技能的高级专门人才。主干学科：生物学

主要课程：微生物学、细胞生物学、遗传学、生物化学、分子生物学、生物化学技术、基因工程、细胞工程等。就业方向：学生毕业后，可在科研机构或学校从事生物技术领域的科学研究与辅助教学工作，可在工业、医药、食品、农、林、牧、渔、环保、园林等行业的企业、事业和行政管理部门从事与生物技术有关的应用研究、技术开发、生产经营和管理等工作。

生物工程专业（本科）培养目标：本专业培养德智体美全面发展，具备生命科学的基本知识和较系统的生物技术及其产业化的科学原理、工艺技术过程和工程设计的基本理论和基本技能，能在生物技术与工程领域从事设计、生产、管理和新技术研究、新产品开发的应用型高级工程技术人才。主干学科：生物学、化学、化学工程与技术

主要课程：无机及分析化学、有机化学、生物化学、普通生物学、物理化学与胶体化学、化工原理、微生物生物学、生化工程、酶工程、细胞工程、基因工程、发酵工程、蛋白质工程、生物工程下游技术、发酵设备。

就业方向：学生毕业后，可到学校、科研院所、生物工程公司、食品酿造公司、医院、药品检验所、生物药厂、现代农业、育种繁殖等单位从事研究、开发和实用技术性工作。

食品科学与工程专业（本科）

培养目标：本专业培养具有坚实的化学、生物学、食品工艺学、食品工程学等方面的基本知识、基本理论、基本技能，能在食品领域从事食品生产技术管理、科学研究、新产品开发、工程设计、食品质量检测的高级专门人才。主干学科：化学、生物学、食品科学与工程

主要课程：有机化学、生物化学、食品化学、微生物学、食品生物技术、果疏加工工艺学、粮油加工工艺学、水产品加工工艺学、乳制品加工工艺学、肉制品加工工艺学、食品工程原理、食品加工机械、食品工厂设计、食品安全检测。

就业方向：学生毕业后，可在科研院所或学校从事相关的科学研究与教学工作，可在食品行业的企、事业单位从事行政管理、科学研究、技术开发、品质监控、生产经营等工作。

食品生物技术专业（专科）

培养目标：本专业培养德智体美劳全面发展，具有食品科学基础知识，较好地掌握食品生物技术的基本理论和基本技能，了解本学科的应用前景和最新发展动态，具有良好的科学素养及技术开发、生产管理等能力的应用型人才。

主干学科：食品科学、微生物学、生物化学与分子生物学

主要课程：生物化学、食品微生物学、蛋白质工程、发酵工程、食品酶学、细胞工程、基因工程、分子生物学、生物技术与食品检测、现代生物技术与疫苗、食品工艺学、食品分析检测技术等。就业方向：可在食品生产、食品卫生检测与管理、微生物应用、植物组织培养、食用菌应用、进出口检疫、环境保护、各类观赏植物生产等研究与开发部门，从事食品加工（肉制品加工、蛋制品加工、乳制品加工及其品质检测）、酿造（制酒、酿制酱油、醋等调味品）、植物脱毒快繁、食用菌生产与加工、制药（药品生产、检验）等行业的管理、技术和研究开发。

食品营养与检测专业（专科）培养目标：本专业培养德智体全面发展，政治素质、知识和能力结构适应社会经济发展需要，具备食品检测和分析、环境科学、食品科学的基本理论和技能，熟知国际食品质量安全体系和标准体系，从事食品质量与安全的检测、控制、监督、执法、管理的高级技术型、应用型人才。

主干学科：食品质量检测与安全评价、食品质量标准体系、食品科学、环境科学

主要课程：食品工艺学、环境化学、食品化学、食品微生物学、现代食品分析检测技术、食品营养与卫生学、食品毒理学、食品法规与标准、食品质量管理学等。

就业方向：毕业后可从事食品生产、营养与食品安全的管理等方面的工作，包括全国各级食品卫生监督部门、营养与食品安全服务部门、食品企业、餐饮业、教学单位和科研院所。

生物制药技术专业（专科）

培养目标：培养掌握生物药物的制备和生产的基本理论、基本知识和实验技能，具备生物制药生产工艺研究和生产过程控制及产品质量分析能力的高级应用型专门人才。主干学科：化学、生物学、制药学

主要课程：高等数学、计算机应用与维护、无机及分析化学、有机化学、生物化学、普通生物学、药物化学、微生物学、细胞生物学、化工原理、生物制药工艺学、生物制药设备及药物分离纯化、药物分析、药事管理与法规。

就业方向：学生毕业后可在药品生产企业、药品经营企业、医院及药品检验所及相关的生物公司等单位从事技术管理、产品开发、营销、质量分析检测工作。

第四篇：南开大学数学科学学院毕业论文

南 开 大 学

本 科 生 毕 业 论 文(设 计)

中文题目：关于轮图的猜测数

外文题目：On the guessing number of wheel graphs

学

号：0915104 姓

名：赵贤秀 年

级：2009级 学

院：数学科学学院 系

别：应用数学系 专

业：数学与应用数学 完成日期：2013年5月1号 指导教师：金应烈教授

关于南开大学本科生毕业论文(设计)的声明

本人郑重声明：所呈交的学位论文(设计)，题目《关于轮图的猜测数》是本人在指导教师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、以公开发表或没有公开发表的作品内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。

学位论文作者签名：

****年**月**日

本人声明：该学位论文是本人指导学生完成的研究成果，已经审阅过论文的全部内容，并能够保证题目、关键词、摘要部分中英文内容的一致性和准确性。

学位论文指导教师签名：

****年**月**日

摘要

现代社会可以说在很大程度上是通过各种网络来管理与控制的，因此用图论等数学工具分析网络问题是一项十分重要的课题。而图的猜测数是一个研究网络编码策略的有效工具。

近年来很多学者试图利用图论、代数和信息论的方法研究图的猜测数，但目前尚未得到一种系统有效的方法来解决图的猜测数问题，特别对于无向圈的猜测数等问题目前还没有较好的结论。因此，本文针对圈的一种扩充图即轮图的猜测数进行了研究，并得到了有向轮图和无向轮图猜测数。

关键词 猜测数;轮图;独立数;团覆盖数;

I

Abstract It can be said that modern society is managed and controlled with a variety of networks in a large extent, so analysis of network problem with mathematics is a very important task, while guessing number is efficient in considering strategy of network coding.In recent years, many scholars tried to do researches on the guessing numbers using the powerful mathematical technique, such as graph theory, algebra and information theory.But the research on the guessing numbers has not formed a method which is effective and systemic.Especially, the study of circles is still a difficulty.Therefore, this paper studied the guessing number of wheel graphs which is a expansion of circles, and got guessing number of wheel graphs.Key Words guessing number;wheel graphs;independence number;clique cover;

II

目录

摘要.................................................................................................I ABSTRACT.......................................................................................II 目录..............................................................................................III 一．引言............................................................................................4 二．猜测数问题的简介....................................................................6

（一）猜测数问题的提出..................................6

（二）网络编码与猜测数..................................8

（三）关于猜测数的一些结论..............................9

1.有向图的猜测数................................................9

2.无向图的猜测数...............................................11

三．轮图的猜测数..........................................................................13

（一）有向轮图的猜测数.................................13

（二）无向轮图的猜测数.................................14

四．结束语......................................................................................19 参考文献..........................................................................................20 致

谢..............................................................................................22

III

一． 引 言

最大流最小割定理决定了网络的最大吞吐量。在多播通信网络中，通过网络编码可使信息传播速率达到最大值。网络编码的诞生和发展为网络信息传输指明了一个新的研究方向。

一个通信网络由一些通信节点和连接在某些节点之间的一些通信链路组成。网络通信的目的是要将网络中源节点产生的消息通过网络传输到汇节点。

在传统的通信网络中，信息传输采用路由的机制，每个中间节点将收到的信息传给与它相邻的下一个节点。在2000年，A.Rhlswede等人提出了新的传输方案，让每个中间节点起到一个编码器的作用，将其收到的信息进行适当的编码后传输出去，这种方案叫做网络编码。

1999年，香港中文大学的杨伟豪教授和美国南加州大学的张箴教授在一篇关于卫星通信网络的学术论文“Distributed Source Coding for Satellite Communications”IEEE Transcations on Information Theory[1]中首次提出了网络编码(Network coding)的概念。

德国Bielefeld大学的Ahlswede教授，西安电子科技大学的蔡宁教授，以及香港中文大学的李硕彦教授和杨伟豪教授(2000)在论文“Network Information Flow” IEEE Transactions on Information Theory[2]中完全发展了网络编码的思想。他们以著名的蝴蝶网络(Butterfly Network)为例阐述了网络编码的基本原理。

伦敦大学的S.Riis在2006年发表的论文“Utilizing public information in Network Coding” Springer[3]中首次提出了猜测数问题，并且证明了网络编码问题等价于对应有向图的猜测数问题。并在2007年发表的论文“Information flows, graphs and their guessing numbers”Electronic Journal of Combinations[4]中说明可以把线路复杂性理论(Circuit Complexity Theory)的核心问题和网络编码问题转化为有向图的猜测数问题。论文中还介绍了一种特殊图叫做钟图(Clock-graphs)，利用线性猜测策略求出了钟图的猜测数。

同年在论文“Graph Entropy, Network Coding and Guessing games” [5]中，S.Riis借用信息论中熵的概念研究了图的猜测数问题。这篇文章中定义了有向图的熵和几种类熵，并且证明任意图的猜测数等于其熵值，利用熵计算出有些图的猜测数(例如无向圈C5的猜测数与广义猜测数)。

T.Wu等人(2009)发表的论文“On the guessing number of Shift graphs” Journal of Discrete Algorithms[6]中应用圈填充数等概念给出了有向图猜测数的上下界，并且应用这一结论计算了一种Cayley图叫做旋转图(Shift graphs)[9]猜测数的上下界。

M.Gadouleau和S.Riis(2011)的论文“Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications” IEEE Transactions on Information Theory [7]中得出了如下两个结论;第一是定义任意有向图的猜测图，并且证明任意有向图的猜测数等于其猜测图的独立数的对数。论文中利用猜测图给出几种有向图乘积[10]的猜测数和在不同编码集下猜测数之间的关系式。第二是找出了围长为l(l3)的一系列有向图使其线性猜测数与其顶点数之比趋于1。

D.Christofids和K.Markström(2011)在他们的论文“The guessing number of undirected graphs”Electronic Journal of Combinations[8]中专门讨论了无向图的猜测数问题，并利用无向图的(分数)团覆盖数和(分数)独立数[11]给出了无向图猜测数的上下界，证明了图的猜测数等于编码图的独立数的对数。同时，D.Christofids和K.Markström在这篇论文中提出了奇圈的猜测数问题，即g(C2k1,2)(k3)和g(C2k1,3)(k4)等尚未解决的问题。

本文主要针对轮图的猜测数问题进行了研究。首先利用论文[6,8]的结论初步计算出轮图猜测数的上下界。其次，对于无向轮图，以构造一个猜测策略的方法得到了与奇圈猜测数的关系。

二．猜测数问题的简介

（一）猜测数问题的提出

先考虑一个合作游戏(A game of cooperation)，其规则如下：

n个人掷s-面骰子(其中每一面的点数分别为0,1,....,s-1)，然后把自己的值给别人观看。如果所有人都猜对了自己的值，则称猜测成功，否则就算猜测失败。

在无策略的情况下，所有人猜对的概率为

Pr(win)1/sn(2.1)假设每个人都知道其他n1个人的值(内部消息)。那么，我们可以采用以下策略使得上述概率达到最大值。

令每个人都相信所有人的值之和被s整除，此时所有人都可以计算出自己的值。

在这一策略下，所有人猜对的概率等于所有人的值之和被s整除的概率，即

Pr(win)1/s

(2.2)我们把这游戏推广到一般有向图中;设G(V,E)为有向图，并把图中每一节点视为游戏参赛者。假设每一点的值均属于S0,1,2,...,s1，其中s2,3,4,...,。对于两个节点v,wV，假设当(v,w)E时v知道w的值，否则v不知道w的值。此时，希望所有人猜对的概率达到最大值。

定义2.1 设G(V,E)(顶点集为Vv0,v1,...,vn1，边集为EVV)为有向图，记S0,1,2,...,s1，s2，此时映射fj:SdjS称为顶点vj的猜测策略，其中dj表示节点vj的入度。并把向量函数F(f1,f2,...,fn):SnSn称之为有向图G的一个猜测策略，其中F(c)(f1(c),f2(c),...,fn(c))，cc0,c1,...,cn1，nV。易知，猜测策略的总数为s

dj1nj。

定义2.2 设F为有向图G(V,E)的一个猜测策略，Fix(F){cSn:F(c)c}称为猜测策略F的固定点集。

定义2.3 称g(G,s)maxlogsFix(F)为有向图G的猜测数，此时等号成立的猜

F测策略称为最优策略，记为Fopt，其中Fix(F)表示固定点集的顶点数。称gl(G,s)maxlogsFix(Flinear)为有向图G的线性猜测数，其中Flinear表示所有Flinearfi均为线性映射的策略。显然有，g(G,s)glG,s

(2.3)下面证明上述最优策略为在合作游戏中所有人猜对的概率最大的策略。设cc0,c1,...,cn1为所有人的真值向量，则所有人vi猜对当且仅当

"i,ci=fi(c)ÛF(c)=cÛcÎFix(F)

因此，猜测策略F下所有人猜对的概率为 Pr(win|F)Fix(F)Snsg(G,s)n

s(2.4)例2.1 完全图Kn(n1)的猜测数为 g(Kn,s)gl(Kn,s)n1，s2

(2.5)证明：首先证明g(Kn,s)n1。

对任意c0,c1,...,cn2Sn1，如果c0,c1,...,cn1Fix(F)，则

cn1fn1c0,c1,...,cn2

(2.6)

因此，Fix(F)sn1，即g(Kn,s)n1。下面证明g(Kn,s)n1。

n我们取如下策略F(f0,f1,...,fn1):ZnsZs，其中S=Zs

fi(c0,...,ci1,ci1,...,cn)(c0...ci1ci1...cn)(0in1)

(2.7)则Fix(F)cc0,...,cn1:c0...cn10

从而Fix(F)sn1，即得g(Kn,s)n1。例2.2 设D为无圈有向图，则g(D,s)gl(D,s)0

□

（二）网络编码与猜测数

这一节中我们将介绍网络编码与猜测数问题的对应关系。在论文[3]中证明了每个网络编码问题均可转化为有向图的猜测数问题。

定义2.4 设N给定的网络，S为编码集(Ss)，如果利用网络编码可以实现源节点到所有汇节点的组播，则称信息流问题N,S可解，并把这种策略称为信息流问题N,S的解。

在这一节中，我们主要考虑源节点和汇节点数相同的网络组播问题。我们先把网络N的源节点和汇节点一一结合起来，然后由恒等映射可以得到有向图GN。例如在图1中，由图(a)和(c)以源汇节点结合的方法可以得到图(b)和(d)。

（a）

(b)

(c)

(d)

图1 网络编码到猜测数问题的转化

定理2.1 [3] 信息流问题N,S的解与有向图GN上成功猜测的概率至少为1sGNnodesn的猜测策略一一对应，其中GNnodes表示有向图GN的顶点数。

证明：考虑有向图GN(V,E)

设网络N的源节点和汇节点分别记为i1,i2,...,in和o1,o2,...,on 由于网络N中无圈，所以可以对中间节点定义偏序，记为 i1i2...inn1n2...nmo1o2...on

(2.8)

下面考虑网络N的任意网络编码策略Ff1,f2,...,fm,g1,g2...gn

z1f1(x1,x2,...,xn)z2f1(x1,x2,...,xn,z1)..........zmf1(x1,x2,...,xn,z1,z2,...,zm1)x1outg1(x1,x2,...,xn,z1,z2,...,zm)outx2g2(x1,x2,...,xn,z1,z2,...,zm)

(2.9)..........outxngn(x1,x2,...,xn,z1,z2,...,zm)其中xi(1in)、zi(1im)和xiout(1in)分别表示源节点、中间节点和汇节点的信息。

则与它对应的有向图GN的猜测策略为F*f1,f2,...,fm,g1,g2...gn，realrealz1guessf1(x1real,x2,...,xn)guessrealrealz2f2(x1real,x2,...,xn,z1real)............guessrealrealrealrealzmfm(x1real,x2,...,xn,z1real,z2,...,zm1)xguess1g1(xreal1,xreal2,...,xrealn,zreal1,zreal2,...,zrealm)(2.10)guessrealrealrealrealx2g2(x1real,x2,...,xn,z1real,z2,...,zm)............guessrealrealrealrealxngn(x1real,x2,...,xn,z1real,z2,...,zm)显然上述策略F与F*一一对应。以下证明猜测策略下猜测成功的概率为1sm当且仅当信息流问题有解。

猜测成功的概率为1sm Pr中间节点都猜对1sm

realguessrealx|zz,i)1信息流问题N,S有解。Pr(xguessjjii□

推论2.2 [3] 源节点和汇节点数均为n的信息流问题N,S可解当且仅当对应的有向图GN的猜测数满足g(G,s)n。

（三）关于猜测数的一些结论

1.有向图的猜测数

先考虑子图和剖分图的猜测数。定理2.3设H为有向图G的子图，则有 g(H,s)g(G,s)，gl(H,s)gl(G,s)(s2)

(2.11)证明：设F和Fl分别为有向图H的最优猜测策略与线性猜测策略。则F和Fl可视为G的猜测策略和线性猜测策略。因此，有

g(H,s)log2Fix(F)g(G,s),gl(H,s)log2Fix(Fl)gl(G,s)定理2.4 [6] 设H为有向图G的子图，则有

□

g(G,s)g(H,s)V(G)V(H)(2.12)其中V(G)V(H)表示有向图G和H的顶点之差。

推论2.5设有向图G为由图G删除一顶点得到的图，即GGv，则有 g(G,s)g(G,s)g(G,s)1

(2.13)定理2.6 设有向图G为由图G剖分一点得到的图，则有

g(G,s)g(G,s)

(2.14)证明：设u,vV(G)且边(u,v)E(G)，并设G为在图G的边(u,v)上添加一个顶点w得到的图，即V(G)V(G)w, E(G)E(G)(u,v)(u,w),(v,w)。

和fv为 ,fv,...，其中fw设Ffu,fv...为G的最优策略。令Ffu,fw

(xu)xu, fvfv(xw,...)fw(2.15)则F为G的猜测策略，并且显然有Fix(F)Fix(F)。因此，g(G,s)g(G,s)

,fv,...为G的最优策略。令 反之，设Ffu,fw

(xu),... fv(xu,...)fvfw(2.16)

则Ffu,fv...为有向图G的一个策略，且 因此，g(G,s)g(G,s)。

故g(G,s)g(G,s)。□

例2.3 设Cn为顶点数为n的有向圈，则有向圈的猜测数为

g(Cn,s)gl(Cn,s)1

(2.17)证明：当m2时，Cm1可以视为Cm的剖分图。由定理2.3有 g(Cm1,s)g(Cm,s)，gl(Cm1,s)gl(Cm,s)

(2.18)而C2K2为完全图，因此

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为有向图，对S0,1(s2)有 (D)gl(D,s)g(D,s)(D)

(2.21)其中(D)表示有向图D中点不相交的圈数的最大值，(D)表示有向图D中把D变为无圈的最小删除边数。

定理2.8 [6] 设D为有向图，则有 gl(D,s)max(nrank(IA))nminrank(IA)

AADAAD(2.22)

I表示n阶单位矩阵，AAD表示当aij0时其中AD表示有向图D的邻接矩阵，D必有aij0。

2.无向图的猜测数

我们可以把无向图视为双向边有向图、无向图的猜测数定义为对应双向边有向图的猜测数。下面利用图论的一些概念计算猜测数的上下界。

定义2.5 设G(V,E)为无向图，节点集VV且E(V)E(V)(VV)，则称G(V,E(V))为图G的导出子图。如果其导出子图为完全图，则称此子图为图G的一个团，并记为Kn(nN)。

定义2.6 若有一团集Kn|nN覆盖了图G的所有边，即图G中每一条至少属于一个Kn，这时我们称团集中的团的个数为团覆盖数，记为cp(G)。定理2.8 [8] 设G(V,E)为无向图，对任意s2有 ncp(G)g(G,s)n(G)

(2.23)其中(G)为图G的独立数，cp(G)为图G的团覆盖数。

三．轮图的猜测数

（一）有向轮图的猜测数

在这一节中，我们考虑有向圈上添加一个顶点并与它连接所有顶点，这类图定义为轮图。为了严格定义轮图，先把有向圈用数学符号来表示，其表示如下 Cn(V,E)，其中V0,1,2,...,n1，E(i, i1 mod n)|0in-1 定义3.1 设D(V,E)为有向图，其顶点集和边集分别为

n1V0,1,2,...,n，E(i, i1 mod n)|0in-1(i, n)或(n, i)(3.1)

i0则称有向图D(V,E)为有向轮图，并记为Gwheel(n)。

记k{ i|(n,i)E,(i1mod n, n)E, 0in1}，它表示顶点n的入出变化数。引理 设Gwheel(n)为有向轮图，则有

1g(Gwheel(n),s)2

(3.2)证明：由定理2.5和例2.3有



g(,)1Gg(),C)nsg(,)Cnsw(heenls(3.3)□

定理3.1 有向轮图的猜测数为g(Gwheel(n),s)1当且仅当k1。证明：(必要性)

反证法：假设k2，只需证明g(Gwheel(n),s)2。

此时，易证Gwheel(4)(k2)为Gwheel(n)(k2)的子图(见图2)。

图2 有向轮图Gwheel(4)

Gwheel(4)(k2)的邻接矩阵为

01000001100001001

01001010

AG(4)wheel(3.4)01记 A00000001001101000s1，则AAG且rank(IA)2。wheel(4)00s101由定理2.3和定理2.,8知， g(Gwheel(n),s)g(Gwheel(4),s)gl(Gwheel(4),s)4rank(A)2(充分性)

(3.5)当k0时，即n点的出度或入度为0。

V删除顶点0,则Gwheel(n)变成有向无圈图。由推论2.5知，g(Gwheel(n),s)1。

因此，g(Gwheel(n),s)=1。

当k1时，删除顶点m，其中m为满足(n,m)E且(m1modn,n)E的点。

则Gwheel(n)变成有向无圈图，因此，g(Gwheel(n))1。故g(Gwheel(n))=1。

推论3.2有向轮图的猜测数为

1:当k1g(Gwheel(n))

2:当k2□

(3.6)

□ 证明：由定理3.2和引理显然成立。

（二）无向轮图的猜测数

类似于有向轮图，我们可以考虑无向轮图的猜测数。

定义3.2 设D(V,E)为如下定义顶点集和边集的无向图，n1V0,1,2,...,n，E(i, i1 mod n)|0in-1(i, n)(n2)(3.7)

i0此时，称D(V,E)为无向轮图，记为Gwheel(n)。定理3.3 有向轮图的猜测数为

(n1)/2g(Gwheel(n),s)(n1)/21 ： 当n为奇数 g(Gwheel(n),s)n/21 ： 当n为偶数(3.8)证明：分别当n为奇数和偶数时考虑轮图的猜测数。1.当n为偶数时

首先，Gwheel(n)中没有顶点数大于3的完全子图(团)。

除掉顶点n之后，CnGwheel(n){n}中没有顶点数大于2的完全子图(团)。因此，Gwheel(n)的团覆盖数满足

n/22cp(Gwheel(n))(n13)/21n/2

(3.9)

而{2i,2i1}{n2,n1,n}为Gi0wheel(n)的n/2-团覆盖。

从而，cp(Gwheel(n))n/2。下面考虑Gwheel(n)的最大独立数。

由于顶点n与其他所有点都相邻，所以Gwheel(n)的包含顶点n的独立集的顶点数为1。设S(nS)为独立集，则iS, 都有i1(mod n)S。因此，Sn/2。另外，S{2i|i0, 1,..., n/21}为独立集，且Sn/2。从而，(Gwheel(n))n/2。

由定理2.8知，g(Gwheel(n),s)(n1)n/2n/21。2.当n为奇数时

类似于上述n为偶数的情形，分别计算团覆盖数和最大独立数。

Gwheel(n)中没有顶点数大于3的完全子图(团)，而且除掉顶点n之后CnGwheel(n){n}中没有顶点数大于2的完全子图(团)。因此，Gwheel(n)(n13)/21(n1)/2。

n/22所以，Gwheel(n) {2i,2i1}{n1,n}为最大数团覆盖，即

i0cp(Gwheel(n))(n1)/2

(3.10)设S(nS)为独立集，与上述n为偶数的情形类似地可以证明

Sn/2(n1)/2

(3.11)因此，S{2i|i0,1,...,(n1)/21}(S(n1)/2)为最大独立集，即

(Gwheel(n))(n1)/2

(3.12)

□ 由定理2.8知，(n1)/2g(Gwheel(n),s)(n1)/21。

下面考虑s2时任意图上加一个顶点并与此点连接所有顶点的情形。为此，先规定如下符号。

设G(V,E)为无向图，用GG{v}表示顶点集为VV{v}、边集为EE(u,v)|uV的无向图。

定义3.11设G(V,E)为无向图，F为无向图G(s2)的一个猜测策略，则称H(X)1nF(1nX)为F的共轭策略，记为F，其中1n表示n维向量。引理 Fix(F)Fix(F)

证明: 对任意XFix(F)，记X1nX，则有 F(X)1nF(1nX)1nF(X)1nXX

(3.13)反之，当XFix(F)时有，XFix(F)。

而且显然有XY当且仅当XY。因此，Fix(F)Fix(F)。由引理可以知道，当F为最优策略是F也为最优策略。

□

定理3.5 设G(V,E)(Vn)为无向图，则有 g(G,2)log231g(G{vn1},2)g(G,2)1

(3.14)证明：设Ff1,f2,...,fn为最优策略，即g(G,2)log2Fix(F)。记MXFix(F)|F(X)X，并称M为对称固定点集。不妨设MFix(F)/2(否则，以最优策略F代替F)。

Gvn1上取如下策略Hh1,h2,...,hn1，fi(x1,...,xi1,xi1,...,xn):xn10其中hi(x1,...,xi1,xi1,...,xn1)

(1in)，f(x,...,x,x,...,x):x1i1i1nn1i1

0:XFix(F)M hn1(x1,x2,...,xn)1:XFix(F)M(3.15)则对XFix(F)有，X,0Fix(H)，X,1Fix(H)从而，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 无向轮图Gwheel(5)的猜测数为

g(Gwheel(5),2)log251

(3.16)证明：在文[8]中介绍了无向轮图C5的猜测数为g(C5)log25，并且最优策略为

1 当xy0时 F(f1,...,f5)，其中fi(x,y)0 其 他 (3.17)此时，按定理3.5证明构造轮图Gwheel(5)的猜测策略，其为如下

F(f1,...,f5,f)

(3.18)0 当xyx6时0 当X(x1,...,x5)Fix(F)其中f(x1,...,x5)，fi(x,y,x6) 否 则 1 当X15XFix(F)x,y,x6表示第i(1i5)顶点所得到的信息。则由推论2.5有，log251log2Fix(F)g(Gwheel(5),2)g(C5,2)1log251

(3.19)

故g(Gwheel(5),2)log251。

从例3.1可以猜想无向奇轮图的猜测数等于奇圈的猜测数加1。定理3.6 无向轮图的猜测数为

□

g(Gwheel(n),s)n/21 : 当n为偶数g(Gwheel(n),s)g(Cn,s)1 : 当n为奇数(3.20)证明：只需证明n为奇数的情形。

设Pf0,f1,...,fn1为奇圈CnGwheel(n){n}的最优策略，其中fixi1,xi1

0in1为顶点i的局部策略。

下面考虑Gwheel(n)上的策略P(f0,f1,...,fn1,fn）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)

则对任意x(x0,x1,...,xn1)Fix(P)和任意a0,1,...,s1有

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)，即有

Fix(P)sFix(P)

(3.29)

从而，g(Gwheel(n),s)logsFix(P)1logsFix(P)1g(Cn1,s)。由推论2.5有，g(Gwheel(n),s)1g(Cn1,s)。

□

四．结束语

由于确定图的猜测数是NP-难问题，而且猜测数的研究起步比较晚，目前还没得到一种系统有效的计算方法。2006年S.Riis[3]提出猜测数问题之后，T.Wu等人从不同的角度出发研究了图的猜测数问题。他们用图的独立数、团覆盖数和圈填充数[5]给出了猜测数的上下界。此外，用熵[5]、猜测图[7]和编码图[8]等新的概念把猜测数问题转化为另一种问题，并且用此工具算出了一些特殊图的猜测数。但是对很多图，特别对无向奇圈C2n1尚未得到确切的猜测数值。

目前，除了奇圈之外对其他简单图的猜测数已经得到了一定的结果，因此我们需要考虑笛卡尔积等图的扩充图的猜测数问题。对于完全图、二部图、路、有向圈和无向偶圈之间笛卡尔积的猜测数，已经得到了非常好的结论。进一步，我们还可以考虑树、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.org/pdf/0711.417541, 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 coding.In Proceedings of the 2002 IEEE Infocom, 2002.[14] B.E.Tarjan, A.E.Trojanowski.Finding a maxium independent set.SIAM J.Comput, 6(3):537-546, 1977.[15] 蒋长浩.图论与网络流.中国林业出版社.2001年, 第一版, 174~194.致

谢

在论文完成之际，我首先向关心帮助和指导我的指导老师金应烈教授表示衷心的感谢并致以崇高的敬意！金应烈老师作为一名优秀的、经验丰富的教师，具有丰富的数学知识和教学经验，在整个论文讨论和论文写作过程中，对我进行了耐心的指导和帮助，提出严格要求，引导我不断开阔思路，为我答疑解惑，鼓励我大胆创新，使我在这一段宝贵的时光中，既增长了知识、开阔了视野、锻炼了心态，又培养了严谨求实的治学方法和勇于探索的科研精神。值此论文完成之际，谨向我的导师致以最崇高的谢意！

光阴似箭，转眼间，四年的留学生活即将结束，依依不舍之情难以言表。要感谢的人太多，要说的话也很多。我会永远记得在南开留学的美好时光。最后，我衷心地感谢在南开四年以来所有老师对我的大力栽培。

第五篇：兰州大学研究生学术年会 - 兰州大学生命科学学院

兰州大学生命科学学院研究生学术年会

优秀论文征集细则

（一）研究生学术年会论文征集对象

我院各年级在读硕士、博士研究生（2010级、2011级、2012级）

（二）学术年会参选论文的要求

1、研究生须每人提交至少一篇论文，论文内容与本主题相关，硕士2011级、2012级硕士研究生若提交文献综述或工作总结等均可。未提交论文者，将不能参与下一奖学金评定。

2、博士研究生必须提交至少一篇论文，获得“学术新人奖”及助研助学金特等奖的博士生必须参加学术年会“博士生学术论坛”，进行学术交流。需以第一作者提交与大会议题相关学术论文一篇。论文要求反映研究生主要研究内容及研究成果，突出作者的见解和创新点，具有一定的理论和实际应用价值，鼓励学科交叉。

3、提交年会的学术论文原则上是尚未正式发表的论文。

4、提交学术年会的论文应该经过导师认真指导，达到发表条件的论文。

5、论文选题范围应符合各研究小组研究方向要求。

6、论文规定统一用A4复印纸激光打印，字数以2000--5000字为限，论文前有200字左右的中文和英文摘要；第一页页角附作者简介，内容包括姓名、性别、所属院系、导师和研究方向。排版要求清楚规范，格式要符合《兰州大学学报》的发表要求。

（三）优秀论文评选条件

1、论文选题新颖，观点明确，内容充实，论据充分，论证合理，逻辑性强，有较高的理论价值和实际应用价值。

2、论文反映了本学科的最新研究进展和成果，具有一定的创新性。

3、论文写作规范，表述准确，格式符合《兰州大学学报》发表论文的规范要求。

4、论文遵循学术道德规范，无抄袭、剽窃等现象。

5、论文涉及的内容无政治性错误，无国家保密事项。

（四）优秀论文评选比例和方式

1、各专业分论坛优秀论文

分一等奖、二等奖、三等奖三个层次，评选比例分别为： 一等奖：占各专业征集到的论文总数的3%； 二等奖：占各专业征集到的论文总数的5%； 三等奖：占各专业征集到的论文总数的10%。

2、院级优秀论文

各专业分论坛将获得一等论文推荐到学院，由学院组织评选出特别优秀论文为我院本届学术年会特等奖进行奖励。由学院组织专家评议，以无记名投票的方式产生。我院优秀论文的奖励标准为：

特等奖每篇奖励500元；

（学院从各专业一等获得者中评出）

一等奖每篇奖励 300元；（含各专业除院级特等后一等获得者）二等奖每篇奖励 200元；（含各专业二等）三等奖每篇奖励 100元。（含各专业三等）

优秀论文奖励将作为下一学业奖学金和助研助学金评定优先考虑的重要参考指标。

3、优秀组织奖励

以论文数量、论文质量为参考指标，一次性奖励1000元。

（五）论文征集时间

各专业与11月20日前将各专业所有论文电子版、获奖者名单及评选出各专业一等优秀论文纸质版，报至学院研究生办公室。