Title: 平面圖的點變樹分割及漢彌頓圈問題
The Vetex-to-Tree Arboricity and the Hamiltonian Cycle Problem in Planar Graphs
Authors: 陳亞萍
Chen, Yaping
陳秋媛
Chen, Chiuyuan
應用數學系所
Keywords: 平面圖, 分割數, 漢彌頓圈;planar graph, arboricity, Hamiltonian cycle
Issue Date: 1994
Abstract: 一個圖G的點集合,最少可被分割成的部份集合個數,使得每個部份集合
皆各自衍生出一個不含圈的子圖,稱為圖G的點分割數,並表示為a(G)
。在本論文中,我們介紹另一個點分割數的變形,稱為點變樹分割數,並
表示為a_t(G);它是一個圖G的點集合,最少可被分割成的部份集合
個數,使得每個部份集合各自衍生出的子圖都是一棵樹。我們證明:如果
圖G是一個連通平面圖,則圖G有漢彌頓圈的充要條件是圖G的平面對偶
圖G^*之點變樹分割數a_t(G^*)為2,並且我們證明:如果圖G是一
個最大平面圖,則a(G)=1若且唯若a_t(G)=1,a(G)=2若且
唯若a_t(G)=2與a(G)=3若且唯若a_t(G)≧3。我們也研究
在最大平面圖中找漢彌頓圈之問題,而且針對最大平面圖提出一個有用的
檢查方法,藉以判斷某些最大平面圖是沒有漢彌頓圈的。
The vertex arboricity a(G) of a graph G is defined to be the
minimum number of subsets into which the vertices of G can be
partitioned such that each subset induces an acyclic graph. In
this thesis, we introduce a variant of vertex arboricity,
called vertex-to=tree arboricity a_t(G); it is the minimum
number of subsets into which the vertices of a graph G can be
partitioned so that each subset induces a tree. We prove that
if G is a connected planar graph then G is Hamiltonian if and
only if a_t(G^*)=2, and we prove that if G is a maximal planar
graph, then a(G)=1 iff a_t(G)=1, a(G)=2 iff a_t(G)=2, and a(
G)=3 iff a_t(G)≧3. We also investigate the Hamiltonian cycle
problem for maximal planar graphs and propose a useful method
checking non-Hamiltonian maximal planar graphs.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT830507018
http://hdl.handle.net/11536/59648
Appears in Collections:Thesis