【摘要】：圖的鄰點(diǎn)可區(qū)別均勻V-全染色(AVDEVTC)是指在滿足鄰點(diǎn)可區(qū)別V-全染色的基礎(chǔ)上,還要保證每種顏色的使用次數(shù)相差不超過1,把完成AVDEVTC所用的最少顏色稱為圖的鄰點(diǎn)可區(qū)別均勻V-全色數(shù)(AVDEVTCN)。針對圖的AVDEVTC問題,提出了一種基于多目標(biāo)優(yōu)化的染色算法。設(shè)計(jì)了一個(gè)總目標(biāo)函數(shù)和四個(gè)子目標(biāo)函數(shù),在染色矩陣上通過每個(gè)點(diǎn)的顏色集合的迭代交換操作,使得每個(gè)子目標(biāo)函數(shù)都達(dá)到最優(yōu),進(jìn)而滿足總目標(biāo)函數(shù)的要求,完成染色。經(jīng)過理論分析和實(shí)驗(yàn)對比表明,8個(gè)頂點(diǎn)以內(nèi)的所有簡單連通圖都存在AVDEVTC,且圖的AVDEVTCN介于最大度加1與最大度加2之間。實(shí)驗(yàn)結(jié)果表明,該染色算法能夠在較短的時(shí)間內(nèi)正確地計(jì)算出1 000個(gè)頂點(diǎn)以內(nèi)的圖的AVDEVTCN。
[Abstract]:The adjacent point of the graph can be distinguished from uniform V-full dyeing (AVDEVTC), which means that on the basis of satisfying the distinguishing V-full dyeing of the adjacent points, it is also ensured that the number of use times of each color is not more than 1, and the minimum color used for completing the AVDEVTC is called the adjacent point of the map to be distinguished from the uniform V-panchromatic number (AVDEVTCN). In order to solve the problem of AVDEVTC, a dyeing algorithm based on multi-objective optimization is proposed. A total objective function and four sub-objective functions are designed, and the iterative switching operation of the color set of each point is performed on the dyeing matrix, so that each sub-objective function is optimal, and the requirements of the total objective function are met, and the dyeing is finished. The theoretical analysis and experimental comparison show that the AVDEVTC exists in all simple communication graphs within 8 vertexes, and the AVDEVTCN of the graph is between the maximum and the maximum of 2. The experimental results show that the algorithm can correctly calculate the AVDEVTCN of the graph with less than 1,000 vertexes in a short time.
【作者單位】： 蘭州交通大學(xué)電子與信息工程學(xué)院;蘭州交通大學(xué)應(yīng)用數(shù)學(xué)研究所;
【基金】：國家自然科學(xué)基金資助項(xiàng)目(11461038,61163010,61163037) 蘭州交通大學(xué)青年基金資助項(xiàng)目(2016014)~~
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 盧建立;任鳳霞;馬美琳;;中間圖的鄰點(diǎn)強(qiáng)可區(qū)別全染色[J];河南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年05期

2 馬生全,張忠輔,姚兵,李敬文;C_(3n)~2,C_(4n)~2鄰點(diǎn)可區(qū)別的全染色[J];蘭州鐵道學(xué)院學(xué)報(bào);2003年04期

3 李敬文;強(qiáng)會(huì)英;張忠輔;王文杰;王治文;;高度圖的鄰點(diǎn)可區(qū)別的全染色界的一點(diǎn)注[J];蘭州交通大學(xué)學(xué)報(bào);2006年01期

4 王顏妮;王麗偉;劉萍;;幾類圖的鄰點(diǎn)可區(qū)別的全染色[J];科學(xué)技術(shù)與工程;2007年13期

5 王雅琴;劉西奎;王英;;一些圖的鄰點(diǎn)可區(qū)別關(guān)聯(lián)著色[J];大學(xué)數(shù)學(xué);2008年04期

6 劉海濤;;C_(5m)×C_(5n)圖的鄰點(diǎn)可區(qū)別的邊染色[J];河西學(xué)院學(xué)報(bào);2008年02期

7 卞西燕;苗連英;尚華輝;段春燕;馬國翼;;圖的鄰點(diǎn)可區(qū)別邊劃分(英文)[J];華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年04期

8 鄭純;劉煥平;;扇和輪的鄰點(diǎn)強(qiáng)可區(qū)別全染色[J];哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào);2009年05期

9 嚴(yán)謙泰;;k-方圖的一般鄰點(diǎn)可區(qū)別邊染色[J];安徽大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年03期

10 嚴(yán)謙泰;嚴(yán)楷;;關(guān)于圖的一般鄰點(diǎn)可區(qū)別邊染色[J];數(shù)學(xué)的實(shí)踐與認(rèn)識;2010年24期

相關(guān)會(huì)議論文 前3條

1 李莉;耿顯民;;一類隨機(jī)圖的鄰點(diǎn)度數(shù)和[A];第十一屆中國不確定系統(tǒng)年會(huì)、第十五屆中國青年信息與管理學(xué)者大會(huì)論文集[C];2013年

2 曹淵;郭永輝;王鐵良;田宙;;自然鄰點(diǎn)插值方法在材料狀態(tài)方程數(shù)據(jù)庫開發(fā)中的應(yīng)用[A];中國計(jì)算力學(xué)大會(huì)'2010（CCCM2010）暨第八屆南方計(jì)算力學(xué)學(xué)術(shù)會(huì)議（SCCM8）論文集[C];2010年

3 劉君;趙傳成;任志國;包世堂;李敬文;張忠輔;;C_m·F_n的鄰點(diǎn)可區(qū)別的邊染色[A];中國運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

相關(guān)博士學(xué)位論文 前2條

1 孔海榮;區(qū)組長為4的二維不含鄰點(diǎn)的平衡樣本設(shè)計(jì)[D];河北師范大學(xué);2008年

2 黃丹君;平面圖的鄰點(diǎn)可區(qū)別染色與點(diǎn)蔭度[D];蘇州大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 馬瑞瓊;復(fù)雜網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)算法的研究[D];電子科技大學(xué);2015年

2 焉秋瑤;圖的廣義字典積與半強(qiáng)積的鄰點(diǎn)可區(qū)別和點(diǎn)可區(qū)別染色[D];西北民族大學(xué);2015年

3 張彩霞;幾類圖的鄰點(diǎn)可區(qū)別均勻E-全染色[D];蘭州交通大學(xué);2015年

4 王立麗;關(guān)于幾類圖的Smarandachely鄰點(diǎn)全染色[D];蘭州交通大學(xué);2015年

5 鄧衛(wèi)東;圖的Cartesian積與合成的鄰點(diǎn)可區(qū)別E-全染色[D];西北師范大學(xué);2015年

6 劉配配;平面圖的非正常染色[D];浙江師范大學(xué);2015年

7 黃晨悅;一類區(qū)組長為5的一維不含鄰點(diǎn)的平衡樣本設(shè)計(jì)的存在性[D];河北師范大學(xué);2016年

8 李曉麗;區(qū)組長為5的二維不含鄰點(diǎn)的平衡樣本設(shè)計(jì)[D];河北師范大學(xué);2016年

9 張曉望;平面圖的邊染色問題[D];山東大學(xué);2016年

10 聶靜方;平面圖的非正常染色[D];浙江師范大學(xué);2016年

，

本文編號：2479029