平面图的Alcuin数  

The Alcuin Number of Planar Graphs

作　　者：单而芳[1] 朱恺丽 SHAN Er-fang;ZHU Kai-li(School of Management,Shanghai University,Shanghai 200444,China;Departmrnt of Mathematics,Shanghai University,Shanghai 200444,China)

机构地区：[1]上海大学管理学院,上海200444 [2]上海大学数学系,上海200444

出　　处：《运筹与管理》2019年第11期112-115,共4页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(11971298)

摘　　要：广义渡河问题是一类重要的组合优化问题,它是经典的狼-羊-卷心菜游戏的推广。冲突图是一个图,这个图的任意两个点所代表的物品不相容时(例如,狼和羊代表的物品不相容),则在这两个点之间连结一条边。渡河覆盖问题的目的是确定冲突图全部点所代表的物品从河的一岸安全地摆渡到河的对岸时所需船的最小容量,而冲突图的Alcuin数定义这个最小容量。本文讨论了平面图的Alcuin数,给出了该类图Alcuin数的完全刻画。The generalized river crossing problem is a class of combinatorial optimization problems and it may be viewed as generalizations of the classical wolf-goat-cabbage puzzle. A conflict graph is a graph in which two vertices are adjacent if and only if they are incompatile(for example, a wolf and a goat are incompatile). The river crossing problem is to determine the minimum required boat capacity to safely transport items represented by a conflict graph. The Alcuin number of a conflict graph is defined as the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper we investigate the Alcuin number of planar graphs and give a complete characterization on the Alcuin number.

关 键 词：平面图 Alcuin数 覆盖集 独立集 渡河问题 

分 类 号：O157.5[理学—数学]