【Planar graph and map 3-colorability reduce to one another】时人不识凌云木,直待凌云始道高。这篇文章主要讲述Planar graph and map 3-colorability reduce to one another相关的知识,希望能为你提供帮助。
目录
- 1.1 证明
-
2.1 Planar 3-colorability is NP-complete
- 2.1.1 平面3着色特点
- 2.1.2 构造方法
Theorem. PLANAR-3-COLOR ? P PLANAR-MAP-3-COLOR.
(一个平面三着色问题是可以跟一个平面图三着色问题相互规约的!)
1.1 证明
文章图片
2.1 Planar 3-colorability is NP-complete证明:1.首先证明它是一个NP问题很好证明只要我们在多项式时间内找到其中一个解就行了。
2.我们可以将3着色问题规约到平面3着色问题。
3.给你任意一个3着色实例G我们都能构造一个平面3着色的实例,如果这个平面是可以被3着色的,那么G就是可2着色的。
2.1.1 平面3着色特点
每一个平面如果可以被3着色那么相反的角具有相同的颜色,依次可以推出其他颜色。
Lemma. W is a planar graph such that:
?In any 3-coloring of W, opposite corners have the same color.
?Any assignment of colors to the corners in which opposite corners have
the same color extends to a 3-coloring of W.
Pf. The only 3-colorings (modulo permutations) of W are shown below. ?
文章图片
2.1.2 构造方法
Construction. Given instance G of 3-COLOR, draw G in plane, letting edges
cross. Form planar G? by replacing each edge crossing with planar gadget W.
Lemma. G is 3-colorable iff G? is 3-colorable.
?In any 3-coloring of W, a ≠ a? and b ≠ b?.
?If a ≠ a? and b ≠ b? then can extend to a 3-coloring of W.
文章图片
文章图片
推荐阅读
- 每日开源 | 一个 Java 接口快速开发框架(magic-api)
- XML – E4X概述
- Satisfiability
- 消息列队基础
- 滤镜也能复制粘贴(视频编辑服务专属滤镜一键搞定)
- P VS NP
- Linux之tar命令
- Kubernetes Cronjob的第一次使用
- 9DNS主从和iptables使用