论文部分内容阅读
Everett和Borgatti引入了k-角色分配的概念。进一步，他们引入并研究了图G的k-角色可分配程度来表示图G可以在多大程度上进行k-角色分配，记作ak(G)．他们还给出了k=2时的k-角色可分配程度口2(G)的下确界，并回答了什么时候a2(G)达到下确界。本文证明了k≥3时，ak(G)的下确界为0，并证明了当图G为Gk+1^1，s图且a(s+1)≠0(modk+1)(n=2，3，4)时，ak(G)达到下确界；最后还刻画了能够(n-1)-角色分配的Gn^1，s图。