超图的Alcuin数与其横贯数的关系

1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等考虑了一般"冲突图"上的渡河问题.将这一问题推广到超图H=(V,ε)上,考虑一类情况更一般的运输计划问题.现在监管者欲运输超图中的所有点(代表"items")渡河,这里V的点子集形成超边当且仅当这些点代表的"items"在无人监管的情况下不能留在一起.超图H的Alcuin数是指超图H具有可行运输方案(即把V的点代表的"items"全部运到河对岸)时船的最小容量.给出了r-一致完全二部超图和它的伴随超图,以及r-一致超图的Alcuin数,同时证明了判断r-一致超图是否为小船图是NP-困难的.

最大度为5的图的Alcuin数

1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等人把这一问题推广到任意的"冲突图"G=(V,E)上,考虑了一类情况更一般的运输计划问题.现在监管者欲运输V中的所有"物品/点"渡河,这里V的两个点邻接当且仅当这两个点为冲突点.冲突点是指不能在无人监管的情况下留在一起的点.特别地,Alcuin渡河问题可转化成"冲突路"P_3上是否存在可行运输方案问题.图G的Alcuin数是指图G具有可行运输方案(即把V的点代表的"物品"全部运到河对岸)时船的最小容量.最大度为5且覆盖数至少为5的图和最大度Δ(G)≤4且覆盖数不小于Δ(G)-1的图的Alcuin数已经被确定.本文给出最大度为4且覆盖数不超过2和最大度为5且覆盖数不超过4的图的Alcuin数.至此,最大度不超过5的图的Alcuin数被完全确定.