串並聯網路上的雙尤拉路徑

Abstract

在電路理論中，我們習慣使用串並聯圖型來表示串並聯網路的型式。然而，一個串並 聯網路卻有著許多的串並聯圖型表示法。現在給定一個串並聯網路Ｎ，即可得到一個 串並聯網路的樹形圖Ｔ表示法，其中的內部點是PARALLEL（Ｐ）或是SERIES（Ｓ）， 外圍點就是每一條邊。當我們把Ｔ中的串聯（Ｓ）與並聯（Ｐ）形式對調後，就可得 到一個對應串並聯網路樹形圖Ｔ3 ，即是串聯網路Ｎ' 。 在一個串並聯網路中，當它存在一個串並聯圖型Ｇ〔Ｎ〕和一個對應串並聯圖型Ｇ〔 Ｎ〕，有著共同的尤拉路徑，那麼我們就稱這個串並聯網路Ｎ，有雙尤拉路徑，我們 原本想找出一個串並聯網路Ｎ，具有雙尤拉路徑（ＤＥＴ）的充分與必要條件，然而 ，並沒有成功，但也找到一些充分與必要條件。例如，當一個串並聯網路Ｎ具有雙尤 拉路徑時，我們知道在這網路中，最多２個子網路外其它子網路的充分及必要條件， 現在如果我們再加上一個可以用線性時間的演算法就可判斷出的分片性質，那麼我們 就可以在這條件下，用一樣是線性時間的演算法去概略判斷是否一個串聯網路Ｎ具有 雙尤拉路徑。 在最後，我們也列出一些並不具備片性質的串並聯網路，這是在研究這問題過程中的 一些小發現，加上這一些不具分片性質的串並聯網路，我們同樣的是可以用線性時間 的演算法去判斷是否一個串並聯網路Ｎ具有雙尤拉路徑。