修改一类G着色图的一个算法.pdf

维普资讯 第 18卷第 3期 天 津 理 工 学 院 学 报 Vo1．18No．3 JOURNALOFTIANJIN INSTITUTE OFTECHNOLOGY Sept．2002 2002年 9月 文章编号 ：1004 2261(2002)03—055—04 Algorithm thatmodifiesakindofG coloredgraph DIYan-jun (TheKanuanno．1middleschoolinTangshaninHebei，Hebei063000，China) Abstract：InthispapergivesanalgorithmtomodifyGcoloredgraph，andproVethatthe( +1)一 thcOlored graphobtained bythen—th iteration mustbedifferentfrom anyofthe colored graphs,andthattheiterationofthealgorithm withtwosamecomponentscan’tperform infinitly· Keywords：simpleplanargraph；subgraph；continouscycling 修改一类 G着色图的一个算法 狄艳军 (河北省唐山市开滦一中，河北 063000) 摘要 ：给 出了修改一类 G着色图的一算法 ，并证明了通过第 n次循环获得 的G—Vo的第n+ 1个着色图一定不 同于前 n个G—Vo的着色图中的任何一个 ，和具有两个 同一分支的连续循 环过程不可能无休止地进行下去 ． 关键词 ：简单平面图；子 图 连续循 环 中图分类号 ：O157．5 文献标识码 ：A verticeswith thesamecoloraredenoted l， 2 Supposition 1 IfVoisavertex which hasbeen colored innoorder，seefigure1，and 2， 2liesonboth withred isavertexwhich hasbeen coloured sidesofthepath( 1，vo， 1)，and(seefigure with black，W e suppose V isthe setofvertex 2)， l， lliesonbothsidesofthepath( 2， coloredwithredorblackinG(weassumeG be 、，0， v2)[，see figure 3，The restvertex is simpleplanargraph[J1IfsubgraphofG hasV as ． denotedby ，seefigure4． itsvertex set。and alltheverticesofitsedge set Note r：red Y=yellow b=black W belong to V ，then thesubgraph【。Jiscallgenerated wh；te byV ，anddenotedby 6． Supposition2 2 Let、，n∈G，Wemaydenotebyd(vo) degreesofvertexvo．Ifd(Vo)=5andfourcolors， thefiveverticeswhich are adjacentto are assignedtowemaydenotebyVl，V2，V3，V4，V5 Fig．1 The