（应用数学专业论文）平面图的全染色及列表全染色.pdf

y8 3 8 2 7 9 平灏圉购全染色疑剿亵全染鬯 摘要 本文壤究甲厦匿8 趣垒谯数凇、瓣) 及垒逸辑数曲t 蜉。逶i f d i s 施$ 辫方馥上 姿谖明了； ( 1 ) 蓉g 怂最大发为8 恳苓客蠢垂瞪瞧甲曩f 篷，魁x ，( 国& f 2 饕s 凳最大度势9 覆不禽霄牟潞蠡巷聱群蕊，剿搬，( 固= i o 一 ( 3 ) 若g 凳最大度为h 丑不含甯褶邻三角形| j 勺下面围，则c k ( g ) 拦，( g ) = 1 2 邀婪缭聚藏对长翔悉新来决的垒色散猜慧波垒造撵数猜想进一涉交撩。 荚键询：乎商灞，不岔誊霹，垒色羧，全选撵数 t o 霉a ec o l o 蛙n ga n d 辩s tt o 置a g o t o 蛙n gf o 巍p b a n a r g 魏a p 糕s a b s t r a e t 鞋l i sd 酶甜a 毫i 。ns 搬d i e st 缱菇c 。l o i n gg 耐l 戳t o 毫赫c 。h 诹g 赫tp 雄g r 8 p b # 驺y d i 8 随a r g i 就舀i t 强p r d 纯8 t i ) 拄g 招a c 0 靠嘴m 髓e 擎神h 趟( g 净6 ，t h 嘲x t ( g ) 蔓8 一 ( 2 ) i f gi 8 8p l a n e g r a 盐硝乞h m 8 x d e g r e e 9 袅n d 慨也。斌- c y c 锚；撼e n x t ( g ) 爨l o v ( 3 ) i fg 招ap l 鲫eg r a p hw i t hm 脒i m l l md e g r e e1 1a n d 谢t h 0 1 l t8 d j a c e n tt r i a n g l e s 嗣l 雌曲彳( g ) 嚣j 防( 0 ) = 1 2 弧镪e 燃h l 秘删净僦鼬秘蛾c 。融堍鼢鲻档瓠勰勰疽 鹣l 融t a le 。淞嘲 c o 积i l r e 瓤r 强嚣。 k 毯yw o 巍静s p l 雠托r 蟮r 娜h 为稍酶挑蟪4 一e 弹l 馘僦甜h 嘲l 魏t i cm l m b e 撼a i 瘫。i e e n u t n b 盯 一、缝论 ( 一) 、纂本掇念 零磐中，+ 定义一骛溪掰蘩辩臻论瓣基奉拳潺苟符弓，孀；嗣表示蒙食s 中瀚觉豢 争敬一个育垮对g 一( 舐e ) 绺为个无商镯，萁中v 跫一个有隈条台，露凳v 中 瓣不弱蠢索瀚是j 芋辩沟巢畚v 中静觉素獬徽璃8 的颚点，鬈中的觉察嘲擞圈g 纳 逸通常用矿0 ) ，嚣( 钟势嬲表示图8 的顶点葵含，边纂禽霹l g 硼( g l 表拳爵8 的顶点数和边数没肖霆远f f f 环附图叫做简单圈除非特剐耩出，本文研究的图均糖 翦隈衡肇，彘商瞬掘果貔将匿g 礴柱警垂上，袋褥它鹋逸段程溃点处方霹戴档交，瓣 髂蹑露是霹乎嚣匿辫麓逮静乎麓上 l 孽囊漾髂为灏瓣乎磷嵌入，或嚣为甲 藩图。 对乎围8 中的蕊点“秘蛰逛# = 粒# 芑嚣辫) ，魁拣嚣秘# 摇邻，戏珏鞴# 篡舞 邻赢；遨彗壹叉淡鞲口戆# 漆臻意，鞠分澍苟籀关联蒋g 辩逾# 和，有一个公 共端点，弼称e 和，榴邻，菪瓣个谢至步关联一螽公共j 氩，喇称运两个僦艄邻，在圊a 串慧顶点 稍邻的预赢的京俸州依“纳部域，记侉0 4 ，并撼。嘲= 蜘洳) u 砖 称作点的鞠部域张 蜥如) 为溪点# 的度数，；b 律南扣) 张瘦熬冀豹硬点兜斡 点+1 m 意义张悬挂点用6 ( g ) 和 ) 表示甲面爆g 顶点的最小发棚最大度。越记 海5 秘a 设瞬嚣璺擎落露，常掰f ( 磷寝幂霹豢含+ 瓣予，毫p 圆，掰馥，) 表永围绕篱， 的闽途缝。营撇，是6 蛙) 土按矮辩赞捧捌游蠢，鼗秘藏记，* 缸l 堍l - 黎点“b 2 ，t ，每灏，季霉篝联，趣途径壤，) 纳长密称蔫丽，衙斑+ 褥争发势 韵衙为舢两廉数的黼可谓为妊面 对予黼g = 戳固潮圈嚣一_ ( 占k 蕾肖矿虻茧黩则器闭嚣盛躁g 的一个子豳。对于矿y g k 把躜0 中鼹手躲疆京轼及鸯串瓣熹关联瓣逑 都删除所得到的匣记作g y 戚g 一对予“， v ) ，蝴蜀譬l ，把在圈g 中连接碾惠毪# 所婚劐趣愿记佟8 + ，艟手矿sy 瓣) 糍盎驴棒为暖森黎。 3 鞭了：蓍g 怒一个奇数阶囝，且6 十iiv ( g ) l 下r ( g ) 十i ，( 其中r ( o ) 是g 中最 大凄点瀚个数) ，剜g 是第一型雨 本文证明了：l 。若g 是最大发灏9 且苇鸯鸯垂窭辫警藏瑟，劐x r 0 j = 1 0 。 2 蓉g 是最犬攫为7 昱苓禽有缸圈的乎蘑辫，女= ，5 ，6 ，曼! l 鼢f 固= & 3 游g 屈一个街数阶图，a 足森林且6 十a 兰 i v ( g ) l 十1 ，1 u 如一l i 曼， 凳 x f ( g j = + l ， 蹬嚣g 羽每争鞭点或逸z 努辩一个色硎表王，( 。) ，著对簿个顶点或遗y u 嚣，都 可从其埘虚的列表五( m ) 中选择出一个颜色染缎，使得任意瞬个相邻戏捆关联的蠢索 接受不同陶颜色，剥称g 是l 垒可染的 若对g 的每一个全包猁表占茹 二( $ ) i 占扣) 七，2 矿u e ，o 都嫩 全可染 憋，尉转g 屉b 垒霹选撵灼。 研究露的列表垒染魁，瓣子捌蒜垒染色，毒以下著名辩籀摄。 酬袭垒絷惩猜憩( 掌0 9 ) ：澍每个琶g ，c b ( q = 特( g ) 。 对甲耐图g ，b o r 础n ，j 如s 。娩詹4 爨f w 。拙赫哦l3 l 证明了，( 1 ) 。兰1 28 童。( 2 ) ? 髓孽4 时， ( 3 ) 6 且乎2s 时，( 4 ) 杰5 艇孽6 封，( 5 ) 3 拽9 1 0 对，疏r ( q = x t ( g ) 藏摊凡f 1 4 】u i 芷明了：著g 足个外下面图且 3 ，赠如r ( g ) 茹x r ( 8 ) 。王缨咒 l 譬_ i 芷骥了，若g 茫一个嚣s 薮髓翻嚣4 ， 则蕊，( o ) 等x 掌( g ) 本文证明了；1 若g 足一个各涟通的系列甲行图，丑( g ) 5 ，则拙r ( g ) 兰 x f ( g ) 2 ，蒋g 惫最丈痰为l l 珏不禽有辐邻三角移释搁邻3 _ 衡与4 _ 筒纳下面图，制 c k ( g ) 一) 凹( g ) = 1 2 。 6 二、 盎 g ) ；麴攀霉錾瓣奎琶数 砖于甲蕊图，全包数猿颦盯g a ) 仍未获穰辩整证明瞧一待完戚的瞳拣情形息 矗( g ) 一6 拳萤营走考虑矗( o = 6 豹乎垂蚕酶盒煎鼗 令c j 我示长度为n ( 3 ) 的圈，则不难证明： i l 理2 ，lg 是垂愈胃选择稳 定义2 2 令焉丧暴一个5 - 鬻。若g 趣一争子蓬嚣丽德于砖曩对所寄鹃 ! y ( 田，肖d 扣) = 4 ，则称嚣为g 的一个f 5 一子母 定义2 3 令霹表承恰有一条公共边的一个5 _ 面与一个3 _ 面的并若g 的一 争子蓬嚣秘搀于瑶要砖耩寄稚”y ( 嚣) ，有d ( # ；= 4 ，委l | 稼群为g 簿一令f 善圣匿， 孽l 理2 d f l 6 】设g 是一个6 兰4 的甲面瞬若g 不禽帑垂匿，则g 含有礤 予瑶。执蔼禽有羁- 子辫。 事l 壤霉5 设g 慧一争6 = 3 ，a = 6 基举禽垂整涟哥嚣墨。著g 躯每争 点的三个邻点都是6 - 点，剐g 禽育b 一子图 瓣黪：嚣笼；塞警辩藩瓣黢控公式毒褥 ( 2 d ( ) 一6 ) 十( d c ，) 一6 ) = 一1 2( 1 ) t ，y ，e f 褒在终g 躲覆轰z 势篦投棼= 豁6 ，绦g 辩嚣努蕺毂$ ) = d 缸 一8 ， 则( 1 ) 即为 扛) 一一1 2( 2 ) 0 y 7 投羁，粥蛐( 口) 蜘( n ) 一6 描o 著d 糖簧联了一个麓数6 曲面穗r l ，岛，a 至多转移了稷5 瑜等它相关联的 鼯。匿为g 葶食有舡嘲，每个书点蘸多关联曼个孓垂，珏撼争孓蠹至磐关联一拿 点；陵此出恐l k 球至多转移了枝l 给棚关联的3 - 鼓上的点。胰蔼 汹整 若口至步关联了两个艘数6 附筒。由咒l ，r 2 ，n 至多转穆了权4 蛤与宅相关联的 露壶甄( 2 ，8 至多转移了较。绘与宅关联的3 一焱曝戴 n ) o 其次考察蕊的新椒： 注意瑚群没有4 一面，d ( ，) 6 的面俺扳没青变化且它们原来的极缘姆o ，所以 下蕊其需考虑3 一面和5 一面柏瓤税 首先考察3 - 匿静瓣投，设，恳g 的一拿3 - 鬻，努疆静憾澎讨论鲻节t 1 ，不与3 - 点相关联 这辩，蠹舰辩琏爵臻它静兰夺谈赢各获撙较l ，扶错，) = 0 2 ，与瓤轰稿美联， 设，= n 蚰，o 是一个3 _ 点，髓与，相邻的兰个蔺为 ，矗，氩如噬2 一l 所示撼 鞭设，8 的曼伞邻点6 ，岛d 都足精点因为拈幂禽有事圈，每，榴部的黧个面既幂 懋3 - 面。也不屉4 面 9 图2 _ 1 图2 2 ( 2 1 ) ， 中有一个足5 一面 不妨设 足5 一面，则，1 至多关联两个3 一点 当 只关联了一个3 一点8 时，顶点c ，d 由规则r 1 ，岛各向 和，转移了权1 ，四 此( ) 1 现在可转移 的权l 给相关联的3 一点，可得叫( n ) = 1 由于3 - 点至多 关联一个3 _ 面，因此又可转穆n 的权l 给它相关联的3 - 面，从而，在保持r 1 ，凰的 条件下，通过权的调整可使，的新权( ，) = 0 当 关联了两个茁点时， 关联的其它三个点都足6 点，由规则见可得 叫( ) = 2 ，现在可转移 的权l 给每个相关联的3 - 点，则叫协) = 1 因此叉可转移 。的权1 给它相关联的摹面，从而，的新权( ，) = 0 ( 2 2 ) ， 都足度数6 的面 由规则r l ，可从顶电b ，c 处共获得权2 ，由规则凰( 1 ) ( 2 ) ，点n 可从点6 ，c ，d 处共 获得权1 囚此可转移。的权1 给它相关联的3 一面，从而，的新权 ，( ，) ：0 其次考| 察5 一面的新权设，足g 的一个5 一面有三种情形需要讨论 1 ，至少关联了一个6 一点 由规则恳，可从这个6 一点处获得权1 ，因此它的新权 ，( ，) 兰0 ； 1 0 2 ，至少关联了一个3 点据题设，至少关联了两个6 点，从而可转化为情 形l ： 3 ，既不与3 - 点，也不与6 - 点相关联这时有三种子情形会发生t ( 3 1 ) ，关联丁五个4 _ 点则，是g 的一个f 5 一子图 ( 3 2 ) ，至少关联了两个5 一点 由规则r 2 ，至少可从速两个5 一点处共获得权；四此( ，) o ( 3 3 ) ，恰关联了一个5 _ 点o ( 3 3 1 ) ，关联的4 - 点中，至少有一个4 一点至多关联一个3 面 由规则r ，可从点。处获得权；在保持冠，的条件下，再分配这个4 _ 点的权 给每个相关联的5 一面因此，的新权”( ，) = 0 ( 3 3 2 ) ，关联的所有4 一点都关联了两个3 - 面，如图2 2 所示 考察点n 所关联的五个面：一个为，与，相邻的两个面都足3 。面，剩下的两个 相邻的面都足度数5 的面，分别记作 ，2 设 与也的公共边为n b 若 ，止中有一个面的度6 重新分配n 的权1 给每个与此点相关联的3 一面或 5 面从而t u 7 ( ，) = 0 若 ，2 都足5 面因为d = 5 ，据题设d ( 6 ) 3 从而d ( 4 当d ( 6 ) = 6 时， 由兄， ，2 从点6 处分别获得权1 四此可垂新分配点n 的权l 给每个相关联的 异于 ，止的3 _ 面或5 一面则钮( ，) = 0 当d ( 6 ) = 4 日寸 b 至多关联一个3 - 面( 否贝哇出现4 _ 圈) 若6 关联一个孓面，不妨设这个孓面与矗糖邻，速时点c 也至多关联一个孓 面仿( 3 3 1 ) ，可再分配6 ，c 的权给 ，这时 可从点6 ，c 处共获得根；田此重新 分配点n 的权 给 ，：给，2 ，l 给其他每个与口相关联的3 _ 面或5 面则”，( ，) ：o 灞2 3 ：懿一予匿 由g 辩逸靛灼最小性，g 露岸) 凳8 - 垒可染的设妒：v ( g ) u 嚣( g ) 一e ( 群) 叫 i ，2 ，8 魁g 一鳓( 科) 的一个8 - 奄染色现柱抹去饥封) 上各点的颜色 讹 y ( 置) u 嚣( 拦) 。令五( 。) 篇 l ，2 ，秘 癜奶| 掣8 一矿( 封) u e 谬) ，笋与# 稿鄂蛾麴 荚联 则 缸 l = 4 据联莲2 1 _ 珂躲鞋是4 一垒霹选撵麓扶蠢g 瑟孓委耄垒露絷 的这与r ( g ) 8 相矛盾 定理2 6 证擎 日 由弓 聪3 3 可箱，孓鲥口至少关联三个虞敦4 曲点，讲此由拽l 可褥叫( 。) 因此，对g 中的顶点鞍露经过投的逶当羹掰努配之蘑毒褥 秘) o 艇p u f 速与( 1 ) 棚矛震。从弼竞戚下定理3 ；2 瓣涯暖a 定理3 5 蒋g 息嚣7 且不禽霄融圈的甲筒随。七篇 4 ，5 ，6 ) ，则船( 回= 8 簸善定邋3 | 5 不戚立- 选取一个滋戆定理条簿，毽苇惫醣垒霉染的 y | + | 蟊 的檄小图，记为g 善i 瑾3 糟蒋封口嚣姆) 珏d ( 锚) 三兰3 ，劂d ( “) + d 斗2 盎9 证罐与 l 骡3 ，3 瓣诞明娄证( 嘲+ 证薅宠臻3 蠢籁巷定理3 不威立选浆一个满怒瘫趣条侔，艇不瑟垒霹 染避l y | | 嚣 憋嘏枣篓，记鸯g 由甲蕊图的歇牡公式哪得 ( 2 d 扣) 一6 ) + ( d ( ， 一国= 一1 2l 现在给g 的顶点$ 分配权叫( # ) 慧2 d p ) 一6 ，缭g 的嚣分鲢较谢( 菩) 紫d 0 一6 ， 蒯( 1 ) 即为 ( 。) = 一1 2 $ v u f i 7 我 f 1 将根据下述规则r l 一悬重新分配蕊点辑l 两的权，婕褥重褰i 分配质的权稿 w 协) o ( 3 ) e v w 遽里t ”( ) 为重新分配权以后，顶点或面。的新权因为分配前的根和与分配后的权 秘应摇等，嚷镥) 秘( 3 ) 挺霹褥完残定理戆话硬辑需要静矛鹰 月l ：从锯个4 一点，转穆权l 给每个与此点相关联的舡田； 磁：获每个矗点，= 5 ，6 ，7 转穆权i 给每个与此点捆关联柏筒 璃：甄蟹争7 - 点转移权i 绐每个与苑点襁关联柏2 一点； 最：从每个- 丽转穆权终姆拿相关联的务点 昆：从每个虹麟，= 4 ：s ，8 转移权1 绘每个耀关联躲善苣。 下甏考察硬点霜藩熬艇较： l ，毫一赢”的毅扳；巍弓l 理3 零珂翔2 一点廷匀孓点辐镡。嚣蠢鸯0 举岔缸鞠， 七盎 4 ，5 ，6 ，则w 至少装联一个厶馘从而据尥，丑可得 ”如) = ”( ) 十2 x2 十拦 一2 + 2 尝o 2 3 一点”的耪权：7 ( ) = ( 。) 一o 3 出点的薪投；因为4 - 点至多关联巅巾3 一嚣，出冀l 霹得帮( ”) = 榭( ”一2 兰 2 2 = o 4 “点 ，七= 5 ，6 ) 的新权，因为每个膏一点至枣关联【l j 个3 一筒，因此耀鼠可 器留( ”) ；铆扣 一l j l # 2 奇一6 一 jx o 5 。缸点”游嘉 较；# 至多关联兰拿3 - 搿； ( 5 1 ) 关联一个3 一蹰时， 至彩相邻6 个磐点，因此点岛，r 3 霹捧；( 呐= 撕扣) 一8 一l = 8 5 一l n 1 s 弱觅最就是所要求的戏配鄙秽中存在匹配n，如。a满足断誊 令o崔9一(nuur)，观稚考察g中替个点黼度数；( 1 ) d 扣+ ) = 2 n + l 2 箨杜一) 嚣2 一2 拜中l ； ( 2 ) 若 。 d 扣) 蔓一( 2 竹一一1 ) 兰2 一2 n 十l ；( 3 ) 若 i ， 、 f 如( ) 一i 一( 窑强一l 篇2 一2 弼 ( 4 ) 。若 足其余点。 d g ，扣) s 十l ( 2 傩一矗) 嚣2 a 一2 悻+ 1 由上可得g 的最大度点集为碥u 和+ u ) ，其中w 魁g 中不在内的最大 度点( 善存在) 毽为矿骘玛中的点稳不摆部，整鸯憝致莓翔鞭轰集骗u 导爨池 子图足森林，默薅串的最大度点饕盎憋予墨墩是森抟。霹照壶g l 璎4 + 4 霹器秽罴 ( 2 一2 n + 1 ) 一边可柴的 漫聍悬g 的一个丑= 常建染题，强它所硐静色榘海 叠豫一+ l ，+ 1 ) 下澍 挟# 岛发用a + l 争色构造窭g 绱一争垒染魏毋 驴缸) 掌秽如) 若e 嚣( g ) n f ( ) ； 烈目) = 口( ”矿) ，蒋矿e ( k ( 口) = ，若口 $ ，挑 ； ( e ) = 奄，装e 鼹，奄# l ，t 。，2 魏一 褰易验涟这嚣的8 凳g 瓣一个汹+ 1 ) 一正豢垒祭魏完蕊了定璎4 毒囊孽麓骥墨 推论4 7 若g 蔑一个毒数阶躅，嚣矗是森林+ 荐( 回ii 矿问) l ，且 珏u 阜么一l s 潮翘( # ) = + 1 ， 逐葫：因强冬g 十l ， d 十a 22 6 + 1 2 y ( 。) l 十l ， 叉因为g 是森林，i 么u 屹一l i ，由定理46 可得x t ( g ) = a 十l 口 五、a ( g ) = l l 抟平西图的全选择数 列袅强色概念由vg v i z i i l g 茼次摇出【2 l 】，p 融出s 等人【2 2 1 丁1 9 7 9 争独立媲握 出这个概念。碰表染包育褡莛童 瓣前聚1 2 3 】，也是逝年来嚣常活跃的研究方秘，到丧染 色概念最初魁关丁点的染瓴，后来，由ac h e t w ”d 和r h 再g g k v i s t 【2 4 】弓l 入边列丧染 色概念，菸联炎了辛鬟斑的焱逸列袭巍惫，在这一肇中，研露强的刭表垒囊蕊阕题，对 t 建表垒色数，弯默下转褰鼹猜怒t 列袭垒色散猜想( 厶r d g ) ：对每个图g ，c h ，( g ) 幂x f ( g ) 壬熊凡等ai 1 4 ，l 鄙汪经征辫了辫甲面图，榉n n 图等燕特殊圈在一定的条件 下游跫捌丧垒染色骑慧率节首先输出系巍甲行稻的全建样数 定义s 1 若图g 币簿有同棉于段的子躅。粼栋g 是一个暴列甲圣荦罄。 引理5 2 f 2 5 j 若图g 是一十2 * 连通的系列甲行图，且( g ) 4 ，则育下述之 一残立： lg 蠢一对辎鹳的务点鞠毽 2g 有一个3 一圈“州z 使得d ) 蜊2 ，d ( 枷) = 3 ； 3 ，g 有一个4 - 豳豇g ”掣使得d ( t 1 ) 勰d f ) 篇2 ； 4 g 霄一个4 一意聊，扣) = 和，* ，访，使褥d 扭) = d ( ) 蜷2 ，( “) 篙 m ，z ) ，( 。) 翟 柳，分 。 引理5 3 【2 5 g 屉一个连通的系列甲行图，若g 。尬或e i ( n o 汩o d 3 ) ) 涮敝，( g ) 品( g ) + 2 ；誉瓣搬，帽) 麓固+ 1 定理5 4 蒋图0 显一个2 连通的系列甲行围，且0 ) 5 ，雕航z ( 回嚣，g 】 谣暌t 霹为簿) 2 龟瓣g 雾嚣l 褒g 乒c 0 每# m 。鹩) ) 虫l 理5 3 翔 x 砜口) 拳蕊g ) + 1 下蕊| j 霹聪吐武g ) ；臻( 国书l 一 假设襻在图g 不聚( 参( g ) 十l 卜垒可选撵婚选取一夺i 矿i 十i 秽l 婀掇小图，记 为o ，。爨髓理5 ，2 可褥最薅 孛沦娃下4 耱馕澎 一必i 审蚕：率 1 掣有一对糟邻的2 一点“捌m 具! 【由g 的极小性可知口一 u ，w 悬( a ( g + ) + 1 p 垒霹选撵游， 设关联，w 的公北边为e l ，其泉两条边分别为e 2 ，e 3 ，如图5 一l 所示因为( g + ) 5 ， 考查e 2 ，铅，电，“，训晦黎用色数，可褥包，8 l ，e 3 ， 分别至少寄 2 ，3 ，2 ，4 ，吣个色可选， 蕊丽可袄次染好e 2 ，如，e 3 ，口搿辩g + 是( ( 秽) 十1 ) _ 垒蜀选择豹，与( 是一个穰，i 反侧矛盾 2 商一争孓蘸。使锫) = 2 ，d 洳= s 菠蓉联 锤，碴 昭边为鼋，荧璇 弘z ，的遗为e 2 ，如爵5 2 所示则由g + 的檄小性可知g 一n 足( + ) + 1 ) 一全可选 的依墩考奁8 e l ，的禁甩龟数w 椰8 2 ，e l ，u 分瓣至少有t l ，魏盛个镪珂造，从黼可 袅敬染替印，s i ，嚣既伊是( 鑫9 + i 金溃涟+ 萼驴是一中羧枣瑟穗矛嚣+ 3 g + 有一个4 - 圈“z f 使得d ( “) ；”) * 2 ，贝| 由伊盼极小性掰知岔一 “， 罡泠伊) 十玲全霹海漉，首先考套 鸭” 蓑袋蛉浓 铘，8 孙唿；e 矗避墨3 所示) 螅 禁餍包数，毒得每条浚分别至少霄两个色可媾由 l 理2 1 可辩4 _ 鬻嚣逸可选样 的，则( e 1 ，e 3 ， 均可染又由下( g 勺矗，则u ，”分别至少有一个色可遗，蹲此 也可染技蠢g + 是给够j + l 垒霹遣拇黪，每9 基一个裰小曩援荸蘑+ 2 5 鬻霉囊攀 l i i ，善j d g 羁q _ 磊转豢= 萄谢! r “嚣i k 篓萋茎；i i 蠹锋i l 囊糍皇手l i j i ? * _ ! 茹i i 羹氍i ；j i p o i j g 崔g 霎霉羁；耋兰：蠢i 一繁蘑jr 耋撬? i i 疆妻煮；爹簧i 暑赛i j 爨i q ：蠹妻妻翥i 望望i 量j 1 _ j i 蠢亭j 菇 i 菇$ l ；型! i ? ? 装g 枣簸耋肇i ：耄j 誉。荨肆l ：耋鑫 茎i ； l 妻， 嚣；肇，墨毫烈q _ ；辫i 坠坠囊ii i pj f i ：l 兰： 坪i 髓誉蔓；熏! ? 葫害；毒i 鞲蓍藕| # ；鬟童 i 囊；至； ；鼍篓 l 誊窑二 嚣i 嘎。喜女强 i 醪妻1i 遵si 电堇蟊j i “￥襄i 蜊m i _ 鏊受毒i 鬟ii j i 划l ，描￥；鹫；蠢菇i 誊g 毫 一缱； 器蠹? 11 函出i j ；搓：誊篓5 r u 辅l ；j ：l 丑z 组：驴；辖雾雾鼍矗i i 藿嚣i 蓦葺；辇自邑箨i 辜i ； 璧l ；耋i 善i j 导j i 耋i 霉= ；垂? i i j 一莲；： 基嘉震i ；1 i g 雾鼙皇：誊藕；一弦赫；i 臻璃j ； 蔫t 蚤露三丽e ￥辜滴j ；i 藏j j 到甏i 艇誊t i l j i 叫嚣 ；= j 茔_ 琴 | 錾；g 繇麴 i * = l i l ；矗i ? ；j l i l l 篓i g ；韩醒j 习g j i 丫薷掣i 磊 舞鼎。翟髯i ；! ”。m ? _ ji 毫! g ；i 碧? 蠢舞 譬i 目_ ；妻i 簦羹羹 ；。i ； i g g 盆$ 薹；矗汗虢囊j ￥j 翼誓；篓硬 ；薹薹一i 筝l ， ! i 酶：釜薹g g ，4 孥i j ；j 女? ；j 鐾l ；叁l i 囊二。芋i ! 垂i ：f 女嚣i ；j j ：? 氡：囊二善釜董j i ；赫i ；室；l ； 毒：；竖自j l 。i 莓f 垂， ；曲，芝豢? “孽e 鞘雾弹：霸器：垂e ；茎! 塞i ， i j g 喜羹；雾 黔i i ；嚣蠹_ _ 荽鬲礤疆夏 i ! ! 女p 蘩 ；茎；萤；一琶蠹! ! i i 墓耋菱! 轰i 霪j i 雾氧 1 ；薹璧礤豢；凳i 姜箕耋童惑蔓一斟鼎姜翳! 鐾妻l 臻妻j 曩妻 薹 饕# 萝* 重毫毒篓i u u 霉 塾藿碧i 猎i 嚣 图5 6 定义5 1 2 若奄个2 _ 点“l ，瓤2 ，锚女( 患3 ) ，满足“。，“件l 尼一对胞点 l = l ，一1 且蛳，“石是一对“麓点喇髂这个2 一点是一个一( 乱跑弼) 证明悫瑾5 。5 ：盎甲蘑匿欧控公式 ( d ( ”) 一6 ) 十( 2 d ( ，) 一6 ) = 一1 2 ( 1 ) v，f 现在给图的硬点分配投 ( ) = d ( 。) 一8 ，给墨的篚分配壤f n 留) 一2 d ( z ) 一6 ， 则f 1 ) 即为 ”如) = 一1 2 ( 2 ) 我们将根据下述规则r l 一岛重汾配g 的顶点和面的权，使得重新分配后的权和 a ，o( 3 ) 3 t f 这里如) 为重新分酉已根以后，顶点戏面。的新权因为分配前的权和与分配后的投 稿痘裾等，辔2 ) 帮f 3 ) 囊碍= 褥完残定理辩证臻辑需要耱矛嚣 r l ：每个1 1 - 点转移权1 给它相邻的每个( 5 + ，3 ) 一点和( 4 ，4 ) ，点 转移权；给它姆 相邻的( 5 + ，4 ) 一点 氇：镶个垂面转移权i 给它榴关联的每个b 点，2 蔓s5 ， 凰：每个5 一面转移权2 给它棚关联的每个一点，2 蔓s5 壶霓2 ，f 毽可得t螂( 口) = 螂( u 十3 i = o 3 ，点的新权( 女= 4 ，5 ) ：没是g 的一个一点 因为g 不禽相