和圖論與分數(shù)圖論的若干結(jié)果.pdf

1、I駔位代碼10445學號20021330分類弓Ol576彥緣街缸大學y764187碩士學位論文論文題目和圖論與分數(shù)圖論的若干結(jié)果i1浦人姓名導(dǎo)師姓名論文提交時間應(yīng)用數(shù)學王斑糶觥教孥2005年4月蘆日一生壅垣整盔蘭巫主堂焦迨塞l和圖論與分數(shù)圖論的若干結(jié)果王海棠(山東師范大學數(shù)學科學學院，濟南，山東，250014)中文摘要本文主要從甄方面研究圖并取得了一些結(jié)果本文的第一部分研究和圖1990年Harary[1】提出了和圖的概念，從而開始了對利

2、圖的研究令v(c)表示圖G的頂點集合，1SI表示集合s中元素的個數(shù)令N(z)表示正整數(shù)(整數(shù))集，N(Z)的非空有限子集s的和圖G(s)是圖(sF)其tlttl!∈E當且僅當u“∈s；一個圖G稱為(整)和圖，若它同構(gòu)于某個s(_』、(z)f0和圈(整)和數(shù)一(G)((G))是使得Gu，；K，是(整)和圖的非負整數(shù)”的最小值1121_慎和圖是取ScZ。＼O)且所有算術(shù)運算均取模m(2lSl1)的和圖一個圖C的模和數(shù)p(G)是使得GupKl

3、是模和圖的孤立點數(shù)P的最小值m圖GunKiIn(懿)f11甄號S稱為排斥的(exclusive)，若對每條邊“u∈E(G)，u—tⅧ∈s＼17(G)Gn0IIJi耵l數(shù)i(G)是使GunKL有排斥和標號的非負整數(shù)，t的最小值㈨從實11lflJ觀點來看，和圖標號可用作圖的壓縮表示，即表示圖∞數(shù)擗結(jié)黝當利川輸入圖f|J壓縮表示來工作時，數(shù)據(jù)壓縮不僅可以節(jié)省內(nèi)存，還可以』JII快某些l到算法的運算速度目前對和圖的研究主要是從一些特殊圖類著手，

4、確定它們的和數(shù)、怪干數(shù)與飲干數(shù)迄今為止，已經(jīng)取得了許多成果在第二章我們研究了圖的并及竹十吲類的排斥和數(shù)；在第三章中，我們主要研究K。一E(t‘№)的干數(shù)、整卻1數(shù)以／支擻fll數(shù)，1ifiJ定了剖分輪1％，和剖分扇E。、L的和數(shù)我們主要得到如下定理定理211設(shè)圖Gl，G2是圖，L。是G。gE(c，)Kl的排斥和標號，G是其n0孤訕氣集(i=1，2)，且lnaxCl與min島互質(zhì)，則E(GlUG2)曼￡(G1)E(G2)一1推論211設(shè)G