線路佈局中之分割問題與最小相交問題

Abstract

在超大型積體電路的線路佈局裡，分割重要的工具。利用圖的模型，我們將分割問題 數學化；以點代表邏輯電路中的組成單元，以線代表其電路連接的情形。並介一種常 用的交換式分割方法。我們也考慮以圖的接鄰矩陣來討論的分割方法，因而得到最小 外連接數的下界。 最小相交數提供了分割線路成為兩個部份的最低代價。我們的主要興趣便放在最大流 量最小相交定理和演算法。由上述觀點，我們研究了多重端點的最小相交問題和使用 一個更適合電路的相交綱路模型。最後，結合多重端點和相交網路的最小相交的演算 法，我們可以計算所有單元之間的最小相連數。