数学中国

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

连续发表(之五十七(四))

[复制链接]
发表于 2012-1-2 18:04 | 显示全部楼层 |阅读模式
连续发表(之五十七(四)):《四色问题与欧拉公式》一书的第五章《四色猜测与欧拉公式》中的第52节《图的亏格》的第四部分(请打开以下DOS文件查看)。


以上DOS文件对表5—1的分析改动如下:

(二)上表(表5—1)“曲面亏格n及其可嵌入图的最大色数γn、最大密度ω最大及最大色数下图的最小密度ω最小对照表”中数据分布的规律如下:
从上表中的数据可以看出:
(1)曲面的亏格n小于等于1时,用赫渥特公式计算出来的最大色数γn都是整数。如n=0时,γ0=4;n=1时,γ1=7。
(2)曲面的亏格n大于等于2时,用赫渥特公式计算出来的最大色数γn都是非整数,都要向下取整。如n=2时,γ2=8.4244,向下取整后才是γ2=8,等等。
(3)曲面的亏格小于等于1时,曲面的亏格数n每增加1,所对应的最大色数γn的增加是大于1的。如曲面的亏格n=0时,γ0中有四个元素,即γ0={1,2,3,4},说明n=0时的曲面所能嵌入的图的色数有四种,都是小于等于4的;当曲面的亏格n=1时,γ1中有七个元素,即γ0={1,2,3,4,5,6,7},说明n=1时的曲面所能嵌入的图的色数有七种,都是小于等于7的;当曲面的亏格由n=0增到n=1时,γ1-γ0中就只有三个元素,即γ1-γ0={1,2,3,4,5,6,7}-{1,2,3,4}={5,6,7},其中的元素个数是3,说明曲面的亏格由n=0增到n=1时,曲面所能嵌入的图的色数增加了3种,是大于1的,但每一种的具体值也都小于等于7。注意,我们可不能把{5,6,7}理解为能嵌入到n=1曲面上的图的色数就只有这三种,而n=1的图的色数应是{1,2,3,4,5,6,7},因为前面第29节《平面图顶点着色色数的界》一节中的图3—9和图3—10的几个图,其亏格都是n=1,但其色数却有的是γ=4,有的是γ=5。
(4)曲面的亏格大于等于1时,曲面的亏格数n每增加1,所对应的最大色数γn的增加是小于等于1的。如曲面的亏格由n=9增到n=10时,γ10-γ9中只有一个元素,即γ10-γ9={1,2,3,4,5,6,7,8,9,10,11,12,13,14}-{1,2,3,4,5,6,7,8,9,10,11,12,13}={14},说明曲面的亏格由n=9增到n=10时,曲面所能嵌入的图的色数只增加了1种;而曲面的亏格由n=8增到n=9时,γ9-γ8={1,2,3,4,5,6,7,8,9,10,11,12,13}-{1,2,3,4,5,6,7,8,9,10,11,12,13}={ }(该集中没有任何元素)= ,是一个空集,说明曲面的亏格由n=8增到n格9时,曲面所能嵌入的图的最大色数数目没有增加。
(5)不同亏格的曲面所能嵌入其中的图的最大密度ω最大、最小密度ω最小等参数也有与上面在不同亏格的曲面所对应的最大色数γn有同样的变化规律,即n≤1时,ω最大和ω最小等参数的增加都是大于1的,n≥1时,ω最大和ω最小等参数的增加则都是小于等于1的。
(6)当曲面的亏格n小于等于5时,与不同亏格的曲面所对应的最大色数γn和图的最大密度ω最大等参数都有一对一的对应关系;而当曲面的亏格大于等于6时,其对应关系既存在着一对一的对应关系,却也存在着多对一的对应关系,这说明几个不同亏格的曲面所能嵌入的图的最大色数γn和图的最大密度ω最大等参数是相同的。
(7)表中还可以看出在曲面的亏格n≤17时,其曲面的亏格n的值是小于等于其所对应的最大色数γn和最大密度ω最大的,而在曲面的亏格n≥18时,其曲面的亏格n的值却是大于等于其所对应的最大色数γn和最大密度ω最大的;同样还有在曲面的亏格n≤9时,可嵌入某亏格曲面的图的最小密度ω最小的值是大于等于曲面的亏格数n的,而在曲面的亏格n≥10时,可嵌入某亏格曲面的图的最小密度ω最小的值却是小于等于曲面的亏格数n的。
(8)从前面第29节《平面图顶点着色色数的界》一节中的图3—9和图3—10的几个图,可以看出,明明是非平面的图同化的最终结果却是顶点数不大于4 的平面完全图,其亏格由原来的n=1变成了n=0(注意,虽然图的亏格发生了变化,但其色数并没有变,而则是γ=4)。所以说在表(5—1)中尽管存在着不同的密度的图有相同的色数值,也即他们同化的最终结果可以是顶点数相同的完全图,但不能说明这些图本身的亏格都是相同的。表(5—1)中的“曲面的亏格(n)”栏中所列亏数,只能理解为图同化的最终结果的亏格数,也即是完全图的亏格数。所以在表(5—1)最下边的“各种格(n)的曲面中,在相同色数(γ)情况下,由于图的密度(ω)的不同,图中某个最大团外有联存在的不可同化道路的可能条数(S)”栏中,图的密度与不可同化道路条数之和,即ω+S正好就是表最上部某亏格曲面下“可嵌入的图的最大公数(γn)”和“可嵌入的图的最大密度(ω大)”。从这里可以明显看出,若给出一个已知亏格的图,其色数(或其最小完全同态的顶点数)并不一定是该亏格下方所对应的色数。
如在表(5—1)中亏格n=6和n=7所对应的最大色数都是γn=12,表中可以看出,在这里除了完全图K12的色数是γω=12=12,以及密度ω=12但图中无论那个最大团外都不含有不可同化道路(即S=0)的图的色数是γω=12=12外,还有ω=8和S=4的图的色数是γω=8=12,还有ω=9和S=3的图的色数是γω=9=12,还有ω=10和S=2的图的色数是γω=10=12,还有ω=11和S=1的图的色数是γω=11=12。这些图ω+S的值都是相同的,即其色数都是相同的(在表的最下部已标出了相同最大色数下的ω与S之值的对照表)。但这些图的亏格却是不同的。只能说这些图同化的最终结果都是亏格为n=6的完全图K12。这些图的亏格分别是多少,等到下节学了多阶曲面上的欧拉公式和图所能嵌入的曲面的最小亏格以后才可通过计算求出。

    图5—6的顶点v=11,边e=45,密度ω=5,不可同化道路的条数S=2,色数γ=ω+S=5+2=7,各顶点的度都d≥8,其亏格并不是色数栏所对应的n=1,而是n=6;而图5—7的顶点v=10,边e=35,密度ω=4,不可同化道路的条数S=2,色数γ=ω+S=4+2=6,各顶点的度都d=7,其亏格并不是色数栏所对应的n=0,而是n=2。
另外,从以上表(5—1)中的规律看,随着图的亏格的增大,图着色的色数的增加幅度是越来越小的,但却没有渐近线。当亏格n趋于无穷大 时,γn也趋于无穷大。
(以下接DOS文件中的小标题 4)
您需要登录后才可以回帖 登录 | 注册

本版积分规则

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

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

GMT+8, 2025-7-10 06:48 , Processed in 0.072804 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代码输入: