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

摘要

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