最大平面圖中哈密頓圈的計算機輔助分析
COMPUTER AIDED ANALYSIS OF HAMILTONIAN CYCLES IN MAXIMUM PLANAR GRAPHS
-
摘要: 本文提出了一個遞推算法,可用來產(chǎn)生某種類型的最大平面圖的全部哈密頓圈。對于Wagner型圖,計算結(jié)果可用下式表示: M(p)=6+4(p-5),5p20其中,p為該型最大平面圖的階(點數(shù)),M(p)是p階圖中哈密頓圈的個數(shù)。文中還給出了一個定理,證明了算法的正確性。
-
關(guān)鍵詞:
Abstract: A recursive algorithm for generating all hamiltonian cycles in maximum planar graphs of certain type has been proposed. For wagner graphs, the computed results may be represented by the following formula: M(p) =6+4(p-5), 5 p 20 where p is the order of the graph and M (p) is the total number of hamiltonian cycles. A theorem has been given and the correetness of the algorithm has been proved. -
陸生勛,電子學報,8(1980), 29.[2]陸生勛,杭州大學學報,1980年,第1期,第63頁.[3]金綏更,用王氏積產(chǎn)生任意圖的全部哈密頓圈,電子學報,1981年,第6期,第33頁.[4]金綏更,張麗君,割算法在719機上的實現(xiàn),科技通訊,1981年,第3期,第89頁.[6]F. Harary著,李藯萱譯,圖論,上?？萍汲霭嫔?1980. -
計量
- 文章訪問數(shù): 1936
- HTML全文瀏覽量: 135
- PDF下載量: 555
- 被引次數(shù): 0
下載:
