【摘要】：圖的鄰點可區(qū)別均勻V-全染色(AVDEVTC)是指在滿足鄰點可區(qū)別V-全染色的基礎(chǔ)上,還要保證每種顏色的使用次數(shù)相差不超過1,把完成AVDEVTC所用的最少顏色稱為圖的鄰點可區(qū)別均勻V-全色數(shù)(AVDEVTCN)。針對圖的AVDEVTC問題,提出了一種基于多目標(biāo)優(yōu)化的染色算法。設(shè)計了一個總目標(biāo)函數(shù)和四個子目標(biāo)函數(shù),在染色矩陣上通過每個點的顏色集合的迭代交換操作,使得每個子目標(biāo)函數(shù)都達到最優(yōu),進而滿足總目標(biāo)函數(shù)的要求,完成染色。經(jīng)過理論分析和實驗對比表明,8個頂點以內(nèi)的所有簡單連通圖都存在AVDEVTC,且圖的AVDEVTCN介于最大度加1與最大度加2之間。實驗結(jié)果表明,該染色算法能夠在較短的時間內(nèi)正確地計算出1 000個頂點以內(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é)基金資助項目(11461038,61163010,61163037) 蘭州交通大學(xué)青年基金資助項目(2016014)~~
【分類號】：O157.5

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：2479029