|
|
楼主 |
发表于 2009-3-22 11:54:30
|
显示全部楼层
若3级胡猜想没有被证明，以下证明大纲为四色定理的手工证明提供了壹条可行途径
任意平面图可以四上色的充分必要条件是任意极大平面图可以四上色。任意极大平面图可以四上色的充分
必要条件是任意素图可以四上色。任意素图可以四上色的充分必要条件是由算法生成的半理想图是素理想图——可叁上色的图。
定义（阶数）：图G（V，E）包含的结点数（即V的元素个数）称为G（V，E）的阶数。
定义（公共邻点）：若结点v1与结点v2存在关联边，则称v1与v2相邻，v1是v2的邻点(v2是v1的邻点)。
若结点v1与结点v2相邻，v1与结点v3相邻，则称v1是v2与v3的公共邻点。
关联=相邻；关联结点=邻点；公共关联结点=公共邻点。
定义（对边、对点）：若边（v1，v2）、（v1，v3）、（v2，v3）存在，则称边（v2，v3）是结点v1
的对边；结点v1是边（v2，v3）的对点。若还存在边（v2，v4）、（v3，v4）,
则称结点v1是结点v4的对点。
定义（导图）：设G（V，E）是无向简单图，若存在图G1（V1，E1）满足：
1.V1包含于V，即V1是V的子集；
2.若边（v1，v2）∈E1,则（v1，v2）∈E，即E1的每条边都在E中；
3.若边（v1，v2）∈E，且v1∈V1，v2∈V1，则（v1，v2）∈E1，即E中两个端点都属
于V1的边必在E1中。
则称G1（V1，E1）是结点集V1在G（V，E）中的导图。特别地，结点集V在G（V，E）中
的导图就是G（V，E）。
定义（素图）：若极大平面图G（V，E）满足：
1.G（V，E）的每个结点的度不小于伍（即G（V，E）的阶数不小于陆）;
2.G（V，E）中任何阶数不小于四的真子图都不是极大平面图。
则称G（V，E）是素图。
定理：设G（V，E）是素图，则有：
1.G（V，E）的阶数不小于12；
2.G（V，E）中任意两个关联（相邻）结点有且只有两个公共的邻点；
3.任意v∈V,v的所有对边构成壹条简单回路。
证明：1.设G（V，E）为n阶素图，则G（V，E）有2（n-2）个域（面），3(n-2）条边。易知G的所
有结点的度数之和为6（n-2），有G（V，E）的每个结点的度不小于五，于是6（n-2）≥5n，
即n≥12 。
2.显然。
3.显然。
定义（半理想图）：设G（V，E）是素图，若G（V，E）存在子图G1（V1，E1）与结点集V2满足：
1.V的每个结点要么属于V1，要么属于V2，即V=V1∪V2；
2.V1与V2没有公共结点，即V1∩V2=Φ；
3.V2中的任意两个结点在G（V，E）中不相邻；
4.V1中的每个结点至少与V2的壹个结点相邻。
则称G1（V1，E1）是G（V，E）的半理想图，V2是对应于G1（V1，E1）的去点集。
V2的每个结点称为去点，V1的每个结点称为留点。G（V，E）中去点的关联边称为
去边，而两个端点都是留点的边（即G1（V1，E1）中的每条边）称为留边。
定理：G1（V1，E1）≠Φ，且G1（V1，E1）是连通图；V2≠Φ。
定义（环）：设G（V，E）是素图，G1（V1，E1）是G（V，E）的半理想图，V2是对应于G1（V1，E1）
的去点集，若G1（V1，E1）中存在两条简单回路G3（V3，E3）与G4（V4，E4），满足：
1.V3∩V4=Φ,即V3与V4没有公共结点；
2. E3的每条边都存在属于V4的对点；
3. E4的每条边都存在属于V3的对点。
则称图(V3∪V4,E3∪E4∪{(vx,xy)|vx∈V3,vy∈V4})为环。
显然,环是连通图。
定义（链）：设G（V，E）是素图，G1（V1，E1）是G（V，E）的半理想图，V2是对应于G1（V1，E1）
的去点集，若G1（V1，E1）中存在简单回路G3（V3，E3）与道路G4（V4，E4），满足：
1.V3∩V4=Φ,即V3与V4没有公共结点；
2. E3的每条边都存在属于V4的对点；
3. E4的每条边都存在属于V3的对点。
则称图(V3∪V4,E3∪E4∪{(vx,xy)|vx∈V3,vy∈V4})为链。
显然,链是连通图。且有环必有链。
定义（平凡细胞）：设G（V，E）是素图，G1（V1，E1）是G（V，E）的半理想图，V2是对应于G1（V1
，E1）的去点集，V3是V1的非空子集，V3在素图中的导图(也是V3在G1（V1，E1）中
的导图)为G3（V3，E3 ），若有：
1.G3（V3，E3）存在K3（即G3（V3，E3）中存在两两相邻的叁个结点）且是连通图；
2.G3（V3，E3）的任何子图都不是环；
3.任意结点v∈V3，v在G3（V3，E3）的所有邻点在素图中的导图(也是在G3中导图)是
壹条道路。
4.V3中的任何两个相邻结点都不存在属于V1但不属于V3的公共邻点。
则称G3（V3，E3）是平凡细胞。
定理:平凡细胞的任意两个相邻结点有属于该细胞的公共邻点(即平凡细胞的每条边都属于该细胞的某个K3).
证:设G3(V3,E3)是平凡细胞,(vx,vy)∈E3,由平凡细胞的定义第叁条知vx在G3中的所有邻点的集合的
导图是壹条道路.设这条道路上vy的壹个邻点为vz,则G3存在(vx,vy),(vx,vz),(vy,vz),即(vx,vy)属于细胞的壹个K3.由(vx,vy)的任意性知平凡细胞的每条边都属于该细胞的某个K3.证毕.
定理:平凡细胞中,每个结点的只属于该细胞的壹个K3的关联边有且只有两条.
证:设vx是平凡细胞的任意壹个结点,由平凡细胞的定义,vx在平凡细胞中的所有邻点的集合的导图是
壹条道路.设这条道路上的结点依次是vy1,......vyλ,λ≥2,则对任意1≤i≤λ-1,边(vx,vyi),(vx,vy(i+1)),(vyi,vy(i+1))构成K3.
显然,若λ≥3,则(vx,vy2),......,(vx,vy(λ-1))都是属于细胞的两个K3的边.从而结点vx在平凡细胞上的只属于该细胞壹个K3的关联边有且只有两条.由vx的任意性知定理成立.证毕.
定理:半理想图的任何两个平凡细胞----若存在不少于两个的平凡细胞----都不存在公共边,即属于两个平凡
细胞的边.
证:显然(由平凡细胞的定义可知).
定义(平凡细胞):设G(V,E)是平面的壹个素图,G(V,E)的任意两条边有交点当且仅当交点是两条边的公共结
点,G1(V1,E1)是素图的半理想图,V2是对应于G1(V1,E1)的去点集,.C(V3,E3')是半理想图的壹条简单回路,平面去掉C有两个连通分支:壹个有界的称为C的内区域,壹个无界的称为C的外区域,这两个区域都以C为边界。C及其内区域的并集称为C的内盘,C及其外区域的并集称为C的外盘。若有:
1.C的内区域不含素图的任何结点(即素图的所有结点都在C的外盘上)。
2.C上每条边在C的外盘上的对点是去点。
3.V3的任意两个结点在C的外盘上相邻当且仅当这两个结点在C上相邻。
则称V3在素图中的导图(也是在半理想图中的导图)G3(V3,E3)为平凡细胞。
平凡细胞的两个定义的等价性的证明:
---->任意e∈C,e在C的外盘上的对点是去点,e在C的内盘上的对点是C上的留点,即e属于某个叁条边都是留边
的K3,且这个K3是V3在的导图的子图,即存在K3。
连通性显然。
G3若存在链,,则C的内区域中有去点,矛盾。故G3不存在链。
设v∈V3,v在G3中的邻点按顺时针方向依次为vx1,......,vxλ,λ≥2.我们只需证明,对任意1≤i≤λ
-1,存在边(vxi,vx(i+1)),从而v在G3中的邻点集在G3中的导图是壹条道路.考虑边(v,vxi),(v,vx(i+1)),在C的内盘上,v在这两条边之间(按顺时针方向)不存在关联边,而素图的每条边都属于K3,则存在边(vxi,vx(i+1))与(v,vxi)、(v,vx(i+1))构成K3,即(vxi,vx(i+1))存在.
若有e∈E3,且e∈E3'.则e在C的外盘上的对点是去点,e在C的内盘上的对点是留点,且该留点是V3中的点
.若e∈V3,但e不属于E3',则e的两个端点是C上两个不相邻的点,由所给定义知这两个点在C的外盘上不相邻,而C的内盘上的素图的点都是C上的点,则e在C的内盘上的两个对点都是留点,且这些留点都属于V3.
<----见下面的定理.
定理:平凡细胞中,由所有只属于该细胞的壹个K3的边构成的图是细胞的生成子图,且该生成子图是壹条简单回
路.
证:平凡细胞的每个结点都有且只有两条只属于该细胞的壹个K3的关联边.于是这些边构成的图有平
凡细胞的所有结点,即是平凡细胞的生成子图.又该生成子图的所有结点的度都为贰,则是若干条简单回路.下面证明,该生成子图就是壹条简单回路.用反证法.
设该生成子图由k条(k≥2)两两之间无公共结点的简单回路C1,......,Ck构成.不妨设
C2,......,Ck都在C1的内区域中.C1及其内区域的并集是C1的内盘,记为D1;C1及其外区域的并集称为C1的外盘.由于C1上的任何壹个结点在平凡细胞中的邻点集的导图是壹条道路,而这条道路的两个端点就是该结点在C1上的两个邻点,则C1上任何两个相邻结点在C1的外盘上的对点是去点,任何两个不相邻的结点在C1的外盘上也不相邻,从而平凡细胞的所有结点与边都在C1的内盘上.
在C1的内盘上,C1的每个结点的邻点集的导图是壹条道路,且C1上任意两个相邻结点有是留点的
公共邻点,从而所有不在C1上但与C1上的结点相邻的结点的集合的导图存在道路,即平凡细胞存在链,矛盾.故定理得证.
定理:平凡细胞可以叁上色.且对平凡细胞的任意壹个K3叁上色后,整个平凡细胞的叁上色方法是唯一的.
证:设平凡细胞是简单回路C的结点集在素图中的导图,平凡细胞所围区域是C的内盘。由平凡细胞的
定义知,平凡细胞的任意两个结点在C的外盘上相邻当且仅当这两个结点在C上相邻.
设(v1,v2)是平凡细胞的任意壹条边.若(v1,v2)是C上的边,则平凡细胞的所有其它边都在
(v1,v2)的某壹侧.
若(v1,v2)不是C上的边,则(v1,v2)把C的内盘----即平凡细胞所围的区域分为两个有界单连通闭
区域,设为Dx,Dy. 则Dx,Dy都至少有叁个属于平凡细胞的结点;都有且只有壹个结点是v1,v2的公共邻点.且对任意不属于{v1,vv2}的vx,vy,vx属于Dx,vy属于Dy,素图中不存在边(vx,vy).即Dx,Dy的非v1,v2的结点分别在边(v1,v2)的两侧.
对平凡细胞的任意壹个K3的结点叁上色,则已上色的结点的的集合的导图所围区域是单连通闭区
域.若平凡细胞只有叁个结点,上色结束.平凡细胞的叁上色方法唯一确定.
若平凡细胞还有没上色的结点,且已上色的结点的集合的导图所围区域是单连通闭区域,设为D1.
则D1的边界必有边属于平凡细胞的两个K3.对D1边界上任何壹条属于平凡细胞的两个K3的边e,e属于这样壹个单连通闭区域Dx x与D1有且只有两个公共结点即e的两个端点;Dx有且只有两个已上色的结点即e的两个端点;Dx的所有没上色的结点都在e的某壹侧,且不与除e的端点以外的其它已上色结点相邻;Dx有且只有壹个结点与e的端点相邻,且这个结点是e的对点.则Dx的属于e的对点的结点可以且只可以上与e的两个端点不同的色.
重复执行上段有限次后,平凡细胞的每个结点都可以上色,且每个结点的上色方法是唯一确定的.证毕.
定义（中细胞、大细胞）：只有叁条边的平凡细胞称为中细胞，不是中细胞的平凡细胞称为大细胞。
定义（小细胞）：设G（V，E）是素图，G1（V1，E1）是G（V，E）的半理想图，V2是对应于G1（V1，E1）的
去点集，若G1（V1，E1）存在结点v，v不属于任何K3（三角域），则称结点v在G1（V1，E1）中的导
图为小细胞。
平凡细胞和小细胞统称细胞。
定理:小细胞与其它细胞不存在公共结点.
证:显然.
定义（细胞的公共结点）：设G（V，E）是素图，G1（V1，E1）是G（V，E）的半理想图，V2是对应于
G1（V1，E1）的去点集，若G1（V1，E1）存在细胞Ax、Ay和结点vi，满足：
vi既是Ax中的结点、又是Ay中的结点，则称vi是细胞Ax与Ay的公共结点。
定义（桥）：设G（V，E）是素图，G1（V1，E1）是G（V，E）的半理想图，V2是对应于G1（V1，E1）的
去点集，若G1（V1，E1）存在细胞Ax、Ay和边（vi，vj），满足：
1.vi是Ax中的结点，但不是Ay中的结点；
2.vj是Ay中的结点，但不是Ax中的结点。
则称边（vi，vj）是细胞Ax与Ay之间的（壹座）桥。
显然，任意中细胞与小细胞最多有壹座桥。
定义（理想图）：设G（V，E）是素图，G1（V1，E1）是G（V，E）的半理想图，V2是对应于G1（V1，E1）
的去点集，若有：
若G1（V1，E1）存在K3，则每个K3属于平凡细胞。
则称G1（V1，E1）为理想图。
定理:设G(V,E)是素图,G1(V1,E1)是G(V,E)的理想图,V2是对应于G1(V1,E1)的去点集.则G1(V1,E1)的每条边(
留边)要么属于平凡细胞,要么是两个细胞之间的壹座桥.
证:设边e∈E1.若e属于G1的某个K3,则由理想图的定义知,e属于平凡细胞.
若e不属于任何K3,则e不属于任何平凡细胞.而退化细胞没有边,故e不属于任何细胞.若e的某个端
点属于G1的某个K3,则这个端点是某个平凡细胞的结点;若e的某个端的的所有关联边都不属于G1的任何K3,则这个端点是小细胞的结点----即e的每个端点都属于细胞,从而e是两个细胞之间的桥.
定义（组织）： 设G（V，E）是素图，G1（V1，E1）是G（V，E）的理想图，V2是对应于G1（V1，E1）
的去点集，若G1（V1，E1）存在k个大细胞A1，、、、、、、，Ak，满足：
1.若k=1，则任何与A1有公共结点的细胞（显然必是平凡细胞）都是中细胞；
2.若k≥2，则对任意1≤i≤k，存在1≤j≤k，j≠i，使得Aj与Ai有公共结点，而
与Ai有公共结点但不属于集合{A1，、、、、、、，Ak}的细胞都是中细胞。
则称A1∪......∪Ak是组织。
定义（恶邻）：设G（V，E）是素图，G1（V1，E1）是G（V，E）的理想图，V2是对应于G1（V1，E1）
的去点集，若G1（V1，E1）存在组织A和细胞b，b不属于A，且b与A有至少两座桥，或者既有
公共结点又有桥，则称b是A的恶邻。
定义(正规组织) :若组织中任何两个大细胞最多有壹个公共结点,有公共结点时不存在桥,没有公共结点时最
多有壹座桥,且该桥是组织中某个细胞的边----称这个组织为正规组织,或者说这个组织是正规的。
定义（素理想图）：若理想图G1（V1，E1）满足：
1.任意组织都是正规组织。
2.对任意组织A，若A存在恶邻，则A的任意恶邻与A的公共结点、桥的属于组织的端点最多
在组织的两个大细胞上；且在两个大细胞上时这两个大细胞有在组织中有公共结点。
3.任意组织的任意两个恶邻既无公共结点也不存在桥。
4.任意叁个细胞至少有两种方法3上色。
则称G1（V1，E1）是素理想图。
在任意素图中构造素理想图的算法：
初始化：令素图G（V，E）的所有结点为待定点；令G（V，E）中所有待定点的导图为待定图.
约定:选取任意壹个待定点为去点后,令所选去点的所有关联边为去边;令所选去点的所有邻点为留点;
令素图中两个端点都是留点的边为留边;令素图中所有待定点的集合的导图为待定图.
步骤壹：在素图中选取任意壹对有度为5的公共邻点的对点为初始去点。
定义(极大待定子图):若待定图Gx(Vx,Ex)非空,且存在非空结点集Vy,满足:
1.Vy在素图中的导图Gy(Vy,Ey)是连通图.显然Gy是Gx的子图.
2.任意v∈Vx,若v不属于Vy,则v不与Vy的任何结点相邻(或者等价地说,任意v∈Vx,若
v与Vy的至少壹个结点相邻,则v∈Vy).
则称Vy在素图中的导图Gy(Vy,Ey)是极大待定子图.
定义(包络):设Gy(Vy,Ey)是极大待定子图,若存在图Gz(Vz,Ez),满足:
1.Vz的每个结点都是留点.
2.Vy的任意结点不与不属于Vz的留点相邻(或者说,Vy中的结点只与属于Vz的留点相邻).
3.Ez的每条边存在属于Vy的对点.
则称Gz(Vz,Ez)是极大待定子图Gy(Vy,Ey)的包络.
定义(临界点):至少有壹个邻点是留点的待定点称为临界点.
显然,待定图非空,则有临界点.非临界点的待定点其所有邻点都是待定点.待定图中也只有临界点到去
点的距离是贰.
定义(对留边):若某个临界点是留边的对点,则称这个临界点对留边,或者说是留边的对点.
定理:包络上的每条留边都有对点是临界点.
证:显然.
显然,步骤壹之后,包络存在、且是所选去点的所有邻点的集合在素图中的导图----即包络是简单回路.
易知任何待定点不与包络上叁个连续留点(即存在两条边的叁个结点)相邻,否则素图中有度为四的结点.
定理:设包络C是简单回路,C的内区域是极大待定子图Gy(Vy,Ey),取Vy中任意壹个对留边的结点为去点.令所选
去点的所有关联边为去边;所选去点的所有邻点为留点.令素图中两个端点都是留点的边为留边.若C的内区域还有待定点,则C的内区域上的每个包络都是至少有四条边的简单回路.
定理:若极大待定子图Gy(Vy,Ey)的包络Gz(Vz,Ez)是简单回路,则Gy(Vy,Ey)的所有临界点的集合在素图中的导
图是连通图.
证:Vz的每个结点的属于Vy的邻点的集合的导图是壹条道路,即是连通图.有Ez的每条边存在属于Vy的
对点，即Vz的每个结点与至少壹个属于Vz的其它结点有属于Vy的公共邻点.从而Vz的所有属于Vy的邻点的集合的导图是连通图,即Gy(Vy,Ey)的所有临界点的集合的导图是连通图.
定义(可选点):若待定图非空,其中存在临界点Vx,满足:
1.Vx对留边.
2.Vx到至少两个去点的距离都是贰.
则称Vx是可选点.
定义（留形）：算法执行过程中，若存在由留点构成的图G3（V3，E3），满足：
1.G3（V3，E3）存在K3（即G3（V3，E3）中存在两两相邻的叁个结点）且是连通图；
2.任意v∈V3,v在G3中的所有邻点的集合在G3中的导图是壹条道路.
3.任意e∈E3,若e存在对点是留点,则这个留点属于V3(V3中的任何两个相邻结点都不存在属于
V1但不属于V3的公共邻点)。
则称G3（V3，E3）是留形。
显然，留形的每条边都在该留形的K3上。称边数大于叁的留形为大留形。
定义(对留形):若某个临界点有对边是留形中的边,则称这个临界点对留形.
定理:步骤壹之后,每个极大待定子图都存在可选点.
证:对任意壹个包络,它的所有结点都是两个去点的邻点,且其中两个不相邻的结点是两个去点的公共
邻点.则包络内的极大待定子图存在这样的临界点:对留边,且所对的壹条留边的壹个端点是两个去点的公共邻点----即这个临界点对留边且到至少两个去点的距离都是贰,从而这个临界点是可选点.
定理:步骤壹之后,待定图非空;且每个包络上的任意两个不相邻结点不属于同壹个留形.
证:待定图非空显然,否则素图有度为四的结点。后者显然。
步骤贰：若待定图为空，结束；若存在极大待定子图的结点数不大于叁，转步骤叁;否则按以下优先级取可
选点为去点：
Ⅰ.在待定图中度为零的；
Ⅱ.在待定图中度为壹的；
Ⅲ.在待定图中度为贰的；
Ⅳ.有最多的邻点是留点的——即若可选点a有s个邻点是留点，则其它任意可选点最多有s个邻点是留点；
Ⅴ.对大留形的。
关于步骤贰的解释
若待定图中存在Ⅰ级点,即度为零的点,则取其为去点。
若待定图中不存在Ⅰ级点,但存在Ⅱ级点,即度为壹的点,则取其为去点;若有多个Ⅱ级点,取其中符合Ⅳ级
的点;若没有或有多个符合Ⅳ级的点,则取其中符合Ⅴ级的点。
依上类推.
定理:执行步骤贰时,符合以下任何壹项的待定点是可选点:
1.是包络上叁个连续结点的公共邻点的.
2.在待定图中度为贰的.
3.有对边属于留形的.
步骤叁：若存在极大待定子图的结点数不大于叁，则按以下方法取可选点为去点：
Ⅰ.若结点数为叁且这叁个结点形成K3，且存在不对大留形的点，则取其中不对大留形的为去点；
Ⅱ.若这些结点不形成K3，则有（在极大待定子图中）度为壹的点，若存在度为壹且不对大留形的点，
则取度为壹且不对大留形的为去点，否则任意取度为壹的为去点。
定理：包络上两个不相邻结点在素图中相邻当且仅当包络上以这两个结点为端点的壹条道路的所有边对同壹
个去点。
定理：在算法执行过程中，每个极大待定子图的包络都是边数不小于四的简单回路。
证明：设Gx(Vx,Ex) 是壹个极大待定子图，Gx 的包络是C 。考虑这样的区域D ：D 的每个域至少有壹个结点
属于Vx ；Vx 的每个结点所在的每个域都在D 上。
易知D 是闭区域，其边界就是Gx 的包落C 。显然D 是连通区域，否则Gx 不是连通图。若D 是多连通区域，
则D 的边界，即C 是由若干条（至少两条）两两之间无公共结点的简单回路构成，且其中壹条简单回路在其它所有简单回路的外区域上——不妨设这个简单回路为C1 。于是
C1 内区域上的其它留点——含C 上其它的留点——到C1 的距离至少是贰。则C1 内区域和外区域都有去点，
且C1 内区域上的去点与C1 外区域上的去点的距离至少为叁。这与算法选取去点的方法矛盾。故假设错误，D 是单连通区域，故C 是壹条简单回路。
显然C 至少有叁条边。若C 只有叁条边，则Gx 所在不是素图。定理得证。
定理：算法执行过程中，任意两个留形最多有壹个公共结点。
证明：设有两个留形Ax 与Ay 存在至少两个公共结点vx 、vy 。则Ax 上存在两条由vx 到vy 的道路R1 、R2
；Ay 上存在两条由vx 到vy 的道路R3 、R4 ：R1 、R2 、R3 、R4 这四条道路两两之间有且只有两个公共结点vx 、vy （若不存在只有两个公共结点vx 、vy 的两条道路R1 、R2 ，则Ax 不是留形；同理对Ay ）。不妨设R2 、R3 在由R1 、R4 围成的闭区域Dx 的内部，如右图所示意。则Dx 内存在去点。不妨设Dx 的去点比Dx 内的去点先被选为去点。则Dx 内的第壹个被选去点不是由选取对留边的临界点所得，即与算法矛盾。于是假设是错误的，定理得证。
定理：对于任意壹个极大待定子图的包络C ，C 上任意两个不相邻的结点不属于同壹个留形。
证明：若定理不成立，则存在不是可选点而被选取为去点结点，与算法矛盾。
推论：任意留形在任意包络上最多有两个结点，有两个结点当且仅当这两个结点在包络上相邻。
证明：若存在留形在某包络上有叁个或叁个以上结点，则包络上存在两个不相邻但属于同一个留形的结点，
与定理矛盾。若存在留形在某包络上有两个结点，则由定理知这两个结点在包络上不能“不相邻”，即在包络上相邻。
定理:算法不会使半理想图有环.
证:若算法使半理想图存在环,不妨设某个环由简单回路G3与连通图G4的结点的集合生成.由算法,不
妨设G3上的结点先成为留点时,G3的内区域上全为待定点,且G4在G3的内区域上.则必然是G3上的结点全为留点时,G4上的结点仍全部为待定点,否则与算法的取点标准----对留边且到至少两个去点的距离为贰----矛盾.但G3上的结点全部为留点,且G4上的结点全部为待定点时,应先取G4上的结点为去点.于是得到矛盾.从而半理想图不存在环.证毕.
定理：算法所得是理想图，即若算法使半理想图存在K3，则每个K3属于平凡细胞。
证明：只需证明算法不会生成链......
定理：算法所得是上面定理所说的素理想图。
证明：
定理：素理想图可以3上色。
可叁上色的不同方法的计算:
新加细胞与已有细胞的关联点分别有(x1,x2,x3),(y1,y2,y3)----即在包含新加细胞的所有已选图的
所有不同叁上色方法中,有x1种是新加细胞的关联点上1的,有x2种是新加细胞的关联点上2的,x3种是新加细胞的关联点上3的,y1种是已有细胞
的关联点上1的,y2种是已有细胞的关联点上2的,y3种是已有细胞的关联点上3的。
===============
我没有时间给出完整的证明。
但是提出了原创的两个猜想——不知道有没有人已经提出过，如果有那么就不希奇了。同时给出了一些参考。这是我认为有价值的地方。
最重要的是两个猜想和下面的证明思路
我认为第一个猜想很有趣。
重要思想
素数——>素图
导数（数学分析）——>导图
理想（群论）——>理想图
包络（常微分方程）——>包络
留数（复变函数）——>留形
标准正交基存在及构造方法的施瓦茨定理（线性代数）——>算法
若尔当定理(复变函数) |
|
/1 
IP卡
狗仔卡
发表于 2009-3-22 11:51:35
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡