路徑分割及相關問題

Abstract

基於對漢米爾頓的紀念, 決定一個圖型是否有包含此圖上所有點的路徑( 圈)的問題稱為漢米爾頓路徑(圈)問題, 而此種路徑(圈)就稱為漢米爾頓 路徑(圈). 這個問題已被研究了幾個世紀, 從演算法的觀點來看這個問題 是很"難"的, 此問題在一般圖型上為NP完備, 甚至在如平面圖、二分圖及 弦圖等特殊圖型上亦是如此.本論文的主要目地是從演算法的關點來探討 下面這個為漢米爾頓問題一般化的路徑分割問題, 此問題為將一圖型的點 分割成最少條路徑. 顯然的, 一圖型有漢米爾頓路徑若且唯若此圖型的路 徑分割數為一. k路徑分割為更一般化的問題, 此問題對一給定的正整數 k, 將一圖型分割成最少條包含的點數不大於k的路徑. 若一圖型包含n個 點則此圖型的路徑分割問題與n路徑分割問題是一樣的. 本論文亦探討了 分散數、L(2,1)標號、 L(2,1)'標號、加權控制、半漢米爾頓路徑及漢米 爾頓連通性等相關問題. In honor of Hamilton, the hamiltonian path (respectively cycle) problem is to determine if a graph has a hamiltonian path (respectively cycle), which is a path (respectively cycle) that contains all vertices of the graph. These problems are well stuied during the past centry. From algorithmic point of view, these problems are hard for they are NP-complete in general graphs, and even in special classes of graphs such as planar graphs, bipartite graphs, and chordal geraphs. The main purpose of this thesis is to study the following eneralization of the hamiltonian path problem from an lgorithmic point view. The path partition problem is to artition the vertex set of a graph into a smallest number of aths. Note that a graph has a hamiltonian path if and only if ts path partition number is one. An even more generalized roblem is the k-path partition problem. For a fixed positive nteger k, the k-path partition problem is to partition the ertex set of a graph into a smallest number of paths, each of hem has at most k vertices. Note that the n-path partition s the same as the path partition in a graph of n vertices. his thesis also studies some related problems, such as the cattering number problem, the L(2,1)- labeling problem, the '(2,1)-labeling problem, the weighted domination problem, the emi-hamiltonian path problem, and hamiltonian-connectivity roblem.