广义de Bruijn有向图的k-元控制集

• 作者: 董艳侠 薛涛 张广
• 来源期刊: 运筹学学报
• 关键词: 广义de Bruijn有向图 控制集 k-元控制集
• 年，卷（期）: 2021,（2）
• 页码范围: 127-134
• 页数: 8页
• 分类号: O157.5|O158
• 语种: 中文
• DOI: 10.15960/j.cnki.issn.1007-6093.2021.02.010

摘要

G =(V,A)表示一个有向图,其中V和A4分别表示有向图G的点集和弧集.对集合Dk? V(G),如果对于任意点v ∈ V(G),都存在k个点ui,1≤i≤k(可能存在某个ui和v是同一点)使得(ui,v)∈ A(G),则称Dk是G的一个k-元控制集.有向图G的k-元控制数γxk(G)是G的最小k-元控制集所含点的数目.给出了广义de Bruijn有向图的k-元控制数的新上界,并且具体给出了构造广义de Bruijn有向图的k-元控制集的方法.此外,对某些特殊的广义de Bruijn有向图,通过构造其k-元控制集,进一步改进了它们k-元控制数的上界.