串并聯網路上雙尤拉路徑的性質

Abstract

在電路理論中，我們習慣用串并聯圖型來表示串并聯網路的型式, 然而，一個串并聯 網路和有著許多的串并聯網路圖形法，現在給定一個串并聯網路N 我們即可在N 中將 串并聯形式對調後得到一個對應串并聯網路N ，在一個串并聯網路中，當它存在一個 串并聯圖形G[N]和一個串并聯圖形G[N]，有著共同的尤拉路徑，那么我們就稱這個串 并聯網路N 有雙尤路徑(DET)CMOS 功能元件的布局面積最佳化中，找出串并聯網路的 雙尤拉路徑是必要的。 我們定義了一些crail cover cype, 再由crail cover type產生出trail cover 的eq uivalence relation然后產生 netwonx classes本篇論文中我們證明了一些有用的性 質，如，蜀於那些class 的necwonx 可group 在一起若有DET 則其子網路必須蜀於那 些 network classes。 本篇論文中，若N 有DET 我們找出了所有N 的子網路的結構，根據DET 網路的性質， 我們發展出網路合成文法的演算法，而且，我們找出一個串并聯網路N 具有DET 的充 分與必要條件。