幾類圖的(排斥)下整和數(shù).pdf

1、本文僅考慮有限無(wú)向簡(jiǎn)單圖，所用圖論基本術(shù)語(yǔ)與符號(hào)遵循文獻(xiàn)[1]． 1990年Haray[2]提出和圖的概念．1994年Harary[3]提出整和圖的概念．令N(Z)表示正整數(shù)(整數(shù))集，N(Z)的非空有限子集S的(整)和圖G+(S)是圖(S，E)，其中uv∈E當(dāng)且僅當(dāng)u+v∈S．—個(gè)圖G稱為(整)和圖，若它同構(gòu)于某個(gè)S()N(Z)的(整)和圖，此時(shí)我們說(shuō)S給出了G的一個(gè)(整)和標(biāo)號(hào)，并且將頂點(diǎn)與其標(biāo)號(hào)不加區(qū)分．G的(整)和數(shù)σ(

2、G)(ζ(G))是使得G∪nK1是(整)和圖的非負(fù)整數(shù)n的最小值． 2005年Miller等人[4]提出排斥圖的概念．圖G∪nK1的(整)和標(biāo)號(hào)S稱為排斥的(exclusive)，若uv∈E(G)當(dāng)且僅當(dāng)u+v∈S\V(G)．圖G的排斥(整)和數(shù)ε(G)(ζ'(G)是使得G∪nK1有排斥(整)和標(biāo)號(hào)的非負(fù)整數(shù)n的最小值． 2006年，李敏等人璐[5]提出下整和圖的概念，令Q*表示正有理數(shù)集．Q*的非空有限子集S的下整和圖

3、G+(S)是圖(S，E)，其中uv∈E當(dāng)且僅當(dāng)[u+c]∈S．—個(gè)圖G稱為下整和圖，若它同構(gòu)于某個(gè)S()Q*的下整和圖，我們說(shuō)S給出G的一個(gè)下整和標(biāo)號(hào)，并且頂點(diǎn)與其標(biāo)號(hào)不加區(qū)分，下整和數(shù)σ(G)是使得G∪nK1是下整和圖的非負(fù)整數(shù)n的最小值． 圖G∪nK1的下整和標(biāo)號(hào)S稱為排斥的(exclusive)，若uv∈E(G)當(dāng)且僅當(dāng)[u+v]∈S\V(G)．圖G的排斥下整和數(shù)ε1(G)是使得G∪nK1有排斥下整和標(biāo)號(hào)的非負(fù)整數(shù)n的最小

4、值． 2007年竇文卿等人[8]提出模整和圖的概念，模整和圖是取S(){0，1，2，…，m-1)，且所有算術(shù)運(yùn)算均取模m(≥|S|)的和圖，一個(gè)圖G的模整和數(shù)ψ(G)是使得G∪nK1是模整和圖的非負(fù)整數(shù)n的最小值． 從實(shí)用的觀點(diǎn)來(lái)看，各種和圖標(biāo)號(hào)都可被計(jì)算機(jī)用作圖的壓縮表示．當(dāng)利用它們來(lái)工作時(shí)，不僅可以節(jié)省內(nèi)存，還可以加快某些圖算法的運(yùn)算速度， 在本文的第一章中，我們主要介紹了文章中所涉及的一些概念、術(shù)語(yǔ)、符號(hào)；

5、在第二章中我們稱圖(V，E)(其中V={α1，α2，b1，b2，…，bn，c1，c2]，E={α1α2，c1c2，α1b1，c1bi|i=1，2，…，n})為燈籠，稱去掉懸掛點(diǎn)α2的圖為殘燈籠：稱將n個(gè)K3，m個(gè)K2的各一個(gè)點(diǎn)粘合在一起所得的圖為風(fēng)車，K2的邊叫其柄：稱由具有一個(gè)公共端點(diǎn)的三條路Pm，Pn，Pl組成的圖為三路樹(shù)，記作P(m，n，t)；稱圖Cn2=(V，E)(其中n≥3，V={α1，α2，…，αn，c}，E={α1α2.α