查詢結果分析
來源資料
頁籤選單縮合
題名 | A Simple Scheme of Generating Bipartite Graphs with Fault-tolerant Hamiltonian Properties=具容錯--漢米爾頓性質之二部圖的簡單建構方法 |
---|---|
作 者 | 高欣欣; 陳育志; | 書刊名 | 中原學報 |
卷期 | 33:1 民94.03 |
頁次 | 頁11-19 |
分類號 | 319.9 |
關鍵詞 | 二部圖; 漢米爾頓性質的; 漢米爾頓連通性; Bipartite; Hamiltonian; Hamiltonian laceable; |
語文 | 英文(English) |
中文摘要 | 在這篇文章中,我們介紹一個產生有良好性質的二部圖的簡單方法。考慮一個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. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。