正常的边染色

2007年(第36卷)第2期 j：化教 李 正常的边染色 刘 君，安容瑾，任志国，赵传成，包世堂 (兰州城市学院 计算机科学教育系，甘肃 兰州 730070) 摘要：图的染色问题是非常困难的问题，使得许多数学工作 者都致力于这一工作。就图的边染色来说 ，已经得到很多重要的 结果。本文着重讨论了几类特殊图的边染色问题。 关键词：边染色 边色数 O 引言 图的染色问题是非常困难的问题，使得许多数学工作者都致 力于这一工作。就图的边染色来说，已经得到很多重要的结果。由 不同实际问题引出了不同的染色概念，如仓库数的确定，地图染 色，有线通讯网、无线通讯网等引出的邻点可区别边染色问题，得 到国内外图论研究者的关注，现在产生了许多有价值的成果。 定义 1【1 2 3】设图G为一个简单连通图{1，2,L,k)，为一个色 集合，若，是一个从E(G)到集合{1，2，L'k)的映射，即 E(G){1，2，L，k)， 满足任意相邻的不同边 e,e ∈E(G)有／(e) ，(e )，则称厂为 G的一个正常k一边染色，简记作k-PEt of G。且称 (G)=min{kIk—PEC of G) 为G的边色数。 Vizing定理：对于简单图 G，有： △(G)≤ (G)≤(G)+1， 其中 △(G)为 G的最大度点。 但什么样的图 G有 (G)=△(G)或 (G)=△(G)+1，这是一 个至今没有解决的问题。 引理 1【1】 设图 G为一个阶至少为 3的圈，则有 ， 一 f2，n 0(mod 2) 1 3,n§l(mod 2)。 引理 2⋯ 设图为一个阶至少为 3的完全图，则有 ㈣ = n -0( ~l( m m od od 引理3111设图G和 H为两个简单图，若 GH，则有 X (G) ≤ (H)。 引理 4【l】对路 Pn，有X (G)= 1 主要结论 定理 1对图C ·Pn(m≥3)，则有 (C ‘Pn)=3。 证明：由引理 1可知，圈cn(n≥3)的正常边色数是 (c =【3，2, n ； =-- 0 1(m (m od od (n≥3)，对于圈 的正常边染色方法是： 情况 1：当n=0(mod 2)时，6- ／【v 1 )=1(i-1，3，L,n-1)；／【v／AVi+1．1)=2(i-2，4，L'n一2) 贝Ⅱ有C(v 。)=f 1,2}，贝4C(vi，1)=f3}。 情况 2：当 n=l(mod 2)时， ／【v 1 )=3 Ivi+LI)=1(j=1，3，L，n-2)；JIv。Ivi+I．】)=2(r-2，4，L'n一1)。 则有 C(vLI)={1,2}O=2，3，4，L,n一1)，C(v l)={1,3}，C(v I)={2，3}； ~J]C(viI)={3}(i=2，3，4，L'n一1)，c(v I)={2}，C(v 1)={1}。 此时每一个顶点的色集合的元素有2个，再跟据定义和定理 1．1的证明，可以得到对每一个路 P (v 。v 。，L，v 。 (i-1，2，L'm) 的正常边染色。 对 于每一个路 (v订 L ym(i=l，2，Lm)，取 c J∈c(v j)， c2∈C(vLI)，然后对 viIv ，VL2V。，L， Ilvlm(i=1，2，L'm)循环用 cI，c2染色。 综合上述，则可得：C ·P m≥3)存在一个正常3一边染色。 定理2对图C ·Fn(m≥3)(C 的顶点u。做为扇 F 的扇心)，则 有 X (C ’V3=△(C ‘ =n+2。 证明：由定理 1的证明，同样先对 cn(n≥3)进行正常边染色， 则类似地可以得到： 情况 1：当n=0(mod 2)时，有 ／【u u )=1(j=1，3，Ln-1)if(u ui+1)=2(j=2，4’L，n一2) 则有 C(u，)={1，2}~IIC(u，)={3,4，L，n+l，n+2}。 情况 2：当n=l(mod 2)时， u ，)=3 ju t)=1(i=1，3，L,n一2) 【uIu t)=2(i=2，4，L'n一1)。 贝U有 C(u )={1,2}(i=2，3，4，L，n一1)，C(u )={1,3}COO={2，3}；贝0 c(u ={3，4，Ln+l，n+2}0=2，3，4，L'n一1)，c(uj{2，4，L，n+l，n+2}，C(u3 {1，4，L，n+l，n+2}。 此时每一个顶点的色集合的元素有 2个，再对每一个扇 的翅进行染色，取 ej∈c i)(j=1，2，Ln)，对扇翅染色为flv~)=ci(i=l,2， L,m；j=1，2，L，n)；最后对扇边进行染色，因为在每个扇中所用颜色 中，无前面c(u 。)集合中的两种颜色分别赋给 c。和c：，而扇边是 路，可以用 和根据引理4对其染色。 综合上述，则可得：C ·F m≥3)存在一个正常n+2一边染色。 由～izing定理知，定理成立。 定理 3设 Pm=u1，u：，L，v PIl=vI，v：，L，v ，则路 P 和 P 的联 图 P V P．(m+n>／3，m≥n)有 (PoVP．)= m + n =3 or m= 2 。 证明：情况 1当 m+n=3，P VP 是 C，，已经在定理 1中做了 证明。 情况2 m=／1=2时， V Pn是 ，由引理 1知命题成立。 情况 3当 m=3，n=l、m=4，n=l和 m+n>／6，n=l时 ，PmV 是 F3、 和 Fm，已经在定理2中做了证明。 情况 4当m=3，m=2时，设，为： f(uIu~=lf(u2u3)=4 (vIvg=lf(uIvI)=2 (uIV =5， f(u：v，)=3f(u2v：)=2 (u3v-)=5 (u3v’)=5。 由此得PmVP 存在 5-PEC法，故例题成立。 情况 5当 m+n>／6，n>／2时，为得到 Pm V 存在 m+2一PEC 法， 情况 5．1当m+n≥6,n=2时，设，为： f(v =1 u )=i(i-1，2，L,m-1)； f(u，v )=i+1(i=1，2，L,m)f(uiv1j=i+2(i=1，2，L，m—L) (u v：)：2o 得到 P VP 存在 m+2一PEC法， 情况5．2当m+n≥6，n≥3时，设，为： 厂( +，)_j(j=1，2，L,n一1)； ，(umu I)=m+2 (u1u2)=mf(uiu I)=m-l(i=2，3，L,m-1) 厂(u =m+j+l-i[mod(m+2)](i=l，2，L，m；j=l，2，Ln)。 得到 PmV 存在m+2-PEC法， 综合以上五种情况，由Vizing定理知，定理成立。 参考文献： 【1】A．Bondy and U．S．R．Murty，Graph Theory with apphcations，The Mac~lillan presS Ltd，1976． (下转 128页) 185 维普资讯 http://www.cqvip.com 遣靛设计 2007年(第36卷)第2期 浅析影响季节冻土地区渠道衬砌防渗效果的因素 张瑞茹 (甘肃省景电管理局，甘肃 景电 730400) 摘要：本文笔者以本人从事渠道防渗抗冻试验研究成果和工 程实践经验为基础，对影响季节冻土地区渠道防渗效果的因素进 行了分析论述，并指 出自设计确定，施工准备阶段起，其防渗 效果便已受到直接和间接因素的作用。要使渠道防渗衬砌达到设 计的意图和保证应有的防渗功能，必须从施工阶段质量控制抓起， 彻底改变粗放管理方式；投入运行后，制定科学有效的#管理#， 强化运行管理，及时掌握、分析、渠道工程运行动态，抓隐患、找原 因，才能防患于未然，发挥工程应有的效益。 关键词：季节冻土地区 渠道防渗透 影响因素 1 影响季节冻土地区渠道衬砌防渗效果的综合因素 渠道衬砌是减少渗漏，节约水量，提高渠系水利用系数，保证输 水安全。充分发挥工程效益的一项重要措施，近十几年来，我国广 大科技人员研究提出了许多防渗抗冻的技术措施及设计，推 广应用中取得了显著成绩，但其应用效果与试验段原型测试结果 有一定的差距。本文就此人手，对影响季节冻土地区渠道衬砌防 渗效果的因素进行了分析论述，认为在防渗衬砌标准一定的情况 下，影响防渗效果的因素是多方面的，主要有工程环境条件因素、 材料品质因素 、施工质量因素、运行管理因素四大类。为此，提出 通过强化管理，提高工作质量等非工程措施来实现原设计应有的 效果。 1．1工程环境条件对渠道防渗的影响 灌溉渠道工程的特点是线长面广，渠段的地理纬度、海拔高 度、地形条件、水文地质状况复杂多变，其本身的走向、断面各 异，渠段各部位接受光照程度、土壤冻胀性、温度差异等环境因素 的不可避免，造成防渗效果大幅度降低或失效。因而冻胀、渗漏相 辅相成，环境条件(土、水、温度等)因素成为衬砌防渗效果的主要 影响因素。渠道原型观测明，受到中等程度冻胀的衬砌渠道，其 渗漏损失增大30％，估计在甘肃全省每年因此而增加的水量损 失达 1×108M3。同一防渗抗冻衬砌设计方案下，其防渗效果取决 于渠道衬砌所处的自然环境及其冻害的强弱程度，可见季节冻土 地区渠道衬砌冻融循环的过程，就是渠道衬砌变形破坏和渗漏加 大的主要原因。以上这种渗漏与冻胀的恶性循环作用加快了防渗 功能的失效速度，严重影响着设计寿命和经济效益的充分发挥。 1．2各种衬砌材料品质对渠道防渗的影响 渠道防渗层及衬砌结构形式较多，但所用的衬砌材料主要是 水泥、砂石料、砼制品、防渗膜料、伸缩止水填料等。工程实践证明 影响渠道衬砌防渗效果的因素关键在于所用材料品种的质量。对 于砼、水泥砂浆的质量来说，其水泥的标号、用量、水灰比是至关 重要的；对于防渗膜料、伸缩止水材料其性能的稳定性，各项技术 指标的真实性、准确性是渠道防渗层达到设计标准的因素。在景 电二期渠工程建设中，所用部分沥青玻璃丝布油毡进货检验不 慎，运行失事发现，所用部分沥青玻璃丝布油毡，胎布质量差，沥 青涂油面量不均匀，不能保证设计的抗渗性能和变形适应能力 (延伸性、抗裂性、低温柔性)，其抗拉断裂强度、直角撕裂强度、断 裂伸长率以及环境耐受性均达不到设计要求。给这种新型材料及 本工程造成不良影响。 1．3施工质量对渠道防渗效果的影响 近年来，我国在新建水利工程中，渠道衬砌工程应用了防渗 抗冻研究成果，其成效显著，但仍然存在一定的问题，经实例调查 分析认为，除设计考虑不够完善外，粗放的施工管理、工艺操作水 平、施工技术质量是影响防渗效果的主要因素之一。在防渗渠道 工程通水运用中不难发现 ，由于砼密实度不够引起的砼扳起皮、 剥落现象；由于施工管理失控造成砼板接缝、伸缩缝未清净、填料 深度不够、粘接不牢靠等止水不良现象；渐变段浆砌石工程砌体 不密实、块石搭接不良、扣缝不紧及缝隙嵌楔不牢固、开挖工程中 放线失误或操作不慎，基土超挖，补填密实度不够，边坡碎石杂草 未认真清除等现象；由于操作工艺不够规范等原因形成施工质量 通病或缺陷。所有这些质量缺陷，致使许多衬砌渠道使用不足十 年即要改建加固。进而在渠道衬砌破坏复修中，常常发现凡是冻 胀严重、出现滑坡、边坡变形、板缝脱节、错位等问题者，其施工质 量原因占70％以上。因此，施工质量缺陷与其它综合作用，纯属 人为的问题，其防渗效果对渠道投资效益影响最为敏感，其损失 令人遗感。 1．4运行管理不良对渠道防渗的影响 在渠道工程建设中，原则是不允许施工质量缺陷的存在，但 实际上很难完全避免。这种“先天 ”不足，在通水运行后，其后患 逐渐表露，主要有以下几方面： (1)在运行管理中，往往对其问题不能引起足够重视和及时 维修、处理，居多是在隐患形态恶化不得处理的情况下，才计划进 行维护，这一发展阶段实质就是衬砌防渗效果逐年逐降低的过 程。反映在运行管理中不能适时维修养护，而对防渗效果必然产 生的影响； (2)在平时管理中，对地下水 、灌溉回归水 、地面经流等外来 补给水未能事先采取有力措施预防、整治 ，造成渠床基土含水量 过大或超过冻胀起始含水量，渠坡在冻融循环中失去稳定性，甚 至产生滑坡，导致对防渗效果的影响； (3)因维修时未查清原因，维修方法及措施不当，维修质量差 而引起对衬砌防渗效果的影响； (4)因春季开灌过早，冻层未完全融化，冬灌停水较迟，渠床 衬砌层内的水分来不及排除或蒸发而冻结等不利因素，形成对防 渗效果的影响。 2 提高季节冻土地区渠道衬砌防渗效果的建议 近十年来，我国虽然在消除或减轻渗漏和冻害的直接原因方 面研究成果较多，当然也难以保证完全消除局部渠段渗漏、冻害 现象，要提高渠道衬砌防渗抗冻效果，必须从工程建设和管理的 实际需要出发，建议以下几点 ： (1)在设计方案及标准确定之后，必须慎重选择各种衬砌材 料，使其性能满足设计要求，并注重适用条件，实施水利工程建设 监理等控制手段，确保施工质量，实现设计应有的效果。 (2)在工程投运之后，应制定一套系统的适应本工程，科学有 效的工程管理与控制运用和管理办法：建立衬砌渠段的 档案卡，定期不定期的观测工程状态，经常检查，记载存在的问题 或处理情况，以便将来查考及其为设计管理积累经验资和资料。 (3)运行管理中要研究出解决常见影响渠道防渗效果问题的 技术对策和预防处理措施，从一点现象人手，分析本质及时维修 养护解决问题，保证渠道衬砌的完好率，使之安全运行，发挥并扩 大其效益，延长使用寿命。 (上接 185页) 【2】Harary，Graph Theory，Addison—Wesley，Reading，Mass，1 969 128 【3】G Chartand and L．Lesniak，Graphs and Digraphs，Second edition， Waswworsth and Brooks／cole，Monterey，C e 1986． 维普资讯 http://www.cqvip.com