無向圖在計算機繪圖中的應用

張強

摘 要：本文把筆式繪圖儀繪圖過程時間最少的調度問題轉換為在加權無向圖中求解最優H-回路，并且利用最小生成樹、歐拉回路、非二部圖賦權匹配的算法給出了一種近似調度算法，旨在減少繪圖儀移動空走時間和換筆時間，從而提高繪圖效率。本算法經RP-MF160等繪圖儀應用，效率提高約15%。

關鍵詞：筆式繪圖儀；調度算法；H-回路；加權圖匹配

中圖分類號：TP301 文獻標識碼：A

1 引言（Introduction）

計算機繪圖是CAD和CAM的重要組成部分。隨著計算機應用技術的飛速發展，目前已廣泛應用于各個領域。

筆式繪圖儀在完成一幅圖的繪制時，其總時間消耗由三段組成：即實際繪圖時間，抬筆移動空走時間以及更換畫筆時間。由于實際繪圖這段時間是必不可少的，因此，為了減少總時間消耗，提高繪圖儀的使用效率，必須盡可能地減少另兩段的時間耗費，即減少抬筆移動空走時間和換筆時間。這樣一來，我們實際上面臨的是一個繪圖儀繪圖過程的時間優化問題，解決的主要途徑就是設計一個高效的繪圖過程調度算法。目前，在設計繪圖儀繪圖過程時，采用的主要方法基本上是根據一幅圖上各個基本圖形的分布情況、相對位置以及程序設計人員的實際編程經驗進行安排，還沒有一個公認高效的調度算法作為依據。因此，不難想象，在某種復雜情況下，采用上述方法將會大大增加繪圖儀繪圖過程的時間開銷，降低其使用效率。為此，下面將針對繪圖儀繪圖建立一種具體的數學模型，在此基礎上給出一種相應的調度算法，并對其時間復雜度進行分析，旨在盡可能地減少繪圖時的抬筆移動空走時間和換筆時間，降低其時間耗費。

2 建立數學模型（Set up mathematical model）

基本圖形：指繪圖儀無需抬筆就可一筆繪制完成的圖形。即所謂的“一筆畫”圖形。如圓、矩形、三角形、弧線等。

一幅圖：指若干基本圖形依照某種特定的布局組合而成的圖。

封閉圖形：指由n（n為正整數）條線段或弧組成的閉合基本圖形。如圓、矩形、三角形等。

開放圖形：指由n（n為正整數）條線段或弧組成的非閉合基本圖形。這里要求開放圖形恰有兩個端點。如拋物線、線段等。

無向圖：指圖G中每一條邊都是無方向的。

加權無向圖：指無向圖G中每一條邊e都對應一個實數W（e），稱W（e）為e的“權”。

H-回路：指經過圖G中每個節點一次且僅一次的回路。

另外，還要求繪圖儀在繪制一個基本圖形時，其間不能抬筆、間斷。必須一次性完成。

接下來，我們可以將繪圖儀完成一幅圖繪制的操作過程描述如下：繪圖儀將畫筆從起始點移動空走到第一個基本圖形，完成該基本圖形的繪制后，再移動空走到下一個基本圖形，完成繪制后，再移動空走……直至把所有基本圖形繪制完畢，然后把畫筆移動空走到初始位置。

下面我們用構造法將一幅圖轉換成與之對應的加權無向圖，以此來描述繪圖儀繪圖過程并分析其時間復雜度。構造步驟如下：

（1）用一個實節點表示封閉圖形，其坐標定為繪圖儀繪制該基本圖形時的起始位置。

（2）用兩個實節點分別表示開放圖形的兩個端點，其坐標分別定為對應端點的坐標位置；另外，在兩個實節點之間增加一個虛節點，其坐標定為這兩個實節點的中心點坐標；該虛節點僅與這兩個實節點有邊相連，這兩條邊的權值均為0。

（3）用一個實節點來表示繪圖儀的畫筆起始位置，其坐標為畫筆起始位置坐標。

（4）圖中的任何兩個實節點間均有無向邊相連，每條邊的權值均為畫筆在該邊所關聯的兩個實節點間移動空走所需時間。若兩實節點對應的圖形顏色不同，再加換筆時間。

采取上述的方法，可以由一幅圖G構造出與之對應的一個加權無向圖G*。這樣一來，繪圖儀繪制一幅圖G的過程相當于G*上構造一個H-回路，反之亦然。實際上，繪圖儀繪制一幅圖G相當于在其對應G*中的一條H-回路上遍歷一次。其所消耗的全部移動空走時間和換筆時間等于對應G*中的該條H-回路上各邊的權值之和。因而，尋找花費時間最少的繪圖過程相當于在G*中求解邊權之和最小的H-回路，即最優H-回路。進一步，我們可以把繪圖儀繪圖過程調度問題抽象為在加權無向圖中求解最優-回路問題。然而，求解加權無向圖G*的最優H-回路屬于NP完全問題。到目前為止，對此沒有有效的多項式算法。因此，求解該問題的主要途徑是設計有效的近似算法。

3 近似算法設計（The approximate algorithm design）

約定一幅圖G對應的加權無向圖為G*，C*為G*的一個最優H-回路，n=v（G*），OPT（G*）表示C*上各邊權之和，并且假定G*不含虛節點，因此，任取x，y，z∈V（G*），滿足：

（1）對稱性：d（x，y）=d（y，x），其中d（x，y）表示節點x與節點y之間邊的權值。

（2）三角不等式：d（x，z）≤d（x，y）+d（y，z）。

下面將運用最小生成樹、E-回路、非二部圖賦權匹配的標準算法來給出求G*圖中最優H-回路的一種算法，稱為最小匹配構造H-回路算法（簡記MM）。

MM算法描述如下：

（1）求G*中的一棵最小生成樹T*。

（2）求T*中奇度數節點構成的集合V'={a1，a2，…，a2k}。

（3）由V'中節點及相關邊構成G*的一個子圖G1*，求G1*中邊權之和最小的完全匹配M，|M|=K。

（4）把M中的K條邊加到T*上，得到T**，T**是一個E-圖。

（5）求T**的一個E-回路。

（6）采用“捷徑”技術[5]，將E-回路變為H-回路。

設MM（G*）表示MM算法在G*中產生的H-回路的邊權之和。則有：

定理MM（G*）證明見參考文獻[2]。

MM算法的時間復雜度分析如下：

步驟1：采用Prim算法[4]，O（n2）。

步驟2：O（n）。

步驟3：采用Lawler算法[1]，O（n3）。

步驟4：O（n）。

步驟5：采用Fleury算法[3]，O（n3）。

步驟6：O（n2）。

因此，MM算法總的時間復雜度為O（n3）。

4 結論（Conclusion）

MM算法僅討論了一幅圖中只包含封閉圖形和整個圖為單一顏色的情況。若一幅圖G包含開放圖形且有多種顏色時，由G誘導的G*不滿足三角不等式，需要對G*及MM算法做適當修改，較為復雜，限于篇幅，在此不作進一步討論。

筆式繪圖儀繪圖過程之調度算法的研究是圖論在計算機繪圖領域的典型應用，尤其是文中所涉及的最優H-回路問題在運籌學中也有著實際意義。因此，越來越受到科研人員（尤其是CAD和CAM的從業人員）及有關商家的高度關注。若能將一個好的調度算法加以編程實現，再將其作為一個應用程序集成到繪圖軟件系統中，不僅能提高該繪圖軟件系統的商業價值，也將會大大提高繪圖儀的使用效率。

參考文獻（References）

[1] E L lawler.combinatorialOptimization：Networks and

Matroids[M].New York：Holt，Rinehart and Winston，1976.

[2] Garey M R，Johnson D S.computers and intractability-A

Guide to the Theory Of NPcompletemess[M].W H Freeman

and compang，1979.

[3] Bondy J A，murty U S R.Graph Theory with Applications[M].

Macmillan Press LTD，1976.

[4] 嚴蔚敏.數據結構[M].北京：清華大學出版社，1987.

[5] 盧開澄.組合數學—算法與分析[M].北京：清華大學出版社，

1983.

作者簡介：

張 強（1962-），男，碩士，教授，碩導.研究領域：計算機科

學理論，軟件技術，現代教育技術.