Abstract: 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.

Key words: planar graph, alcuin number, cover set, independent set, ferry problem

摘要： 广义渡河问题是一类重要的组合优化问题,它是经典的狼-羊-卷心菜游戏的推广。冲突图是一个图,这个图的任意两个点所代表的物品不相容时(例如,狼和羊代表的物品不相容),则在这两个点之间连结一条边。渡河覆盖问题的目的是确定冲突图全部点所代表的物品从河的一岸安全地摆渡到河的对岸时所需船的最小容量,而冲突图的Alcuin数定义这个最小容量。本文讨论了平面图的Alcuin数, 给出了该类图Alcuin数的完全刻画。

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