数学中国

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

从求图的亏格到四色猜测的证明

[复制链接]
发表于 2015-2-18 12:47 | 显示全部楼层 |阅读模式
从求图的亏格到四色猜测的证明
雷  明
(二○一四年十一月二十四日)

所谓图的亏格就是一个图所能嵌入的曲面的最小亏格。而曲面的亏格则是球面上所接环柄的个数。一个图可以嵌入到不同的多个亏格的曲面之中,即把图画在这些曲面中时,图中在顶点以外再没有边与边相交叉的情况。这些曲面中亏格最小的一个曲面的亏格就是该图的亏格。如果把图画在某亏格的曲面上后,图中出现了在顶点以外有边与边相交叉的情况时,该图就不能嵌入到该亏格的曲面中去。
1、多阶曲面上的图的欧拉公式
已经证明是正确的多阶曲面上的图的欧拉公式是
v+f-e=2+2n                               (1)
式中v、f、e、n分别是图的顶点数、面数、边数和亏格数。多阶曲面上的图的欧拉公式的证明见范益政等翻译的《图论导引》。
把该多阶曲面上的图的欧拉公式变形就可以求出任何图的亏格。
2、若在知道图的顶点数、面数和边数的情况下,可以用
    n=(e-v-f+2)/2                          (2)
求出其亏格。如:可嵌入到亏格是1的曲面上的K7图的v=7,f=14,e=21,代入(2)式得n=(21-7-14+2)/2=1;K5图v=5,f=5,e=10,代入(2)式得n=(10-5-5+2)/2=1;K3,3图v=6,f=3,e=9,代入(2)式得n=(9-6-3+2)/2=1;可嵌入亏格为0的曲面上的K4图的v=4,f=4,e=6,代入(2)式得n=(6-4-4+2)/2=0;K3图的v=3,f=2,e=3,代入(2)式得n=(3-3-2+2)/2=0;5—轮的v=6,f=6,e=10,代入(2)式得n=(10-6-6+2)/2=0;K2图的v=2,f=1,e=1,代入(2)式得n=(1-2-1+2)/2=0; K1图的v=1,f=1,e=0,代入(2)式得n=(0-1-1+2)/2=0;等等。
3、若当知道图的顶点数和面数的情况下,可以用
n≥〔〈1+(e-3v)/6〉〕(v≥3)                 (3)
求出其亏格。式中〈 〉表示其中的数字取绝对值,〔 〕表示其中的数字向上取整。现推导如下:
由于任何图中都存在3f≤2e的关系,把f≤2e/3代入多阶曲面上的图的欧拉公式(1)v+f-e=2+2n中得
    v+2e/3-e≥2-2n
整理并变形得
        n≥(e-3v)/6+1
由于n是正整数,所以不但要取绝对值,还得再向上取整得
        n≥〔〈(e-3v)/6+1〉〕(v≥3)                  (3)
这就是(3)式。现仍以以上几个图为例:K7图的亏格是n≥〔〈(21-3×7)/6+1〉〕=1;K5图的亏格是n≥〔〈(10-3×5)/6+1〉〕=1;K3,3图的亏格n≥〔〈(9-3×6)/6+1〉〕=〔〈-9/6+1〉〕=〔〈-3/2+1〉〕=〔〈-1/2〉〕=〔1/2〕=1。K4图的亏格n≥〔〈(6-3×4)/6+1〉〕=0;K3图的亏格n≥〔〈(3-3×3)/6+1〉〕=0。这都是正确的。唯只有K2图和K1图以及圈、轮、道路或树,按公式(3)计算的亏格却不是0而是1,所以公式是有(v≥3)的条件限制的。如果把公式(3)中的向上取整改成向下取整,则
    n≥<〈(e-3v)/6+1〉>(v≤2)             (3')
式中< >表示其中的数字向下取整。把K2图和K2图的参数代入公式(3')中,则K2图的亏格n≥<〈(1-3×2)/6+1〉>=<〈-5/6+1〉>=<〈1/6〉>=0;K1图的亏格n≥<〈(0-3×1)/6+1〉>=<〈-3/6+1〉>=<〈1/2〉>=0。把圈、轮、道路或树的参数代入(3')中,则其亏格也都是0了。如5—轮的亏格是n≥<〈(10-3×5)/6+1〉>=<〈-5/6+1〉>=<〈1/6〉>=0等。
4、当只知道图的顶点数的情况下,可以用
    n≥〔(v-3)(v-4)/12〕(v≥3)              (4)
求出完全图的亏格。推导如下:
把任意图中顶点与边的关系e≤v(v-1)/2代入以上(3)式中得
    n≥〔(v(v-1)/2-3v)/6+1〕
变形整理后得
        n≥〔(v-3)(v-4)/12〕(v≥3)               (4)
(4)式说明了某完全图的亏格一定是n=〔(v-3)(v-4)/12〕(v≥3),它一定是能够嵌入到亏格为n≥〔(v-3)(v-4)/12〕(v≥3)的曲面上去的。例如K7图的顶点数是v=7,亏格则是n=〔(v-3)(v-4)/12〕=〔(7-3)(7-4)/12〕=〔12/12〕=1,同样K5图的顶点数是v=5,亏格则是n=〔(v-3)(v-4)/12〕=〔(5-3)(5-4)/12〕=〔6/12〕=1,二图均可嵌入亏格大于等于1的曲面上;又如K4图的顶点数是v=4,亏格则是n=〔(v-3)(v-4)/12〕=〔(4-3)(4-4)/12〕=〔0/12〕=0,同样K3图的顶点数是v=3,亏格则是n=〔(v-3)(v-4)/12〕=〔(3-3)(3-4)/12〕=〔0/12〕=0,同样的,二图均是可嵌入亏格大于等于0的曲面上。
     同样的,完全图K2和K2不包括在(4)式中的,若把(4)式向上取整也改为向下取整,则有
        n≥<(v-3)(v-4)/12>(v≤2)            
这时把K2图和K2图的参数代入公式(4')中,两图的亏格都是0。如K2图的亏格是n=<(v-3)(v-4)/12>=<(2-3)(2-4)/12>=<(-1)(-2)/12>=<(-1)(-2)/12>=<2/12>=0
5、三个计算图的亏格的公式的比较
一般的图,除了平面图(亏格为0)能直接看出面数f是多少外,其它的图是无法看出其面数的,而只能看出其顶点数v和边数e。但平面图一般也不需要求其亏格,所以说式(1)是没有多大用处的;式(2)的用处是最大的,可以说对所有的已知其顶点数v与边数e的图,都可以求出其亏格n;而式(3)只是对于完全图有用,但如果知道已知顶点数的图是完全图,那么也就相当于知道其边数了,用公式(2)同样也是可以求出其亏格的。所以说式(2)的用处是最大的。
6、赫渥特地图着色公式的推导与四色猜测的证明
以上的三个公式,分别是一步一步的把f≤2e/3和e≤v(v-1)/2代入到多阶曲面上的图的欧拉公式而得到的,把(4)式在向上取整前的式子变形后就可得到
  v2-7v+12(1-n)≤0
解这个关于顶点数v的一元二次不等式,得正根是
    v≤(7+√(1+48n))/2                     
由于顶点数是正整数,所以该式还得向下取整得
        v≤<(7+√(1+48n))/2>                  (4)
因(4)式是由完全图的亏格公式推导出来的,所以这里的v应是完全图的顶点数。由于图的最小完全同态也是完全图,所以(4)式中的v也应是图的最小完全同态的顶点数。而图的最小完全同态的顶点数就是图的色数,所以又有
        γn≤<(7+√(1+48n))/2>                (5)
这就是赫渥特的地图着色公式(若同时把f≤2e/3和e≤v(v-1)/2直接代入到多阶曲面上的图的欧拉公式中也可以直接得到这个公式)。(5)式中当n=0时,γn≤4,这也就证明了四色猜测是正确的。
    7、赫渥特地图着色公式的又一推导方法
一个可以嵌入到亏格为n的曲面上的图的边数与顶点数的关系是
e≤3v+6(n-1),完全图的边与顶点数的关系是e=v(v-1)/2,该二者的关系又是
        v(v-1)/2≤3v+6(n-1)
整理并解出v得到
         v≤<(7+√(1+48n))/2>                 (4)

        γn≤<(7+√(1+48n))/2>                 (5)
这与上面的(4)式与(5)式是完全相同的。这个方法实质上与上面的方法也是相同的,因为e≤3v-6(n-1)本身就是把f≤2e/3代入到多阶曲面上的图的欧拉公式后所得的结果。

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

注:该文已于二○一四年十一月二十五日于《中国博士网》上发表过。


您需要登录后才可以回帖 登录 | 注册

本版积分规则

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

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

GMT+8, 2025-7-9 14:31 , Processed in 0.077988 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代码输入: