文章詳目資料

中原學報

  • 加入收藏
  • 下載文章
篇名 A Simple Scheme of Generating Bipartite Graphs with Fault-tolerant Hamiltonian Properties
卷期 33:1
並列篇名 具容錯--漢米爾頓性質之二部圖的簡單建構方法
作者 高欣欣陳育志
頁次 11-19
關鍵字 二部圖漢米爾頓性質的漢米爾頓連通性BipartiteHamiltonianHamiltonian laceable
出刊日期 200503

中文摘要

在這篇文章中,我們介紹一個產生有良好性質的二部圖的簡單方法。考慮一個bipartite圖形G,令W和B為它的二個分部 (partition),假如它有1-edge hamiltonian,1p-hamiltonian和hamiltonian laceable的性質,我們就稱它為一個「良好的」二部圖。更明確的說,令F為一個包含任意一個邊的集合,或F是一個包含一對點的集合{v1, v2|v1[9465]W, v2[9465]B},若稱G是「良好的」,則G-F必保有漢米爾頓性質;而且在G中給定任意二點u[9465]W和v[9465]B,必存在從u到v 的漢米爾頓路徑。我們稱此處所介紹的方法為「邊代換」。兄弟樹[4],BT(n),n≧1就是一可由邊代換產生之良好的二部圖的例子。

英文摘要

In this paper, we introduce a simple scheme of generating “good” bipartite graphs. A bipartite graph G with bipartition W and B is a good graph if it is 1-edge hamiltonian, 1p-hamiltonian and hamiltonian laceable. More specifically, G is good if G-F remains hamiltonian where F consists of an edge or a pair of vertices {u1, u2|u1[9465]W, u2[9465]B}, and if there exists a hamiltonian path between u and u for any u[9465]W, u[9465]B. This scheme is called “edge replacement”. Simple examples of good bipartite graphs, as well as the family of brother trees BT(n) with n≧1 [4], are obtained as an application of edge replacement.

相關文獻