平面图的Alcuin数

论文摘要

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

论文目录

• 0 引言
• 1 预备知识
• 2 平面图的Alcuin数

文章来源

类型: 期刊论文

作者: 单而芳,朱恺丽

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

来源: 运筹与管理 2019年11期

年度: 2019

分类: 基础科学

专业: 数学

单位: 上海大学管理学院,上海大学数学系

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

分类号: O157.5

页码: 112-115

总页数: 4

文件大小: 1401K

下载量: 29