圖的標(biāo)號(hào)和圖的分解問題研究.pdf

1、圖的標(biāo)號(hào)問題起源于1967年A.Rosa的著名優(yōu)美樹猜想。一個(gè)圖的頂點(diǎn)標(biāo)號(hào)是圖的頂點(diǎn)集到整數(shù)集的映射，邊標(biāo)號(hào)是圖的邊集到整數(shù)集的映射，根據(jù)對(duì)映射的不同要求產(chǎn)生了各種類型的標(biāo)號(hào)問題。至今為止，有關(guān)圖的標(biāo)號(hào)問題的文章不下千余篇。(d，1)-全標(biāo)號(hào)和強(qiáng)優(yōu)美標(biāo)號(hào)是圖的標(biāo)號(hào)研究中較典型的內(nèi)容，特別是近幾年，它們被廣泛的應(yīng)用于頻道分配、射電天文學(xué)、x-射線衍射晶體學(xué)、密碼學(xué)、通訊網(wǎng)絡(luò)編址、導(dǎo)彈控制編碼設(shè)計(jì)、同步機(jī)碼設(shè)計(jì)等領(lǐng)域。本文的第一部分對(duì)(d，

2、1)-全標(biāo)號(hào)和優(yōu)美標(biāo)號(hào)做了一些研究和討論。
　　 圖的分解問題起源于組合學(xué)中最經(jīng)典的幾個(gè)問題，如Kirkman15個(gè)學(xué)校女生問題，歐拉的36個(gè)軍官問題等等。隨著圖論逐漸發(fā)展成為比較系統(tǒng)的一門學(xué)科之后，人們逐漸發(fā)現(xiàn)許多組合問題都與圖的分解問題有聯(lián)系。人們?cè)谘芯繄D的分解問題時(shí)，發(fā)現(xiàn)代數(shù)方法中如設(shè)計(jì)理論、置換以及群論也是解決圖分解問題的一種很好的方法。圖分解的結(jié)論可應(yīng)用于密碼理論，實(shí)驗(yàn)設(shè)計(jì)，X-射線衍射晶體學(xué)，計(jì)算機(jī)與通訊網(wǎng)絡(luò)等其它領(lǐng)