標題: 串並聯網路上的雙尤拉路徑
作者: 何東洋
HE, DONG-YANG
徐力行
XU, LI-XING
應用數學系所
關鍵字: 串並聯網路;電路理論;樹形圖;雙尤拉路徑;分片性質;線性時間;DET;LINEAR-TIME
公開日期: 1988
摘要: 在電路理論中,我們習慣使用串並聯圖型來表示串並聯網路的型式。然而,一個串並 聯網路卻有著許多的串並聯圖型表示法。現在給定一個串並聯網路N,即可得到一個 串並聯網路的樹形圖T表示法,其中的內部點是PARALLEL(P)或是SERIES(S), 外圍點就是每一條邊。當我們把T中的串聯(S)與並聯(P)形式對調後,就可得 到一個對應串並聯網路樹形圖T3 ,即是串聯網路N' 。 在一個串並聯網路中,當它存在一個串並聯圖型G〔N〕和一個對應串並聯圖型G〔 N〕,有著共同的尤拉路徑,那麼我們就稱這個串並聯網路N,有雙尤拉路徑,我們 原本想找出一個串並聯網路N,具有雙尤拉路徑(DET)的充分與必要條件,然而 ,並沒有成功,但也找到一些充分與必要條件。例如,當一個串並聯網路N具有雙尤 拉路徑時,我們知道在這網路中,最多2個子網路外其它子網路的充分及必要條件, 現在如果我們再加上一個可以用線性時間的演算法就可判斷出的分片性質,那麼我們 就可以在這條件下,用一樣是線性時間的演算法去概略判斷是否一個串聯網路N具有 雙尤拉路徑。 在最後,我們也列出一些並不具備片性質的串並聯網路,這是在研究這問題過程中的 一些小發現,加上這一些不具分片性質的串並聯網路,我們同樣的是可以用線性時間 的演算法去判斷是否一個串並聯網路N具有雙尤拉路徑。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT772507006
http://hdl.handle.net/11536/54171
Appears in Collections:Thesis