求一個給定圖形之最小循環基底

Abstract

循環基底（Cycle Basis ）在理論研究與實際應用上都是一項極重要的課題。所謂加 權圖形（Weighted Graphs ）之最小循環基底（Minimum Cycle Basis ）是指加權值 最小的一組線性獨立之循環基底。要求出最小循環基底，J.D.Horton首先提出一個執 行時間為輸入資料大小的多項式的正確演算法，此演算法是採用考慮每個（點一邊） 配對（vertex-edge pair）的方式以達成Ｏ（ｎ□）的執行時間。在本論文中，我們 以另一（點一點）配對（vertex-vertex pair）方式提出一個執行時間為Ｏ（ｎ□） 的新演算法，此演算法僅用於處堙未加權圖形（Unit-Weighted Graphs）。另外，我 們再設計另一個求取加權圖之最小循環基底的Ｏ（ｎ□）演算法，雖然對此演算法沒 有給定完整而嚴謹的證明，但是所得的許多相關結果與觀察在本論文中一併提出。由 於這些新結果，我們已將問題範圍（Problem Domain）由一般的加權圖形降至所謂的 幾何圖形（Geometric Graphs）。