数学中国

用户名  找回密码
 注册
帖子
热搜: 活动 交友 discuz
查看: 3312|回复: 3

改进肯泊的调色法

[复制链接]
发表于 2012-3-4 12:13 | 显示全部楼层 |阅读模式
通过学习雷明连续发表之42,他的“一个顶点是一条特殊的链”的思想。本人对肯泊关于四色问题的证明有了新的改进考虑。
  思路:不在两次交换不连通的二色链!它的弊端是别人利用这些交换的点制造矛盾。而是专致于一次交换或关注连通的二色链。
证明:如果一个顶点v与五个其它用四种颜色着色的点邻接,那么总能多出诸颜色之一用来给v着色(摘自【图论的例和反例】p10).图中数字1、2、3、4、5表示五个邻接点,它们之间的短线代表两点相邻;括号内的字母r 、b 、y、 g分别代表红、蓝、黄、绿四色。
/-----------------\
|                 |
5(y)----1(r)-----2(b)-\
|                 |    0
|       v         |    |
|                 |    |
4(g)--------------3(r) |
|                      |
\----------------------/
  肯泊关于四色问题的证明在【数学证明】一书中有介绍,我认为是诸多专著中最贴切的一种。肯泊证明的实质是调色----在用除待着色顶点以外的其他所有顶点已用过的四种颜色来调色。这种方法具有深远的的意义。为什么这么说,大家猜他怎么不用归纳法?这是受当年图论的知识的局限,还没有作为归纳法所需要的能从k传递到 (k+1)的引理(现在不一样了)!
就是在图论知识丰富的今天,我们照样可以用肯泊的调色法。特别是当他的证明遇到希伍德反例图的冲击后,他的调色方法仍可发挥作用!
  观察图中的二色链:2(b)至4(g)及2(b)至5(y)。1)如果有一条二色链是不连通的,则立即可调出一对同色;与原有的一对同色及另一单色使五邻点构成三色,可空出一色給待着色顶点。2)如果这两条中有一条是连通的,则可不必去看另一条的情况。在连通的这条链上,从某个端点起的第一条边上取(重新找)一点,着上与边的端点(如b、g)不同的第三色,然后将这个端点的颜色(如b)调为另一个端点的颜色-----重新制造出一对同色(如gg)!最后,使五邻点着三色(如r、g、y),空出四色中的一色(如b)给待着色顶点。


解读Kempe的证明㈣:Heawood反例  (2011-05-03 10:37:01)[删除]
标签:  转载  
原文地址:解读Kempe的证明㈣:Heawood反例作者:平常心
    1890年,P.J.Heawood举出一个反例(见图4),说明Kempe证明平面图不含结构R的方法并非总是对的。





以图4(1)Heawood反例图为例,其中的2(b)至4(g)链为蓝、绿二色链,路线是:2--9--15--4;在该链上从端点2(b)起的第一条边(2--9)上取一点并着与b和g皆不同的第三色---r色,随即将端点2的b色改为g色,只有这小小改动,就达到u的五邻点有两对g两对 r及一个y色,共计三着色的调色目的。从而待着色点u可着上b色!
  读者感兴趣可接着练习:1)从以4(g)为端点的第一条边上取点做起......,最后使u着g色;2)同样道理,也可在另一二色链2(b)至5(y)做两种练习。
  另外雷明连续发表之42的第4部分“一个与五个顶点相邻的待着色顶点的着色实例”中的许多图都可作为练习用。
  
  

   

   


   

文字
发表于 2012-3-5 14:38 | 显示全部楼层

改进肯泊的调色法

朋友,你这个“改进”实际上是错的。你在b—g链上的某条边中增加一个顶点,着r色,然后把顶点2 的b改着成了g色,似乎是空出了b色,但你的前提是“在b—g链上的某条边中增加一个顶点”,并着r色,你没有想一想,你这个“着r色的顶点”如同几何证明中所作的辅助线一样,它并不是原图中的顶点,还是要去掉的。如果去掉了该顶点后,不就又产生了两个相邻顶点同着上了g色吗,不等于还没有完成着色任务吗。你可以按你的方法,在你所引用的赫渥特图上去作一作。雷明,2012,3,5,
发表于 2012-3-5 14:55 | 显示全部楼层

改进肯泊的调色法

后加的那个点及所着的颜色就不去掉了!这就是改进的所在。因为这样做并没有减少图的着色数。
 楼主| 发表于 2012-3-5 19:47 | 显示全部楼层

改进肯泊的调色法

因为文章中的图被删掉,有关心的网友请到新浪网去查看。[br][br]-=-=-=-=- 以下内容由 刘福 时添加 -=-=-=-=-
该文是借鉴雷明对希伍德反例图的研究,他在解决两个连通的交叉链时使用了一个能够不交换到底的办法----将这个交叉点是为特殊的链,进行兰红(b、r)交换破换连通性,然后在交换----达到5邻点的四着色转变为5邻点地三着色!
  我现在利用这一思想,研究出在边上加点(也可以理解为辅助点法)并着上第三色,可直接把原来链上的端点调为一对同色。
  这样,加上原图就有的另一对同色,还有一个单色,5 邻点成为三色之目的达到。
  只动用一、二个点,非常便捷。请网友检验,并提出宝贵意见!
您需要登录后才可以回帖 登录 | 注册

本版积分规则

LaTEX棰勮杈撳叆銆€鏁欑▼銆€绗﹀彿搴�銆€鍔犺鍐呮爣绛�銆€鍔犺闂存爣绛�銆€
瀵瑰簲鐨� LaTEX 鏁堟灉锛�

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2025-7-6 10:33 , Processed in 0.114962 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表
\frac{\square}{\square}\sqrt{\square}\square_{\baguet}^{\baguet}\overarc{\square}\ \dot{\baguet}\left(\square\right)\binom{\square}{\square}\begin{cases}\square\\\square\end{cases}\ \begin{bmatrix}\square&\square\\\square&\square\end{bmatrix}\to\Rightarrow\mapsto\alpha\ \theta\ \pi\times\div\pm\because\angle\ \infty
\frac{\square}{\square}\sqrt{\square}\sqrt[\baguet]{\square}\square_{\baguet}\square^{\baguet}\square_{\baguet}^{\baguet}\sum_{\baguet}^{\baguet}\prod_{\baguet}^{\baguet}\coprod_{\baguet}^{\baguet}\int_{\baguet}^{\baguet}\lim_{\baguet}\lim_{\baguet}^{\baguet}\bigcup_{\baguet}^{\baguet}\bigcap_{\baguet}^{\baguet}\bigwedge_{\baguet}^{\baguet}\bigvee_{\baguet}^{\baguet}
\underline{\square}\overline{\square}\overrightarrow{\square}\overleftarrow{\square}\overleftrightarrow{\square}\underrightarrow{\square}\underleftarrow{\square}\underleftrightarrow{\square}\dot{\baguet}\hat{\baguet}\vec{\baguet}\tilde{\baguet}
\left(\square\right)\left[\square\right]\left\{\square\right\}\left|\square\right|\left\langle\square\right\rangle\left\lVert\square\right\rVert\left\lfloor\square\right\rfloor\left\lceil\square\right\rceil\binom{\square}{\square}\boxed{\square}
\begin{cases}\square\\\square\end{cases}\begin{matrix}\square&\square\\\square&\square\end{matrix}\begin{pmatrix}\square&\square\\\square&\square\end{pmatrix}\begin{bmatrix}\square&\square\\\square&\square\end{bmatrix}\begin{Bmatrix}\square&\square\\\square&\square\end{Bmatrix}\begin{vmatrix}\square&\square\\\square&\square\end{vmatrix}\begin{Vmatrix}\square&\square\\\square&\square\end{Vmatrix}\begin{array}{l|l}\square&\square\\\hline\square&\square\end{array}
\to\gets\leftrightarrow\nearrow\searrow\downarrow\uparrow\updownarrow\swarrow\nwarrow\Leftarrow\Rightarrow\Leftrightarrow\rightharpoonup\rightharpoondown\impliedby\implies\Longleftrightarrow\leftharpoonup\leftharpoondown\longleftarrow\longrightarrow\longleftrightarrow\Uparrow\Downarrow\Updownarrow\hookleftarrow\hookrightarrow\mapsto
\alpha\beta\gamma\Gamma\delta\Delta\epsilon\varepsilon\zeta\eta\theta\Theta\iota\kappa\varkappa\lambda\Lambda\mu\nu\xi\Xi\pi\Pi\varpi\rho\varrho\sigma\Sigma\tau\upsilon\Upsilon\phi\Phi\varphi\chi\psi\Psi\omega\Omega\digamma\vartheta\varsigma\mathbb{C}\mathbb{H}\mathbb{N}\mathbb{P}\mathbb{Q}\mathbb{R}\mathbb{Z}\Re\Im\aleph\partial\nabla
\times\cdot\ast\div\pm\mp\circ\backslash\oplus\ominus\otimes\odot\bullet\varnothing\neq\equiv\not\equiv\sim\approx\simeq\cong\geq\leq\ll\gg\succ\prec\in\ni\cup\cap\subset\supset\not\subset\not\supset\notin\not\ni\subseteq\supseteq\nsubseteq\nsupseteq\sqsubset\sqsupset\sqsubseteq\sqsupseteq\sqcap\sqcup\wedge\vee\neg\forall\exists\nexists\uplus\bigsqcup\bigodot\bigotimes\bigoplus\biguplus\bigcap\bigcup\bigvee\bigwedge
\because\therefore\angle\parallel\perp\top\nparallel\measuredangle\sphericalangle\diamond\diamondsuit\doteq\propto\infty\bowtie\square\smile\frown\bigtriangledown\triangle\triangleleft\triangleright\bigcirc \wr\amalg\models\preceq\mid\nmid\vdash\dashv\nless\ngtr\ldots\cdots\vdots\ddots\surd\ell\flat\sharp\natural\wp\clubsuit\heartsuit\spadesuit\oint\lfloor\rfloor\lceil\rceil\lbrace\rbrace\lbrack\rbrack\vert\hbar\aleph\dagger\ddagger

MathQuill输入:

Latex代码输入: