科学网 › 标签 › 图表示方法

标签: 图表示方法

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

答网友顶点覆盖的子句消去法: 热度 1 accsys 2017-1-23 12:59; 答网友顶点覆盖的子句消去法姜咏江图论中的顶点覆盖问题是说，给定一个 N 个点 M 条边的无向图 G （点的编号从 1 至 N ），问是否存在一个不超过 K 个点的集合 S ，使得 G 中的每条边都至少有一个点在集合 S 中。这实际上是求最小顶点覆盖问题。本文介绍如何用子句消去法来来求解图论中的顶点覆盖问题。 1. 图的 0 和 1 句表示将图中本顶点用 1 表示，与其关联顶点用 0 表示，就是图的 0 和 1 子句表示法。图 1 的 0 和 1 表达形式如表 1 所示。因为这个求解方法近似于本人发明的子句消去法，所以也将表 1 中的每一行叫做子句。图 1 哈密顿图表 1 哈密顿图子句表示 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 deg 1 0 0 0 3 0 1 0 0 3 0 1 0 0 3 0 1 0 0 3 0 0 1 0 3 0 1 0 0 3 0 1 0 0 3 0 0 1 0 3 0 1 0 0 3 0 0 1 0 3 0 1 0 0 3 0 0 1 0 3 0 1 0 0 3 0 0 1 0 3 0 0 1 0 3 0 1 0 0 3 0 0 1 0 3 0 0 1 0 3 0 0 1 0 3 0 0 0 1 3 2. 顶点覆盖的子句消去法用 0 和 1 表示的图，要确定最小顶点覆盖的基本规则是：不分图，叶单枝优先，否则选择得到多叶单枝优先，得不到单枝，关联度由高到低。表 2 哈密顿图顶点覆盖 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 deg 1 0 0 0 0 0 1 0 0 0 0 1 0 0 3 0 1 0 0 2 0 0 1 0 0 0 1 0 0 3 0 1 0 0 0 0 0 1 0 2 0 1 0 0 0 0 0 1 0 0 0 1 0 0 2 0 0 1 0 0 0 1 0 0 3 0 0 1 0 0 0 0 1 0 2 0 1 0 0 0 0 0 1 0 2 0 0 1 0 3 0 0 1 0 0 0 0 0 1 2 最小顶点覆盖集为｛x1,x3,x4,x6,x8,x10,x11,x13,x15,x17,x18,x20｝。 2017-1-23; 个人分类: P/NP问题|3119 次阅读|2 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 图表示方法

相关帖子

相关日志

关闭安全验证