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

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

平面图的Alcuin数

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

最大度为5的图的Alcuin数

1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等人把这一问题推广到任意的"冲突图"G=(V,E)上,考虑了一类情况更一般的运输计划问题.现在监管者欲运输V中的所有"物品/点"渡河,这里V的两个点邻接当且仅当这两个点为冲突点.冲突点是指不能在无人监管的情况下留在一起的点.特别地,Alcuin渡河问题可转化成"冲突路"P_3上是否存在可行运输方案问题.图G的Alcuin数是指图G具有可行运输方案(即把V的点代表的"物品"全部运到河对岸)时船的最小容量.最大度为5且覆盖数至少为5的图和最大度Δ(G)≤4且覆盖数不小于Δ(G)-1的图的Alcuin数已经被确定.本文给出最大度为4且覆盖数不超过2和最大度为5且覆盖数不超过4的图的Alcuin数.至此,最大度不超过5的图的Alcuin数被完全确定.

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

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