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

The Alcuin number of a hypergraph and its connections to the transversal number

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

More than 1000 years ago, Alcuin proposed a classical puzzle involving a wolf, a goat and a bunch of cabbages. Recently, Prisner and Csorba et al. considered this transportation planning problem that generalizes Alcuin＇s river crossing problem to arbitrary conflict graphs G. In this paper we generalize this problem to arbitrary hypergraphs H = （V, ε）. Now the man has to transport a set V of items/vertices across the river. Some items of V formed a hyperedge in g iff they are conflicting and thus cannot be left together without human supervision. The Alcuin number of a conflict hypergraph is the smallest capacity of a boat for which the hypergraph possesses a feasible schedule. In this paper we give the Alcuin numbers of complete bipartite r-uniform hypergraphs and their adjoint hypergraphs, r-uniform hypergraphs. We also prove that it＇s NP-hard to decide whether a given r-uniform hypergraph is a small boat hypergraph.