串并聯網路中雙尤拉路徑之辨識

Abstract

串并聯網路通常被用來當作電子線路之模型; 此外，一般我們都用串并聯圖形來表示 串並關網路；然而，對於每個串并聯網路，往往存在許多不同的串并聯圖形表示方式 。給定一個串并聯網路N ，經由變換每個內部節點之串、并聯型態即可得到N 的對偶 串并網路網路N'；假如N的某個串并聯圖形表示方式G[N] 和N'的某個串并聯圖形表示 方式G[N'] 存在共同的尤拉路徑(Euler Trail) ，我們稱該串并聯網路N 存在雙尤拉 路徑(Double Euler Trail)。 而在超大型積體電路(VLSI)設計的領域裡，靜態互補式金屬半導體(Static CMOS) 基 本功能元件(Functional Cell) 所對應的布林函數可用串并聯網路來表示，如果該串 并聯網路存在雙尤拉路徑，而不考慮靜態互補式金屬半導體基本功能元件之高度，則 此靜態互補式金屬半導體基本功能元件之寬度將可降至最小，所以此元件所佔據之面 積將減少甚多；因以，就制作高密度之超大型積體電路而言，辨識串并聯網路是否存 在雙尤拉路徑即為重要。 在這篇論文中，我們求出存在雙尤路徑的串并聯圖形裡所有子串并聯圖形在該雙尤拉 路徑裡的路徑型態(Trail cover Type)，考慮串并聯網路所有可能的路徑型態，探討 存在雙尤拉路徑的串并聯網路所具有的重要性質，并提出一個僅需線性時間(Linear Time) 即能辨識串并聯網路是否存在雙尤拉路徑的演算法(Algorithnl)。