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

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