数学的实践与认识
數學的實踐與認識
수학적실천여인식
MATHEMATICS IN PRACTICE AND THEORY
2011年
13期
159-162
,共4页
嵌入%超图%PTAS
嵌入%超圖%PTAS
감입%초도%PTAS
H为定义在圈G上的一个超图,将H的每条超边映射为圈G中不同的路,并且这条路包含此超边中的所有的顶点,此问题称为超边在圈G中的嵌入问题(MCHEC问题).超图在圈中的嵌入问题即为寻找H在G中的最优嵌入使得G中任一边被H所有超边的嵌入经过的最大次数最小.应用组合最优化以及概率方法可得到MCHEC问题的PTAS算法.
H為定義在圈G上的一箇超圖,將H的每條超邊映射為圈G中不同的路,併且這條路包含此超邊中的所有的頂點,此問題稱為超邊在圈G中的嵌入問題(MCHEC問題).超圖在圈中的嵌入問題即為尋找H在G中的最優嵌入使得G中任一邊被H所有超邊的嵌入經過的最大次數最小.應用組閤最優化以及概率方法可得到MCHEC問題的PTAS算法.
H위정의재권G상적일개초도,장H적매조초변영사위권G중불동적로,병차저조로포함차초변중적소유적정점,차문제칭위초변재권G중적감입문제(MCHEC문제).초도재권중적감입문제즉위심조H재G중적최우감입사득G중임일변피H소유초변적감입경과적최대차수최소.응용조합최우화이급개솔방법가득도MCHEC문제적PTAS산법.
