数学中国

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

各密度的平面图的最小完全同态不同——四色猜测的又一种证明方法

[复制链接]
发表于 2015-5-11 14:33 | 显示全部楼层 |阅读模式

各密度的平面图的最小完全同态不同
——四色猜测的又一种证明方法
雷  明
(二○一五年五月十一日)

1、任何图都有一个顶点数最小的完全同态,且其亏格绝不会大于原图的亏格。这就是说平面图的最小完全同态的亏格一定仍然是0,也即平面图的完全同态也一定是平面图。完全同态也是一个完全图,而是平面图的完全图只有K1,K2,K3,K4四种,其色数分别是1,2,3,4,均不大于4。
2、通过对图的同化运算的研究,知道图的最小完全同态的顶点数不会小于图的密度,也不会大于图的密度的一倍半。图的最小完全同态顶点数比其密度的增大,主要是因为图中有不可同化道路所引起的,因为该道路中总有一个顶点是同化不到最大团中去的。比如一个5—轮,其最大团是K3,5—轮同化的最后结果总是一个顶点数比K3顶点数多1 的K4。这是因为轮沿顶点数大于等5 的奇轮中的每一个K3团外的其他顶点,对于该K3团来说就是一条不可同化道路,其中一定有一个顶点不可能同化到该K3团中去。
3、对于一个最大团来说,若有多条不可同化道路,且它们之间又构成了联时,就有与不可同化道路条数相同数目的顶点同化不到最大团中去。但这个不可同化道路的条数是受一定约束的。即受联中的最大团的顶点数不能大于图本身最大团的顶点数的约束。该联中的最大团的顶点数是构成它的不可同化道路条数的2倍,所以不可同化道路的最大条数是不能大于图的密度的一半的。用S表示不可同化道路的条数,用ω表示图的密度,则有S≤ω/2。
4、一个平面图的最小完全同态的顶点数无论是多少,但它一定是不能大于4 的,因为这个完全同态也是一个平面图,如果其顶点数大于4,则该完全同态就成为一个非平面图了。最小完全同态的顶点数是由图的密度与构成联的不可同化道路的条数之和构成的,所以也有ω+S≤4,即S≤4-ω的结论。
5、可以看出满足S≤ω/2和S≤4-ω二者中S的较小值即是各密度条件下的平面图中最大可能的不可同化道路的条数。可以看出,当图的密度ω=1和4 时,不可同化道路的条数S=0,即不可能有不可同化道路;当ω=2和3时,S≤1,即最大可能的不可同化道路只有一条。
6、因为图的色数就等于其最小完全同态的顶点数,所以,密度为1 的平面图K1的色数为1;密度为2的平面图的色数最大为3;密度为3的平面图的色数最大为4;密度为4的平面图的色数最大仍为4;都没有大于4。这也就证明了四色猜测是正确的。

雷  明
二○一五年五月十一日于长安

注:本文已于二○一五年五月士日在《中国博士网》上发表过,网址是:
您需要登录后才可以回帖 登录 | 注册

本版积分规则

LaTEX预览输入 教程 符号库 加行内标签 加行间标签 
对应的 LaTEX 效果:

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

GMT+8, 2025-7-13 00:27 , Processed in 0.113373 second(s), 15 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代码输入: