置换杨图的组合性质及其应用

置换杨图本质上是A.Postnikov在研究完全非负Grassnann元胞及其元胞分解时所定义的]-图(]-diagram)的一个子集.它的发现引起许多组合学者的关注和研究,其中L.K.Williams和E.Steingrí-sson是最先关注这类组合结构的,他们在研究它的组合性质时发现了它与置换群之间存在着一一对应关系Ψ.从置换杨图本身的结构出发按照行递归的方式给出了Ψ是一一映射的一个新方法,利用这种方法可简单地将任意的一个排列π∈Sn分解成若干圈的乘积形式,并且每个圈中的元素都是按递减顺序排列.     

变换图G+——的极大边连通性(英)

证明了对于任意的图G,其变换图G --是极大边连通的当且仅当G至少有两条边且不同构于2K2.     

似星树与路的乘积图的任意可分性

设似星树S=S(a₁,a₂,…,a_t,b₁,b₂,…,b_s), 其中a_i(1≤i≤t)是奇数, b_j(1≤j≤s)是偶数. 首先, 讨论似星树S与路P_l的乘积图SPl在t和s不同取值下是否为任意可分图, 并用图不含完美匹配的方法和反证法给出其不是任意可分图的充分条件; 其次, 分析图SP_l的Hamilton性, 并用似星树的任意可分性给出图为任意可分图的充分条件. 结果表明, 当t=1且s≤2时, 图SP_l是任意可分图; 当t≥2或t=0, 或者t=1, s≥3, b₁=b₂=…=b_s, t+s≥l+2时, 图SP_l均不是任意可分图.     

生成树及2134有禁错排置换

为了证明猜想:2134有禁错排置换的生成树可能同构于2143有禁错排置换的生成树,即它们有相同的生成树。首先给出了A2n(2134)的生成树的继承法则,接着证明了A2n(2134)的生成树同构于A2n(2143)的生成树,最后得到了|A2n(2134)|=|A2n(2143)|=|SYT(n,n,n)|=2·(3n)!/(n!(n+1)!(n+2)!)。     

线图的限制性邻域连通度

在间谍工作中,限制性边邻域连通度和限制性邻域连通度比一般连通度和边连通度更加稳定可靠。文中提出了两个新概念:限制性邻域连通度和限制性边邻域连通度。证明了如果图G的线图L(G)是κ’NC图,那么κRNC(L(G))=λRNC(G)当且仅当G不是super-λRNC。并且证明了如果G是λpN C+1,q+1(G)连通图,那么L(G)是κpN,Cq连通的,并且κpN,Cq(L(G))=λpN C+1,q+1(G)。     

变换图G--+的超边连通性

如果λ(G)=δ(G),则称图G是极大边连通的;如果G的最小边割只能分离G的一个孤立点,则称图G是超边连通的.证明了对所有的有限图G,其变换图G-- 都是极大边连通的,G-- 是超边连通的当且仅当G不同构于K1,2也不同构于K2∪K1.     

信息调度中的一个组合问题

研究了多用户信息服务中的实时调度问题,在基于双向扫描调度模型的基础上使用组合分析技术,对使用扫描算法进行调度时造成的服务延迟这一组合问题进行定量分析,推导出了计算延迟的递推公式.数值计算表明平均延迟时间随用户数的增长率近于常数.该公式可用于对双向扫描算法服务性能的评价.