（运筹学与控制论专业论文）图的均匀着色.pdf

详细中文摘要 本文涉及的图均为有限，非空，无向，简单图本文主要研究了以下两方 面的问题： 1 树的均匀着色 2 完全r 一部图的均匀着色 称图g ( v e ) 是可均匀k 着色的，如果可以用k 种颜色给g 的顶点着 色，使得相邻的顶点不同色且各色类的基数至多差1 称g 可均匀k 一着色的最 小整数k 为g 的均匀色数，记为x 。( g ) w m e y e r 2 在1 9 7 3 年提出了这个概念 并提出了一个猜想：若g 是连通图但不是完全图和齐圈，则) ( 。( g ) ( g ) ，其 中a ( a ) 表示图g 的最大度m e y e r 的猜想对一些特殊图被证明是正确的，如 二部图【6 】，完全r 一部图 1 3 】，线图【1 3 ，外平面图【8 ，最大度不小于1 3 的平亟图 【9 ) 最大度不小于顶点数一半或最大度不大于3 的图4 关于图的均匀着色， b b o l l o b 6 s 和r k g u y 【5 证明了如果礼3 一8 或n = 3 a 一1 0 ，则顶点数为n 的树可均匀3 一着色；a k o s t o c h k a 2 6 证明了最大度不大予的外平面图可 均匀k 一着色，如果k 2 + 1 ；s r i r a mv p e m m a r a j u 2 7 证明了礼个顶点的外 平面图可均匀6 一着色，如果它的最大度不大于竹6 b l c h e n 和k w l i h 7 给出了不能均匀2 一着色的树可均匀k 一着色的充要条件由该条件的启发，我 们得到了树可均匀k 一着色的其他条件 定理1 设t 是最大度为的几个顶点的树，则t 可均匀k 一着色的充要 条件是存在一个点 ，d ( ”) = ，使得a ( t 一( ”) ) i n 肚l 一1 定理2 设t = t ( x ，y ) 是树且l x i = n m = m 如果k 芝m ( m + 1 ) 1 ，则 t 可均匀着色，其中3 定理3 如果t 是最大度为的树，则对任一顶点。，d ( v ) = ，t 一”可均 匀3 一着色 称树t 是毛虫树，如果删去t 的悬挂点及其关联的边后是路该路称为 毛虫树的脊线，记为p m = 2 ) 1 一设d ( v ) = d i ，i = 1 ，2 ，m ，记毛虫树为 t ( d l ，d 2 ，d m ) ，记 n7 = d i ，b 7 = 魂 ! 是奇数 是偶数 定理4 毛虫树可均匀2 一着色的充要条件是当m 是偶数时， 当m 是奇数时，0sa 一b 2 定理5 设t ( d t ，d 。，d m ) 是最大度为的n 个顶点的毛虫树，则对3 ，可均匀女一着色，如果 sm a x 2 n 3 一b + l ，2 n 3 一m + 2 ，f ( 竹+ 1 0 ) 3 ) 除了当n = 3 a 一9 时 a j 如果a 是奇数a j 是偶数，称( a t ，叼) 是a 的奇偶序对称 两个序对( a i ，a ，) 和( a 。，a t ) 是完全不同的，如果a t a j a 。 a 。o ( a ) 表示a 中完全不同的奇偶序对的最大数目设p m = ”。砚是t 的脊线令 ，= i ：v i y ( f i m ) 且d ( v i ) 3 ) u m ) ， 称，是t 的p 3 集 定理6 设t 是最大度为的n 个顶点的毛虫树，则对于k 3 ，t 可均匀 一着色的充要条件是存在t 的一个顶点。，d ( ”) = ，使得 n l n 划( m - + 1 ) 2 + ( m z + 1 ) 2 + d ( - ) + o ( h ) + ， 其中t n ( v ) 是两个子毛虫树，即脊线为p m 。= ”t 的丑和脊线为p m 。= ” u o v 。i 的马， 和如分别为噩和如的p 3 一集 二分树或者是空的( 没有顶点) ，或者是有一个称为根的点和两个可能是 空的子树，称为左子树和右子树根点到叶子点的最长路的长度定义为二分 树的深度如果二分树的叶子点都在第m 层或第m 一1 层，且第m 层的叶子 点都在左侧，则称为完全二分树如果二分树的叶子点都在第m 层且每个点 都恰好有零个或两个孩子，则称为满二分树 定理7 对于k 之3 ，二分树可均匀一着色 定理8 深度为m 的完全二分树可均匀2 一着色的充要条件是当，n 是奇数 时，2 一。2 1 + 2 ；当m 是偶数时，2 1 2sa 。2 1 ；其中a 。为第 m 层的顶点数 推论9 深度为m 的满二分树可均匀2 一着色的充要条件是m = l 2 设是壹经为4 懿檬，剡瓣去爨接熹及蒸关联懿边后为一个蓬记。为 r 的中心， 2 ， 。为的邻点设a ( v i ) = d i ，i = 1 ，2 ，m ，这样的树表示 为r ( v o ；现，v 2 ，v m ) 或f ( m ；d l ，d 2 ， 定璇1 0 设t = ，( m ；d t ，d 2 ，d m ) 是直径为4 的树，则丁可均匀2 一着色的 兖要条件是0s2 m 一墨。破s2 定璎1 1 设t t ( 2 1 0 ； t ，抛，w 。) 是直径为4 的树，则对于k 3 ，t 可均匀 k 一着色的充要条件是存在丁的一个顶点d ( v t ) = 使得 卟川吲，器地0 其中v 2 * ( 忱：d ( v i ) 2 ，她巩，1 i m ) 令p ( t ) 表示，申悬挂点戆数基，g 表示与褒点够耀邻黪悬挂点酶数 翻， q ( t ) = m i n q ( v ) ：d ( v ) = ( t ) ) 定瓒1 2 设t = t ( x ，y ) 怒直径为4 的树，如果 1 x 卜i y l l 1 ，则 x o ( t ) 一m a z 3 , 岩臻南1 l，、，t 、一，1 “ 关予毛虫橼，绘出了嚣耪计算均匀色数鳇方法。关予树懿均匀k 一蛰色， 23 ，给出了一个算法，并证明了其正确性和时间界 定理1 3 算法e k c 在o ( k 1 x 2 1 y | ) 时闲内给溅树? 的均匀k 一着包，其 中k 3 如果一个图的顶点集可以划分为r 个独立集k ，k ，使得联中的每 个顶点和碥中酶每个溪点均有一边籀连，i j ，葵中r 2 ，冈一i ，i = 1 ，2 ，r ，则称这样的图为完垒r 部圈，记为。，。， 关予完全r 都圈的璃匀k 着色，给出了一个宽要条件扶这个条 串可浚 给出另外的方法证明前人的一些结果，包括完全r ，部图的均匀色数表达式和 m e y e r 猜想对完金r 一郝罂鲍正凌俊， 定理1 4 设。，是黧全r 部图，k 是一个正整数，k ：。7 1 , i ，则 琢。可均匀k 一着色匏充要条件是存在一个正整数嬲使褥 h ( m + 1 ) l n i l m j ，i = 1 ，2 ，r i 并且 rr r n i l ( m + 1 ) 1sk 曼 n i t m j 推论1 5 设m 是满足 ( m + 1 ) l n j m j ( i = l ，2 ，r ) 的最大的整数，则 r ) ( e ( 。，。) = e h ( m + 1 ) 推论1 6 如果k 是正的偶数，则，。可均匀k 一着色 推论1 7 如果k 是正的奇数，则k n ，。可均匀k 一着色的充要条件是 【2 n k js2 n ( m o dk ) k 一【2 n k j 推论1 8 对于= 2 ，3 ，4 ，k n ，。可均匀k 一着色的充要条件是存在一个整数 p ，0 3 a 一8 0 r 嚣= 3 a l o ， a 。k o s t o c h k af 2 唾p r o v e dt h a te v e r yo u t e r p l a n a rg r a p hw i t hm a x i m u m d e g r e ea tm o s ta i se q u i t a b l yk - c o l o r a b l ef o re v e r y 危a 2 + 1 s r i r a mv p e m m a r a j u 【2 7 1s h o wt h a ta n y c o n n e c t e do u t e r p l a n a rg r a p ho nnv e r t i c e sw i t hm a x i m u m d e g r e ea tm o s tn 6i se q u i t a b l y 6 - c o t o r a b l e ，b l c h e na n dk w l i h 【7 】p r o v e dt h ef o l l o w i n gr e s u l tw h i c hd e t e r m i n e s t h es e to fv a l u e s 女s u c ht h a tat r e ei se q u i t a b l yk - c o l o r a b l e l e t 曲f g ) ，c a l l e dt h ei n d e p e n d e n c en u m b e ro fag r a p hg ，d e n o t et h en u m b e ro fv e r - r i c e si nam a x i m u m i n d e p e n d e n t8 e to fg ，a n da ( x ，y ) d e n o t et h eb i p a r t i t eg r a p hw i t h b i p a r t i t i o n ( x ，y ) l e m m a1 1 。1 7 l e tt = t ( x ，y ) b eat r e es u c ht h a t | | x 卜l y l | i ，t h e nti s e q u i t a b l yk - c o l o r a b l e i fa n d o n l yi f m a x 3 ，f ( 1 y ( f ) l + 1 ) ( 穗窜一( 口) ) + 2 ) 1 ，w h e r e ui sa na r b i t r a r yv e r t e xw i t hd ( v 、一 m o t i v a t e db yl e m m a1 1 w eo b t a i no t h e rc o n d i t i o n sf o rw h i c hat r e et i se q u i t a b l y 0 t h e o r e m1 2 l e ttb e 氇t r e eo i lnv e r t i c e sw i t hm a 3 d l m l n ld e g r e e 。t h e n ；f o r 女23 ，ti se q u i t a b l y 走一c o l o r a b l ei fa n do n l yi ft h e r ee x i s t sav e r t e x o ft w i t hd ( 口) = s u c ht h a t 貔( ? 一( w ) ) 【嚣列一l 。 t h e o r e m1 3 。l e tt = r ( x ，y ) b eat r e ew i t h x = n m = ；r t t h e nti s e q u i t a b l yk - c o o r a b l ei f 女f 托( y 托+ 1 ) 1 + 1 。 t h e o r e m1 4 ，i fti sat r e ew i t hm a x i m u m d e g r e e ，t h e nf o ra n yv e r t e x v ( t ) w i t hd 扣) 一，t vi se q u i t a b l y3 - c o l o r a b l e at r e eti sac a t e r p i l l a ri ft v i sap a t hw h i c hi sd e n o t e db y = v t v 2 ， w h e r ev 一 移v ( 秘：矗扣) 一l t h ep a t hj 一 l 强i sc a l l e dt h es p i t t eo ft h e c a t e r p i l l a r s u p p o s et h a td ( v i ) 馥，i = 1 ，2 ，m a l s o ，w em a y d e n o t et h i st r e eb y ，( 壶，d 2 ，d 。) l e t = d i ， ； i s 瓣d 一e 函 t h e o r e m1 , 5 ac a t e r p i l l a rt ( d l ，d 2 ，。，蠡) i se q u i t a b l y2 - c o l o r a b l ei fa n do n l yi f | 一萝i 1f o rm i se v e no r0 鑫7 一扩墨2f o rmi so d d 。 t h e o r e m1 6 。l e tt ( d t ，如，瓠) b e 磊c a t e r p i l l a r0 1 1 露v e r t i c e sw i t hm a x i m u m d e g r e e ，t h e nt i se q u i t a b l yk - c o l o r a b l ef o r 蠢3i f 曼m a 茹 2 犯3 1 一b 十1 ，f 2 n 1 3 1 一，n + 2 ，f ( 札+ 1 0 ) 3 1 e x c e p tt h a t 彤。i f a i i so d da n d i s e v e n ，( 如，) i sc a l l e da no d d - e v e no r d e r e dp a i r 。t w oo r d e r e dp a i r s ，( 啦，) a n d ( ，趣 a r ec o m p l e t e l yd i f f e r e n ti fa i 钧 a # a t d e n o t eb yo ( a ) t h em a x i m u mc a r d i n a l i t y o fs u b s e t so faw h i c ha r ei nt h ec o m p l e t e l yd i f f e r e n to d d - e v e no r d e r e dp a i r s ， l e t 玩2 口l 钍2 b e t h e s p i n eo f8c a t e r p i l l a rt s e t f = 囊：钝e 矿蜀0a n d 窟( ) 3 u m a n d w e s a y j i sa p 3 - s e to f t t h e o r e m1 7 。l e ttb eac a t e r p i l l a ro n 珏v e r t i c e sw i t hm a x i m u md e g r e e t h e n f o r 奄3t i s e q u i t a b l yk - c o l o r a b l ei fa n do n l yi f t h e r ee x i s t sav e r t e xvo ft w i t h d 扣) = ， 摊一l 站捌f ( 十1 ) 2 1 + f 洳2 + 1 ) 2 l 0 ( 聂) + ( ) ( 是) + 8 w h e r et 一( # ) h a st w os u b c a t e r p i l l a r s ，夏w i t ht h es p i n e 焉h = o t v 2 嚣m la n d 霸w i t h t h es p i n ep 2 一 ：u o w 麓，a n dj l a n d 如 r e s p e c t i v e l y ，a r et h ep 3 - s e t so f t ta n d 噩 a b i n a r 。yt r e ei se i t h e re m p t y ( n ov e r t i c e s ) ，o rh a sar o o tv e r t e xv ，t w op o s s i b l ye m p t y s e t st h a ta r eb i n a r yt r e e sc a l l e dl e f ta n dr i g h tb i n a r yt r e eo f w es a yt h er o o ti sa tl e v e l 0 t h ed e p t ho ft h eb i n a r yt r e ei st h el e n g t ho ft h el o n g e s tp a t hf r o mt h er o o tv e r t e xt o a i e a f t h e o r e m1 8 ab i n a r yt r e ei se q u i t a b l yk c o l o r a b l ef o r 芝3 c o m p t e t eb i n a r yt r e ei sab i n a r yt r e ei nw h i c h a l ll e a v e s 躲ea ts o m el e v e imo rm 一1 。 a n da l ll e a v e sa tl e v e lma r et o w a r dt h el e f t ，f u l lb i n a r yt r e ei s & c o m p l e t eb i n a r yt r e ei n w h i c he a c hv e r t e xh a se x a c t l yz e r oo rt w oc h i l d t e n t h e o r e m1 9 ac o m p l e t eb i n a r yt r e ew i t hd e p t hm i se q u i t a b l y2 - c o l o r a b l ei fa n d o n l yi f2 m 一1 a ms 2 “一1 + 2w h e nm i so d d ，o r2 m 一1 2sa m 2 ”1w h e nm i se v e n ， w h e r ea mi st h en u m b e ro fv e r t i c e si nl e v e lm 。 c o r o l l a r y1 1 0 。af u l lb i n a r yt r e ew i t hd e p t hm i se q u i t a b l y2 - c o l o r a b l ei fa n d o n l y i f m = 1 s u p p o s et h a tt i sat r e ew i t hd i a m e t e r4 l e tv 一 ：口v ( t ) a n dd ( v ) 一1 ， t h e n t v i s a s t a r ，d e n o t e b y v 0 t h e u n i q u e c e n t e ro f t ，a n d 甜l ，v 2 ， m t h e n e i g h b o r s o f o 。s u p p o s et h a t 症( 弼) = 哦，i = 1 ，2 ，m 。w ed e n o t et h i st r e eb yt ( v o ；v l ，啦，口m ) o rt ( m ；d l ，d 2 ，d m ) t h e o r e m1 1 1 l e tt 一丁( m ；d l ，如”，d m ) b eat r e ew i t hd i a m e t e r4 t h e nt i s e q u i t a b l y2 - c o l o r a b t e i fa n d o n l yi f0 2 m 一銎i 杰冬2 + t h e o r e ml 。1 2 。l e tt # t ( v 。；口l ，v 2 ，蛰m ) b eat r e ew i t hd i a m e t e r4 。t h e nt i s e q u i t a b l y 一c o l o r a b l ef o r 3i fa n do n l y i ft h e r ee x i s t sav e r t e x 巩o ftw i t hd ( v t ) = s u c ht h a t 一l n l k j 会+ 吲，：t f 融v , = 妇v o ，, w h e r e = f 姚：d ( v i ) 2 ，钝雷b 1 i m l e tp ( t ) d e n o t et h en u m b e ro fl e a v e si nat r e et ，q ( v ) d e n o t et h en u m b e r o fl e a v e s a d j a c e n tt ot h ev e r t e x 口，a n d q ( t ) = m i n q ( v ) ：蠢移) = 霸 t h e o r e m1 1 3 l e tt = t ( x ，y ) b e at r e ew i t hd i a m e t e r4 i f1 i x 卜i y | 1 ，t h e n 蒯国，f 岩鞴强 f o rc a t e r p i l l a r s ，w ep r o v i d et w ow a y st oc a l c u l a t ee q u i t a b l ec h r o m a t i c n u m b e r ，f o r e q u i t a b l yk - c o l o r i n g 3 ) t r e e s ，w ed e s c r i b e a na l g o r i t h ma n dd e t e r m i n e t h ec o r r e c t n 8 s 8 a n dt h ec o m p l e x i t yo ft i f f sa l g o r i t h m 。 7 t h e o r e ml 。1 4 。a g o r i t l l me k c c o r r e c t l ys o l v e st h ee q u i t a b l ek - c o l o r i n gp r o b l e m ( 3 ) f o ra t r e eti no ( k | x f t y | ) t i m e a g r a p hi sc a l l e dac o m p l e t er p a r t i t eg r a p h ，d e n o t e db yk m ，i fi t sv e r t e xs e t o & bb ep a r t i t i o n e di n t o ，i n d e p e n d e n ts e t s 巧j ；：j 蟛s u c ht h a te v e r yv e r t e xi nki s j o i n e dt oe v e r yv e r t e xi n 码，i j ，w h e r er 2 ，l 磁l 一瑰1 ，i = 1 ，2 ，7 ， f o re q u i t a b l ek - c o l o r i n go fc o m p l e t er p a r t i t eg r a p h s ，w ed e t e r m i n eas u f f i c i e n ta n d n e c e s s a r yc o n d i t i o nf r o mt h i sr e s u l t w em a yp r o v i d ea n o t h e rw a yt od e d u c es o m e p r e v i o u sr e s u l t s ，i n c l u d i n gt h ee x p l i c i tf o r m u l af o rt h ee q u i t a b l ec h r o m a t i cn u m b e ro f c o m p l e t e7 - p a r t i t eg r a p h sf 1 0 】a n dt h ep r o o fo fm e y e r sc o 瑙e e t u r ef o rc o m p l e t er p a r t i t e g r a p h s 【l a ， t h e o r e m 2 1 l e t 2 h ，b eac o m p l e t er p a r t i t eg r a p h ，a n d b eap o s i t i v e i n t e g e rw i t h ：1n i t h e n 。n ，i se q u i t a b l yk - e o l o r a b l ei fa n do n l yi ft h e r e e x i s t sa p o s i t i v ei n t e g e rm s u c ht h a t n j ( m + 1 ) 1 【n , m j f o r i 一1 ，2 ，r rr n d ( m + 1 ) 1s 缸曼 n j m l 赫】l = l c o r o l l a r y2 2 s u p p o s em i st h el a r g e s ti n t e g e rs u c ht h a t f n i ( m + 1 ) 1 n i m j f o r i 一1 ，2 ，r 地( 赫。，罅，卜h ( m 十1 ) 1 i = l c o r o l l a r y 2 3 i f 惫i sap o s i t i v ee v e nn u m b e r ，t h e n 。i se q u i t a b l yk - c o l o r a b l e c o r o l l a r y 2 4 + l fki sap o s i t i v eo d dn u m b e r ，t h e n 磁mi se q u i t a b l yk - c o t o r a b l ei f a n do n l y i f 【2 n k 2 n l m o d 七) k 一【2 n k j c o r o l l a r y2 5 。f o r 凳= 2 ，3 ：4 ，甄l 懈i se q u i t a b l y 一c o l o r a b l ei fa n do n l yi ft h e r e e x i s t sa n i n t e g e r p ，0 3 a 一8o rn = 3 a 一1 0 a k o s t o c h k a 【2 6 p r o v e dt h a te v e r yo u t e r p l a n a rg r a p hw i t hm a x i m u m d e g r e ea tm o s ta i s e q u i t a b l yk - c o l o r a b l ef o re v e r y 七2 + 1 s r i r a mvp e m m a r a j uf 2 7 s h o w e dt h a ta n y c o n n e c t e do u t e r p l a n a rg r a p ho nnv e r t i c e sw i t hm a x i m u m d e g r e ea tm o s tn 6j se q u i t a b l y 6 - c o l o r a b l e b l c h e na n dk w l i bf 7 1d e t e r m i n e dt h es e to fv a l u e s s u c ht h a tat r e e i se q u i t a b l y 一c o l o r a b l e e q u i t a b l ec o l o r i n gt h e o r yh a saw i d er a n g eo fa p p l i c a t i o n si nr e a l w o r l d f o re x a m p l e v e r t i c e sr e p r e s e n tg a r b a g ec o l l e c t i o nr o u t e sa n dt w os u c hv e r t i c e sw e r e1 0 i n e dw h e nt h e c o r r e s p o n d i n g r o u t e ss h o u l dn o tb er u no nt h es a n ed a y t h e p r o b l e mo fa s s i g n i n go n eo f t h es i xd a y so ft h ew o r kw e e kt oe a c hr o u t e sb e c o m e st h ep r o b l e mo f 6 - c o l o r i n gt h eg r a p h s u c ht h a tn oe d g ej o i n sv e r t i c e so ft h es a l n ec o l o r o np r a c t i c a lg r o u n d s i tm a ya l s ob e d e s i r a b l et oh a v ea na p p r o x i m a t e l ye q u a ln u m b e ro fr o u t e so ne a c ho ft h es i xd a y s t h i s i sa ne q u i t a b l y6 - c o l o r i n g p r o b l e m 1 2 c o n c e p t sa n dt e r m i n o l o g y i nt h i s s e c t i o n ，w er e p r o d u c es o m en o t a t i o n sa n dd e f i n i t i o n s f o rd e t a i l s ，s e e 1 t h r o u g h o u t t h i sp a p e r ，g r a p h sa r ea s s u m e dt ob e n o n - n u l l ，s i m p l e ，f i n i t e ，a n du n d i r e c t e d f o ra g r a p h g ，w e u s et h es y m b o l s y ( g ) ，e ( g ) ，i v ( a ) la n dl e ( c ) | r e s p e c t i v e l y ，t od e n o t e t h ev e r t e xs e t ，e d g e8 e t ，t h en u m b e ro fv e r t i c e sa n de d g e s t h en u m b e ro fe d g e si ng i n c i d e n tw i t hav e r t e x i sc a l l e dt h ed e g r e eo fu ，a n di sd e n o t e db yd ( ) a ( a ) = m a x d ( v ) ：u y ( g ) ) i s t h em a x i m u m d e g r e eo fg s u p p o s et h a tsi s an o n e m p t ys u b s e to fv f g l g si su s e dt od e n o t et h ei n d u c e d s u b g r a p ho b t a i n e df r o mgb yd e l e t i n gt h ev e r t i c e s i nst o g e t h e rw i t ht h e i ri n c i d e n t e d g e s t h ec l o s e dn e i g h b o rs e to fsi ng ，d e n o t e db y ( 鳓，c o n s i s t so fa l lv e r t i c e si n sa n da 1 1t h e i ra d j a c e n tv e r t i c e s t h en e i g h b o rs e to fs ，d e n o t e db y j ( s ) ，i s ( s ) s i fs = 口) ，w ew r i t eg ( v ) f o r ( ) ) a n dn 0 ( u ) f o r 0 ( ) ) as u b s e tso fv ( a ) i s c a l l e da ni n d e p e n d e n ts e to fgi fn ot w ov e r t i c e so fsa r ea d j a c e n ti ng t h en u m b e r o fv e r t i c e si nam a x i m u m i n d e p e n d e n ts e to fg i sc a l l e dt h ei n d e p e n d e n c en u m b e ro fg ， a n di sd e n o t e db y 口( g ) ab i p a r t i t eg r a p hgw i t hb i p a r t i t i o n ( x ，y ) i so f t e ne x p r e s s e d a sc ( x ，y ) ac o m p l e t eb i p a r t i t eg r a p hi sd e n o t e db y 纸 as u b s e tko fv ( a 1s u c ht h a te v e r ye d g eo fgh a sa tl e a s to n ee n di nki sc a l l e da c o v e r i n go fg ，a n dt h en u m b e ro fv e r t i c e si nam i n i m u mc o v e r i n go fg ，d e n o t e db y 卢( g ) ， i st h ec o v e r i n gn u m b e ro fg a ne d g ec o v e r i n go fgi sas u b s e tco fe ( g 1s u c ht h a te a c h v e r t e xo fgi sa ne n do fs o m e e d g ei nc a s u b s e tmo fe ( a 1i sc a l l e dam a t c h i n gi ng i fi t se l e m e n t sa r ee d g e sa n dn ot w oa r ea d j a c e n ti ng a nm a l t e r n a t i n gp a t hi sap a t h w h o s ee d g e sa r ea l t e r n a t e l yi ne ma n dm a nm a u g m e n t i n gp a t hi sa nm a l t e r n a t i n g 1 0 p a t hw h o s eo r i g i na n dt e r m i n u sa r ei n c i d e n tw i t hn oe d g eo fm l e tma n dnb et w o s u b s e t so fe ( g ) ，a n dt h es y m m e t r i cd i f f e r e n c eo fm a n dni sd e n o t e db y m a n = ( m u ) ( m n n ) t h ed i a m e t e ro fgi st h em a x i m u md i s t a n c eb e t w e e nt w ov e r t i c e so fg w eu s eix la n d i z l t od e n o t e ，r e s p e c t i v e l y ，t h el a r g e s ti n t e g e rn o tg r e a t e rt h a noa n dt h es m a l l e s ti n t e g e r n o t1 e s st h