完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | 吳宙耕 | en_US |
dc.contributor.author | Chou-Keng Wu | en_US |
dc.contributor.author | 譚建民 | en_US |
dc.contributor.author | Jimmy J.M. Tan | en_US |
dc.date.accessioned | 2014-12-12T02:56:58Z | - |
dc.date.available | 2014-12-12T02:56:58Z | - |
dc.date.issued | 2005 | en_US |
dc.identifier.uri | http://140.113.39.130/cdrfb3/record/nctu/#GT009323614 | en_US |
dc.identifier.uri | http://hdl.handle.net/11536/79145 | - |
dc.description.abstract | 給一個圖G=(V,E)以及邊集合R屬於E,其中R的邊為獨立路徑。如果一個圖G包含漢米爾頓迴路以及含有任何的需求邊R且|R|小於等於k,則圖G稱為k-漢米爾頓需求邊。我們定義圖G的漢米爾頓需求邊且k為最大時,稱為hr(G)。如果一個圖G-F包含漢米爾頓但不包含壞邊F且|F|小於等於k,則圖G稱為k-漢米爾頓容錯邊。我們定義圖G的漢米爾頓容錯邊且k為最大時,稱為hf(G)。在這篇論文中,我們要證明如果圖G為三正則漢米爾頓圖,則hf(G)小於等於1。如果圖G為三正則漢米爾頓圖且hf(G)=1,則hr(G)大於等於1且hr(G)小於等於3。我們將介紹一些hf(G)=1且hr(G)=i其中i=1,2,3的3-連通漢米爾圖G,以及一些hf(G)=0且hr(G)=1的3-連通漢米爾圖G。 | zh_TW |
dc.description.abstract | Given a graph G = (V,E) and edge set R belong E, where the edges of R form independent paths. A graph G is k-edge-required-hamiltonian if it contains a hamiltonian cycle including any R whenever |R| <= k. We define edge-required hamiltonicity of G, denoted by hr(G), to be the maximum of such k. A graph G is k-edge-fault-tolerant-hamiltonian if G–F is hamiltonian for any faulty edge set F with |F| <= k. We define edge-fault-tolerant hamiltonicity of G, denoted by hf(G), to be the maximum of such k. In this thesis, we prove that hf(G) <= 1 if G is a cubic hamiltonian graph, 1 <= hr(G) <= 3 if G is a cubic hamiltonian graph with hf (G) = 1. We present some cubic 3-connected hamiltonian graphs G with hf(G) = 1 and hr(G) = i for i = 1, 2, 3, a cubic 3-connected hamiltonian graph G with hf(G) = 0 and hr(G) = 0, and a cubic 3-connected hamiltonian graph G with hf(G) = 0 and hr(G) = 1. | en_US |
dc.language.iso | en_US | en_US |
dc.subject | 漢米爾頓 | zh_TW |
dc.subject | 漢米爾頓連結 | zh_TW |
dc.subject | hamiltonian | en_US |
dc.subject | hamiltonian connected | en_US |
dc.title | 三正則及連通圖中漢米爾頓性質之連線需求數目的研究 | zh_TW |
dc.title | The Edge-Required-Hamiltonicity of the Cubic 3-Connected Hamiltonian Graphs | en_US |
dc.type | Thesis | en_US |
dc.contributor.department | 資訊科學與工程研究所 | zh_TW |
顯示於類別: | 畢業論文 |