圖的邊加權(quán)頂點(diǎn)著色.pdf

《圖的邊加權(quán)頂點(diǎn)著色.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、?aò:—?:UDC:?ò:????>o:Xúx?“6?:M~“￡?¤àó’?????O:a??‰!;’??:A^ê???J?m:2011c11??‰F?m:2011c12???ü:àó’??‰F”?ìR:μ<:2011c12DissertationSubmittedtoHebeiUniversityofTechnologyforTheMasterDegreeofScienceinAppliedMathematicsVERTEX-COLORINGEDGE-WEIGHTINGSOFGRAPHSbyliYunyunSuper

2、visor:Prof.XuChangqingDec2011àó’??a?????>o:Xúá?w′é?Gk->D,w:E(G)!f1;2;


;kg.é??Pv2V(G),??ù>Y?fw(v)=v2ew(e),K>Dw?±???o:Xúfw:V(G)!N.XJé??uv2E(G)?kfw(u)6=fw(v),K??G#Nk->o:Xú.?GNNk->o:Xú?k???G>o:Xúê,P?(G).?(??ü?úü?nü?A??>o:Xúê.'…i:o:Xú,>o:Xú,?ü?i?>

3、o:XúVERTEX-COLORINGEDGE-WEIGHTINGSOFGRAPHSABSTRACTAk-edge-weightingofgraphGisamappingw:E(G)!f1;2;


;kg.Anedge-weightingwinducesavertexcoloringfw:V(G)!N,wherePfw(v)=v2ew(e)foreachv2V(G).Furthermoreiffw(u)6=fw(v)foranyedgeuv2E(G),wesaythatGadmitsavertex-coloringk-edge-weighting.

4、TheminimumkforwhichGadmitsavertex-coloringk-edge-weightingisdenotedby(G).Theexactvaluesof(G)forsomeclassesofgraphs,includingcompletemultipartitegraph,sometripartitegraphsaredeterminedinthispaper.KEYWORDS:vertexcoloring,vertex-coloringedge-weighting,completemultipartitegraphiià

5、ó’??a????81￥?á?........................................................................i=?á?........................................................................ii?ò`2.......................................................................iv1?ùX?..............................

6、.....................................1x1