论文部分内容阅读
Everett和Borgatti引入了k-角色分配的概念,用于研究社会网络问题.对于图G,它的一个k-角色分配就是由各顶点映到正整数1,2...,k的一个函数,它满足:如果x和y有相同角色,那么分配到它们邻接点的角色的集合也相同.这种思想源自社会网络理论:我们说如果两个个体社会角色相同,那么和他们相联系的的个体的总体社会角色类别相同.Li sheng等人在《三角化图的2-角色分配》这篇文章中刻画了一类2-角色可分配的图:无差图.并在开放问题中提出:k≥3时,能否找出k-角色可分配的图类和相应的分配方法?本文对格图和环面蜂巢图以及G<, n>图作了相应的研究,其中用到了一种坐标化图的方法.k-角色可分配的图有很多优美的特性,但由于条件过强,这些性质不具广泛性;在实际问题中往往可以适当放宽条件,于是Roberts等人引入了域近角色分配的概念,得出了许多更具广泛性的定理.Roberts和Li Sheng证明了每个至少k个顶点的图是k-域近角色可分配的,这一命题对k=1,2,3,4,5是成立的.并在开放问题中提出:k≥ 6时,这一性质是否成立?本篇论文介绍了一种角色染色方法,用之证明了几乎所有的图都是7-域近角色可分配的;并给出了一种有效的判别图G是N-域近角色可分配的算法.这里我们引入随机图论中相关理论,在概率意义下解决了这一开放问题,并且所给方法有推广性,可用于解决k≥7时,特定k值的k-域近角色分配问题.