两类立方体的垂直3-树连通度的研究

摘要

斯坦纳树问题是组合优化中的一个重要问题.图论中的斯坦纳树问题在网络设计和电路分布中也有着广泛的应用.给定一个连通图G,图G的一棵S-斯坦纳树（S-树）是包含S中所有顶点的树T=（V′,E′）,使得S■V′.如果两棵树T和T′,满足E（T）∩E（T′）=■,V（T）∩V（T′）=S,则称T和T′是内部不交的.对于一棵S-树T来说，S■V（T）,任意的顶点v∈S,都有d（v）=1,则称树T为垂直S-树.垂直树连通度τ_G（S）为图G中内部不相交的垂直S-树的最大数目.垂直k-树连通度（2≤k≤n）定义为τ_k（G）=min{τ_G（S）:S■V（G）,|S|=k}.在本文中，证明了τ₃（CQ_n）=n-2（n≥3）,其中CQ_n是n-维交叉立方体；除此还证明了τ₃（FCQ_n）=n-1,其中n≥2,且FCQ_n是n-维折叠交叉立方体.

关键词

交叉立方体 / 折叠交叉立方体 / 斯坦纳树 / 内部不交 / 垂直树连通度