覆盖数不超过3的图上渡河问题

1000多年前,英国著名学者Alcuin曾提出一个古老的渡河问题,即狼、羊和卷心菜的渡河问题。2006年,Prisner把该问题推广到任意的冲突图上,考虑了一类情况更一般的渡河运输问题。所谓冲突图是指一个图G=(V,E),这里V代表某些物品的集合,V中的两个点有边连结当且仅当这两个点是冲突的,即在无人监管的情况下不允许留在一起的点。图G=(V,E)的一个可行运输方案是指在保证不发生任何冲突的前提下,把V的点所代表的物品全部摆渡到河对岸的一个运输方案。图G的Alcuin数定义为它存在可行运输方案时所需船的最小容量。本文讨论了覆盖数不超过3的连通图的Alcuin数,给出了该类图Alcuin数的完全刻画。

River Crossing Problem on Graphs with Cover Number at Most Three

More than 1000 years ago, Alcuin of York proposed a classical puzzle involving a wolf, a goat and a bunch of cabbages that needed to be ferried across a river using a boat that only had enough room for one of them. In 2006, Prisner considered a transportation planning problem that generalizes Alcuin’s river crossing problem to scenarios with arbitrary conflict graphs. In a conflict graph G=(V,E), two vertices (items) of V are connected by an edge in E if and only if they are conflicting, and thus they cannot be left together without human supervision. A feasible schedule on a graphG=(V,E) is a plan that all items of V can be ferried across a river unhurt. The Alcuin number of G is the smallest possible capacity of a boat for which the graph G possesses a feasible schedule. In this paper we investigate the Alcuin number of connected graphs with cover number at most three and give a complete characterization on the Alcuin number for the graphs.