串並聯綱路上一些演算法

Abstract

串並聯網路，多用於電路模型之中，我們通常用串並聯圖來表示之，然而一個串並聯 網路之串聯表示圖並非唯一。給一個圖型Ｇ＝（Ｖ，Ｅ），Ｍ為Ｅ（Ｇ）之子集，如 果所有元素，有不同端點，且任兩個元素都不相聯，我們稱為配對。而一個圖型之配 對數β（Ｇ）定義為Ｇ所有配對集合個數之最大值，Ｓ為Ｖ之子集合，我們稱Ｓ為Ｖ 之孤立集合，如果沒有任何一Ｇ中之邊，二頂點皆為Ｓ中之元素，而一個圖型之孤立 點個數α（Ｇ）定義為Ｇ中所有孤立集合個數之最大值，最大配對數β（Ｎ）定義為 對一串並聯網路中，所有串並聯表示圖中配對數β（Ｇ〔Ｎ〕），最大的值。最小配 對數β（Ｎ）則為配對數β（Ｇ〔Ｎ〕）之最小值。最大孤立點數α（Ｇ〔Ｎ〕）定 義為孤立點數α（Ｇ〔Ｎ〕）中之最大值。 在此篇論文中，我們用一個線性演算法來計算任意串並聯網路Ｎ之β（Ｎ），β（Ｎ ）和α（Ｎ）值。並討論相關之應用。