报告时间：2015年5月27日14:00-
报告人：黄小龙 博士
报告人单位：yl60000永利官网 yl60000永利官网
报告地点：教2-501室
报告题目：平面图和线图上的彩虹连通性研究
报告内容：假设在一个蜂窝网络中，人们希望能在任意两个顶点之间传送信息，并且要求该线路上的每条边被分配不同的信道。那么，在满足上述要求的前提下，最少需要使用多少不同信道才能保证网络中任意两点之间能够传送信息？将该网络抽象成一个图，研究证明这个最小值就是该图的彩虹连通数。图的彩虹连通性问题是近年来图论研究的热点课题，图的彩虹连通数和彩虹顶点连通数可以看作是连通度和色数的一种推广，具有重要的理论意义和应用背景。本报告主要内容包括：证明了给定一个边染色平面图G，判定图G在该染色下是否彩虹连通是NP-完全的。对于彩虹顶点连通性的复杂性问题，证明了给定一个顶点染色线图，判定该染色是否顶点彩虹连通是NP-完全的。研究了平面图的彩虹连通数的上界问题，给出了无桥平面图在具有较小直径条件下的彩虹连通数的上界。