发布时间 : 星期一 文章图染色问题研究--成品更新完毕开始阅读c80aacf758fb770bf68a5512
[6] a.基本定理:
邻强边染色(邻点可区别染色):对图G的k-边染色f(uv)?E (G),有f(u )≠f(v),f(u)={f(uw)|E(uw)?G},那么我们称f为图G( V, E)的邻强边染色,记作k— ASEC,并称x G)=min(k|存在G的一个k —ASEC)为图的邻强边色。 b.基本结论：
1）邻点可区别全色数：
定理1：对任意阶为n(n≥2)的简单连通图G,邻点可区别全色数X G）存在,并且X G）≥△G+1。 定理2： 若图G（V，E）有两个相邻的最大度点,则有 X(G)≥△G+2。
2）单圈图邻强边染色： 定理1：设G是p (p ≥3) 阶的单圈图, C为G中唯一的圈，C的长为r。若△G=2，则
3）完全4-部图的邻强边染
定理1：设m >n> p> q≥1, 则xmnpq = m+n+p 定理2：设n≥2,则 x
。
Kn111）= n+3.
mn11 定理3：设m >n>2, 则x
K ）= m+n+2.
定理4：若n≥p+2且p≥2，则 x
KKnnnp）= 3n. )= 2n+p+1.
定理5： 若n≥p+1且p>1,，则x 定理6： 若n ≥p+2且2p, 则 x 定理7: 若n≥2,则x 定理8: 若n≥3,则x
nKnnppnppp)= n+2p+1.
Knnnn-1)= 3n.
K）= 3n-1。
nnnn-1 4）联图（Sn?S）的邻强边染色 定理1：对:m>n>1，x 定理2：对m>n>1,有
Sn?S=m+n+1。
三 、应用与意义：
研究图染色问题有什么应用价值及理论意义呢？若仅就地图染色而
言，用四种色或更多一些颜色并无多大实用价值。然而，若将地图中的几个区域视为几种化学品，凡两个邻接的区域所代表的两种化学品有某种关系，例如该两种化学品若放在一起容易发生爆炸或引起变质等。现欲建造仓库来存放几种化学品，显然建造几个仓库分别存放这几种化学品是万无一失的。但建库费用大，怎样才能使建库数量最少，又能使这几种化学品的存放万无一失呢？显然，两两均无任何危险关系的几种化学品可存放于同一仓库中，即只要建造一个仓库就够了。可见，这一建库问题就转化为图点染色问题了，所以研究图染色问题是具有实用价值的。但是如此得到的图，一般并非平面图或可平面图，则可由研究非平
面图的点染色问题求得解决。
至于图边染色，在电网络、时间表问题、拉丁方构造等方面都有很好的应用实例，这里不一一列举了。
虽然图染色问题已经取得了不少的理论研究及应用研究成果，但是染色问题的原本问题——“四色猜想”迄今尚未得到令人满意的结果，致使“四色定理”的证明成为悬而未决的一大世界数学难题。由于这一数学难题历时150多年尚未解决，就不能不使一些数学家们想到：很可能“四色定理”的证明必然伴随着一个全新的数学方法的诞生，以至形成一个全新的数学分支。若果真如此，研究“四色定理”的意义就远远超出其染色本身了，这将是数学家们对数学发展的一个重大贡献。[7]
参考文献
【1】孙惠泉 图论及其应用 科学出版社 2010年8月 页码2 【2】百度文库：图的染色问题
http://wenku.http://www.china-audit.com//view/52b07b225901020207409c71.html 【3】孙惠泉 图论及其应用 科学出版社 2010年8月 页码3 【4】多半是他人总结，参考而已，但是纯手工输入 【5】图的着色问题——PPT第36页
http://wenku.http://www.china-audit.com//view/2e1a0e2acfc789eb172dc81e.html 【6】图的着色问题——PPT第8页
http://wenku.http://www.china-audit.com//view/2e1a0e2acfc789eb172dc81e.html 【7】百度文库：有关图的染色问题的研究
http://wenku.http://www.china-audit.com//view/39770c0b6c85ec3a87c2c548.html