本論文主要研究2-邊染色與2-弧染色重載費用歐拉回路問題。對2-邊染色重載費用歐拉回路問題,具體描述如下:給定一個2-邊染色歐拉圖G=（V,E）,染色函數(shù)c:E→{1,2},重載費用函數(shù)r:{1,2} × {1,2}→R+0,其中r11 = r22 = 0,要尋找圖G的一條歐拉回路PP,目標(biāo)是使得歐拉回路P的重載費用r（P）達(dá)到最小,這里對歐拉回路P=（v0,e1,v1,...,em,V0）,歐拉回路P的重載費用規(guī)定為r（P）= rc（em）c（e1）+∑i=1m-1rc（ei）c（ei+1）°對2-弧染色重載費用歐拉回路問題,具體描述如下:給定一個2-弧染色歐拉圖D =（V,A）,染色函數(shù)c:A →{1,2},重載費用函數(shù)r:{1,2} × {1,2}→R+0,其中r11 =0,要尋找圖D的一條有向歐拉回路P,目標(biāo)是使得有向歐拉回路P的重載費用r（P）達(dá)到最小,這里對有向歐拉回路P＝（v0,a1,v1,...,am,v0）,有向歐拉回路P的重載費用規(guī)定為r（P）＝rc（am）c（a1）+ ∑i=1m-1rc（ai）c（ai+1）°本論文主要得到兩個結(jié)果:（1）當(dāng)重載費用滿足對稱性時,... 

【文章來源】：云南大學(xué)云南省 211工程院校

【文章頁數(shù)】：54 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 引言
    1.1 理論背景
    1.2 問題來源
    1.3 主要結(jié)果
    1.4 論文結(jié)構(gòu)
第二章 預(yù)備知識
    2.1 圖論基礎(chǔ)知識
    2.2 基本問題及算法
第三章 重載費用歐拉回路問題及算法設(shè)計
    3.1 2E-RCETP問題及算法設(shè)計
    3.2 2A-RCETP問題及算法設(shè)計
    3.3 算例
結(jié)論
附錄
參考文獻(xiàn)
致謝



本文編號：3197005