English

运筹学学报 ›› 2014, Vol. 18 ›› Issue (3): 104-110.

• 运筹学 • 上一篇    下一篇

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

单而芳1,2,*, 孔鹭2   

  1. 1. 上海大学管理学院, 上海 200444, 2. 上海大学数学系, 上海 200444
  • 出版日期:2014-09-15 发布日期:2014-09-15
  • 通讯作者: 单而芳 E-mail:efshan@shu.edu.cn
  • 基金资助:

    国家自然科学基金 (No. 11171207)

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

SHAN Erfang1,2,*, KONG Lu2   

  1. 1. School of Management, Shanghai University,  Shanghai 200444, China, 2. Department of Mathematics, Shanghai University, Shanghai 200444, China
  • Online:2014-09-15 Published:2014-09-15

PDF

907

被引次数

1

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

关键词: Alcuin数, 横贯, 独立集

Abstract: 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,\mathcal{E})$. Now the man has to transport a set $V$ of items/vertices across the river. Some items of $V$ formed  a hyperedge in $\mathcal{E}$ 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.

Key words: Alcuin number, transversal set, independent set

中图分类号: