（電路與系統(tǒng)專業(yè)論文）任意圖同構判定及其應用.pdf

摘要 摘要 圖的同構問題一直受到數學界與工程技術界的關注，其原因主要來自兩個方 面：第，從理論上講，一般認為該問題屬于n p 一完全問題；第二，圖的同構問 題具有很好的應用前景，在化學、運籌學，計算機科學、電子學、網絡理論等諸 多領域都有應用，但指數時間復雜度的算法以及算法本身適用對象的局限性使得 涉及到復雜圖形同構判定的應用問題難以入手。 本文提出了面向任意圖的同構判定算法并系統(tǒng)的討論了實際應用中基于任 意圖的建模方法。 在實現上述算法與應用過程中，本文完成了以下工作： 1 在分析了簡單圖拓撲結構描述的基礎上提出了新的任意圖拓撲結構描 述方法和相應的同構判定條件。 2 建立了任意圖的伴隨電路模型，采用節(jié)點電壓方法求取電壓，將其作為 同構判定的參數，使用物理方法解決圖論問題。 3 針對部分特殊圖形提出了相對位序表的概念，以改進算法在處理這類圖 形時的效率。 4 在具體應用中引入任意圖建立模型，從而為一類很難采用單一拓撲圖建 模的復雜問題提供了一種新的解決方案。 區(qū)別于目前已有的同構判定算法，該算法對于待判定的拓撲圖沒有附加限定 條件，能有效的應用于無向圖，有向圖，帶權圖以及由它們組成的混合圖，因而 適用于各類涉及到圖的同構判定的應用領域。 關鍵詞：任意圖，同構，伴隨電路模型，相對位序表 中圖分類號：t n7 1 1 6 a b s t r a cc a b s t r a c t t h ep r o b l e mo fg r a p hi s o m o r p h i s mh a sb e e nc o n c e r n e db yt h ef i e l d so f m a t h e m a t i c sa n de n g i n e e r i n gf o ry e a r s t h em a i nr e a s o nc o l ：1 1 e sf r o mt w oa s p e c t s ：f o r o n et h i n g ，t h e o r e t i c a l l y ，t h ep r o b l e mi sg e n e r a l l yc o n s i d e r e dt ob en p c o m p l e t e ；f o r a n o t h e r , g r a p hi s o m o r p h i s mp r o m i s e s aw i d e a p p l i c a t i o n ，s u c h a s c h e m i s t r y , o p e r a t i o n a lr e s e a r c h ，c o m p u t e rs c i e n c e ，e l e c t r o n i ce n g i n e e r i n ga n dn e t w o r kt h e o r y , b u tt h ee x p o n e n t i a lc o m p l e x i t yo ft h ea l g o r i t h m sa n dt h e i rh a r s hl i m i t a t i o n sp u to n t e s t i n gg r a p h sm a k e i td i f f i c u l tt os o l v es o m e a p p l i e dp r o b l e mr e f e r r i n g t o c o m p l i c a t e dg r a p h s i nt h i sp a p e r , a na l g o r i t h mf o ri s o m o r p h i s mt e s t i n go fa r b i t r a r yg r a p h si sp r o p o s e d a n dt h em e t h o do fm o d e l i n gf o ra p p l i e dp r o b l e m sb a s e do na r b i t r a r yg r a p h si s d i s c u s s e ds y s t e m a t i c a l l y t h ef o l l o w i n gw o r k sh a v eb e e n d o n ei nt h ei m p l e m e n t a t i o no ft h ea l g o r i t h ma n d i t sa p p l i c a t i o n 1 t h et o p o l o g i c a ls t r u c t u r eo fs i m p l eg r a p hi sa n a l y z e d ，t h e nan e wd e s c r i p t i o n o ft o p o l o g i c a ls t r u c t u r eo fa r b i t r a r yg r a p ha n dc o r r e s p o n d i n gc r i t e r i o n sf o r i s o m o r p h i s mt e s t i n ga r ee s t a b l i s h e d 2 ，t h ec o n c o m i t a n tc i r c u i tm o d e lo fa r b i t r a r yg r a p hi sb u i l t ，t h en o d a lv o l t a g e s a c h i e v e da r et h e nu s e da sp a r a m e t e ro fi s o m o r p h i s mt e s t i n g ，t h u st h ep r o b l e m o fg r a p ht h e o r yi ss o l v e db yp h y s i c a lm e t h o d 3 c o m p a r a t i v es e q u e n c et a b l e ( c s t ) i sp r o p o s e dt oe n h a n c et h ep e r f o r m a n c eo f a l g o r i t h mf o rs o m es p e c i a lg r a p h s 4 a r b i t r a r yg r a p hi si n t r o d u c e di n t om o d e l i n gi na p p l i c a t i o nf i e l d ，t h u sp r o v i d e s an e ws o l u t i o nf o rt h ec o m p l i c a t e dp r o b l e m st h a tc a nh a r d l ym o d e lw i t h s i n g l et o p o l o g i c a lg r a p h k n o wf r o ma l lt h ea l g o r i t h m sp r e s e n t e dt i l ln o w , t h i sa l g o r i t l m aa p p e n dn o r e s t r i c t i o nt ot h eg r a p h sf o rt e s t i n g i tc a nb eu s e df o ru n d i r e c t e dg r a p h s ，d i r e c t e d g r a p h s ，w e i g h e dg r a p h sa n dm i x e dg r a p h sc o m p r i s e do fa i la b o v e ，t h u si t sa p p l i c a b l e t ov a r i o u sp r o b l e m sr e f e r r i n gt og r a p hi s o m o r p h i s m k e yw o r d s ：a r b i t r a r yg r a p h ，i s o m o r p h i s m ，c o n c o m i t a n tc i r c u i tm o d e l ，c o m p a r a t i v e s e q u e n c et a b l e c l cn u m b e r ：t n7 11 6 4 0 f 言 引言 自然界和人類社會中的大量事物以及事物間的關系，?？捎脠D形來描述。例 如，物質結構，電氣網絡，城市規(guī)劃，交通運輸，信息傳送，工作調配，事物關 系等等都可用點和線連接起來的圖模擬。研究圖的基本概念和性質，圖的理論及 其應用，構成圖論的主要內容。 圖論通過由點和線組成的圖形，構成模擬物理系統(tǒng)的數學模型，并根據圖的 性質進行分析，提供研究各種系統(tǒng)的巧妙方法。任何一個包含了某種二元關系的 系統(tǒng)都可以用圖論的方法分析，而且它往往還有形象直觀的特點。圖論中應用的 線形圖與幾何圖不同，每條邊都可以有方向有權值，用以研究系統(tǒng)特性，進行決 策分析，確定最優(yōu)設計，調整經濟管理等等。 圖的同構判定問題是圖論學科中的基本問題之一，所謂圖的同構，簡單的 說，就是兩個圖的結構完全相同，一般認為判定同構的問題屬于n p 一完全問題 j 。， 從而使得該問題與3 0 0 多個類似的問題建立了聯系，這類問題是等價的，即如果 其中一個問題能找到多項式時間復雜度的算法，其他問題就都能找到多項式時間 復雜度的算法，因此，圖的同構判定問題直為圖論研究人員所關注。同時，圖 的同構判定還有著廣泛的應用前景，但指數時間復雜度的算法以及算法本身適用 對象的局限性往往使得涉及到復雜圖形同構判定的應用問題難以入手。 過去3 0 年來尋找高效的同構判定算法的努力從來沒有中斷過。對一些特殊 的圖，例如樹、二分圖以及頂點度數滿足一定條件的圖，已經有了較為高效的算 法 2 。一般的無向圖同構算法中，常用的思路是出圖的鄰接矩陣的特征值和置換 矩陣入手來確定圖的同構”r ，這樣的方法在數學上是嚴密的，效率卻不夠高。 自h o p f i e l d 5 將神經網絡的方法應用于圖論以來，出現了很多利用神經網絡解 決同構問題的新方法 6 ，“，然而這類方法往往局限于規(guī)模不大的圖，且存在收斂 性的問題。雖然近年來，在同構判定問題上還出現了很多新方法【8 _ qj o ，但至今 仍未找到普適性的多項式時間復雜度算法，而在有向圖以及帶權圖等復雜圖形的 同構判定問題上更是存在大量問題有待探索。因此，找到一個能普遍適用于任意 圖同構的判定方法，提高算法效率使之盡量接近于多項式復雜度依然是當前圖論 研究中的重要課題。 第一章圖的刪構及其應用概況 第一章圖的同構及其應用概況 為了便于展開圖的同構問題的討論，本章先引入圖論中的一些基本概念，在 此基礎上簡單介紹目前已有的一些較為成熟的同構判定算法，最后舉出一些涉及 到同構判定的具體應用。 1 1 基本概念 在系統(tǒng)的介紹圖的同構判定問題之前，先就圖論中的一些基本概念做如下 說明。 圖論所研究的對象是事物間晟一般的關系的相互聯系，事物和事物間之關 系抽象為點、線集合的圖?，F給出圖論中通用的與本文中任意圖同構判定問題相 關的概念，定義如下。 定義1 1 一個圖g 定義為一個偶對( y ，e ) ，記作g = ( y ，e ) ，其中 ( 1 ) v 是一個非空集合，其中的元素稱為項點。 ( 2 ) e 是無序積v x v 中的一個子集合，其元素稱為邊；集合v v 中的元素 可在f 中出現不止一次。 根據以上定義，分別用v ( g ) 和e ( g ) 表示圖g 的頂點集合與邊的集合。如 果v ( g ) 和e ( g ) 都是有限集合，則g 稱為有限圖；否則稱為無限圖。比較無限圖 的同構是沒有意義的，因此以下討論的同構圖都是指有限圖。 通常，定義1 1 是針對無向圖而言，對于有向圖，需要對無向圖概念作一些 拓展。 定義1 2 一個有向圖q 定義為一個偶對q = ( v ，e ) ，其中 ( 1 ) v 是個非空集合，其中的元素稱為頂點。 ( 2 ) e 是有序積v v 的一個子集，其元素稱為有向邊( 或叫做弧) ；集合v v 中的元素可在e 中出現不止一次。 根據有向圖的定義，與一條有向邊相關聯的兩個端點具有一定的次序關系， 即有向邊e = ( “，v ) 是頂點“和v 的有序對。稱材為有向邊p 的起點，v 為終點。 如果對有向圖倪= ( v ，e ) 的每一條有向邊( “，v ) 從起點“到終點v 作一矢線，方 向是從“指向v ，那么有向圖的每一條有向邊都有確定的方向。因此有向圖就是 每條邊都有一定方向的圖。 關于點和邊的相互關系有以下概念，邊與它的兩端點稱為關聯的；與同一 第一章朗的同構及其應用概況 條邊關聯的兩端點或者與同一個頂點關聯的兩條邊稱為相鄰的：兩端點相同的邊 稱為環(huán)；有公共起點并有公共終點的兩條邊稱為平行邊或者重邊；兩端點相通但 方向互為相反的兩條有向邊稱為對稱邊。 有了上述定義和概念，立即可以看出，有向圖與無向圖的差別僅在于v v 中元素是礦中元素的有序對還是無序對。然而，無序對饑v ) 可以視為兩個有序 對( “，v ) 和( v ，“) 。也就是說，對于無向圖g ，將g 中每條邊e 用兩條與p 有相同 端點的對稱邊來替代后得到個有向圖q 。這樣得到的有向圖q 稱為g 的對稱 有向圖。由此可見，無向圖可以視為特殊的有向圖。圖1 1 ( a ) 和( b ) 中所示的圖就 是這樣的兩個圖。 圖論中研究的部分內容常與邊的方向沒有關系，故在討論與邊方向沒有關 系的有向圖q 時，人們通常去掉邊上的方向，這樣得到的無向圖g 稱為g ，的基 礎圖。反之，任給一個無向圖g ，將g 的邊指定個方向從而得到一個有向圖g ， 稱這樣的有向圖玩為g 的一個定向圖，如圖1 1 ( c ) 所示。 v ，義 ，!毪 ( a ) 無向圖g( b ) g 的對稱有向圖q ( c ) g 的定向圖氓 圖1 1 定義1 3 對無向圖( 或有向圖) ，在各條邊加上相應的權值w ，則構成了帶 權圖。可以認為，不帶權的圖中各條邊的權值均為1 。 定義1 4 設v v ( g ) ，g 中與頂點v 關聯的邊的條數稱為v ( 在g 中) 的度數。 相應的，對于有向圖而言，與頂點v 關聯的邊中方向指向這個子圖的邊稱 為入邊，方向離開這個子圖的邊稱為出邊。入邊的數目稱為入度，出邊的數目稱 為出度。 定義1 5 設有個頂點的無向圖g = ( 礦，e ) 的頂點集為g = v ，v 2 ， ， 用略表示g 中v 與之間的邊數。稱其對應的矩陣d = 【毛 。為g 的鄰接矩陣。 其中： 吒= k葉和v ，鄰接，且v 和v ，間有k 重邊( 0 ) 4 ，= 0v 和v ，不鄰接 0 第一章圖的同構及e 應用概況 圖的鄰接矩陣有以下明顯的性質： ( 1 ) d 是一個對稱矩陣； ( 2 ) 若g 為無環(huán)圖。則d 中第f 行的元素之和等于頂點v 的度數。 ( 3 ) 當且僅當圖的鄰接矩陣可以分塊為 d ：i2 墮k 一旦一l l 0l d ( q ) j 時，圖g 是一個具有g ，和g ：兩個連通片的非連通圖。d ( g 。) 是對應連通片 g 的臨界矩陣，d ( g ) 是對應連通片g 的鄰接矩陣。 而對于有向圖和帶權圖，顯然以上關于無向圖鄰接矩陣的定義很不合適， 具體的定義方法將在以后的章節(jié)中討論。 利用以上基本概念考察以下兩幅無向圖( 圖1 2 ) 。 爪 么：查：! 左：竺：! 鹽 一 么：! 查蘭 v i e 6 ( a ) g 原始同 ，p ：和e 鹺 小 e ；火。； v ，么二。 圖1 3 變形后的同構圖 ( b ) g 3 第一章圖的司構及其應用概況 很明顯，直觀上看g l 和g 3 結構上完全一致，而由變化過程可知圖q 和g 3 是 同一個圖，由此可得g 1 和g 2 結構上完全一致，即同構。 對照圖l - 3 很容易得出g l 和g 3 ( g 2 ) 頂點與邊的對應關系為： q 停吩e j 停e 3 v 2h 屹島hf 2 b ”ie he l v 4 七v 4e 4 be 4 ”島 h 由上，可以得到圖的同構定義。 定義1 6 如果兩個圖g 與g 的點之間一一對應，邊之間一一對應，而且 對應點與對應邊之間保持相同的關聯關系，那么g 與g 同構。 該定義直觀的表述了圖的同構概念，對于一些回溯算法可以采用這種定義 判斷同構，但在計算機處理中更為一般的是使用矩陣的方法來判斷圖的同構，相 應的，可以使用置換矩陣的概念來描述圖的同構。 定理1 1兩個圖g 與g 同構的充要條件是存在一個置換矩陣p ，使得鄰 接矩陣有 d = p 7 d 尸 即經過一定的行、列變換能夠使g 與g 對應的點處于鄰接矩陣中行與列的 相同位置。 考察如下g 和g ，的鄰接矩陣。 v 1 d 1 ：v 2 屹 v 4 巧吩 o1 10 11 ll 嶼蟾 一 11 1l o1 l0 v 。1v 2v 3v 4 o111 1oll 1 101 1l1o 這里無需經過任何行列變換，可以直接從兩個圖的相同的鄰接矩陣得到兩圖 同構的結論。 實際上，上面的例子是一類特殊的無向圖完備圖，它的每一對不同的頂 點之間均有一條邊相連，因此無論頂點編號如何改變，它都具備唯一的鄰接矩陣。 具有n 個頂點的完備圖中，每個頂點的度為即一1 。相同頂點數的完備圖的鄰接矩 陣無需經過行、列交換即是相等的。還有一種圖，每一個頂點都具有相同的度， 這種圖被稱為正則圖。每個頂點的度均為k 的正則圖稱為知正則圖。完備圖是一 類特殊的正則圖，即即一1 正則圖。 4 v v v v = 現 第章圖的同構及其應用概猶 1 2 算法簡介 在大多數情況下，頂點的編號并不是事先確定的，因此對于兩個非完備圖而 言，即使它們是同構圖，對應的鄰接矩陣也往往不是一開始就相等的，如圖1 4 所示。 g g 圖1 4 兩個具有不同鄰接矩陣的同構圖 它們的鄰接矩陣如下。 巧吩哆吩吩 ol1l1 1o 1 01 1101o 10 101 110lo v lv2 v3v4v5 o1101 10 ll1 1l0lo 0l1ol 11o10 經過比較分析，可以找到兩幅圖頂點的一種對應關系為：v 1h v ：，v 2hv ， v ；v ，v d v 。，嵋v 。應對鄰接矩陣就是將d 的第1 行與第2 行交換， 第3 行與第5 行交換，再將第l 列與第2 列交換，第3 列與第5 列交換，可得到 變換后的d 等于d 。 遺憾的是，對計算機而言，并不能直接“看”出點與點之間的對應關系， 一個古老而嚴密的算法是：先寫出兩個圖的鄰接矩陣d 與d ，然后對d 進行所 有可能的行、列交換，如果能使d = d ，則判定同構，否則不同構。而“所有 可能的行、列交換”意味著行的全排列與列的全排列，在最壞情況下可能需要”! 次行、列交換，這種算法在點數稍大時就無法忍受了。這種算法的一種改進算法 是對相同度數的頂點進行全排列，即如果圖g ( g ) 有”個度數為i 的頂點，那么 第一章圖的同構披其應用概況 需要重新排列的運算量就減少至m ! n 21 喝h ，當比較幸運時，數量會得到一定 程度的限制，但并不能保證對每一個圖都適用，例如對于每個頂點度數都相同的 正則圖就毫無作用，因此這種改進是相當有限的。 同時，以上篇幅介紹的同構還僅是無向圖范圍內的同構，對于有向圖和帶 權圖以及更廣義上的任意圖的同構判定的研究也還只是處于探索階段。這里對一 部分現有的同構算法做簡單的介紹。 1 2 1v f 算法 lpc o r d e l i a 等人提出的v f 算法 1 0 3 是一種經典的圖匹配算法，用于解決無 向( 子1 圖同構問題。 算法的基本原理為：假設提問圖q g 有m 個頂點，目標圖t g 有”個頂點， m 5 ，根據定義的匹配原則，在q g 與z - g 間可建立映射c ，c 是q g 和丁g 中 相互匹配的頂點對的集合，c 中的元素q = ( m ，n j ) 表示q g 的頂點m ，與t g 的頂 點n j 相互匹配。c 也反映了q g 與t g 中邊的對應關系，即如果c 中含有兩元素 ( ，n j ) 與( m p ，) ，并且( 礙，州，) 是9 g 中的一條邊，則( 療，) 必定是t g 中的一 條邊，并且邊( ，m ，) 和邊( 打，) 匹配。如果c 中包含q g 中的所有頂點，即c 中含有m 個頂點對，則表明q g 是丁g 的子圖( 子結構匹配) ，否則q g 與z t g 不 是子結構匹配。 算法中引入狀態(tài)空間( s s r ) 的概念來描述匹配過程，狀態(tài)空間s 是c 的一個 子集，代表局部匹配，向s 中加入新的滿足條件的頂點對，j 就轉變成下一一個更 大的狀態(tài)空間s 。 算法采用了深度優(yōu)先遍歷的方式，在判定過程中，首先將狀態(tài)空間晶設為 空，表示不存在任何匹配的頂點。對于q g 中的任一頂點，在t g 中尋找滿足匹 配原則的頂點，如果找到則將該頂點對加入到s o 中，如果找不到則回溯到上個 頂點，直到回溯到第一個頂點，如果在丁g 中找不到與q g 的第一個頂點匹配的 頂點，表明兩圖不匹配。其步驟如下： 1 ) 賦初值：s = 。 2 ) 如果s 中包含m 個頂點對，則q g 與丁g 匹配，輸出s ，算法結束。 3 ) 如果q g 的當前頂點是q g 的第一個頂點且在t g 中找不到與之匹配的 頂點，則q o 與t g 不匹配，算法結束。 4 ) 選擇q g 中下一個頂點現。 5 ) 選擇粥中下一個未訪問過的頂點”，如果不存在這樣的頂點則回溯到 第一章圖的同構搜其成用概況 上一級頂點，轉到步驟3 ) 。 6 ) 如果所。與療，滿足上述條件，記為( 卅。，n ，) ，將其加入到s 中，并將狀 態(tài)空間記為s ，如果不滿足條件，則轉到步驟5 ) 。 7 ) 令s = s ，轉到步驟2 ) 。 在最好的情況下，每次匹配只有一對頂點滿足條件，匹配過程中需要訪問 的狀態(tài)空間數與該圖頂點數相同，此時，算法是具備多項式時間復雜度的；在。 些較壞的情況下，需要遍歷所有可能的狀態(tài)空間才能得出結果，而所有的狀態(tài)空 間數正比于圖中頂點數的階乘，進而可能需要較大的開銷的才能得到結果。 1 2 2 基于h o p f i e l d 網絡的圖的同構算法 自從h o p f i e l d 網絡被成功的用于解決t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 這類 困難組合問題以來，許多學者也嘗試應用神經網絡來解決圖的同構問題，提出了 一些基于神經網絡的圖的同構算法。其中文 7 】的作者通過簡化能量函數，并建 立相應的數學理論，給出了一種新的神經網絡求解無向圖同構的改進方法，并通 過進一步分析h o p f i e l d 網絡的拓撲結構，給出了電路實現圖。 對于兩個滿足頂點數與邊數相等條件的n 階無向圖，算法首先構造了一個含 個神經元的h o p f i e l d 網絡，由這些神經元組成置換矩陣，構成兩個圖之間 的映射。根據置換矩陣的性質可以構造相應的能量函數。由于h o p f i e l d 網絡算法 是一種梯度算法，有可能求得能量函數的局部極小，即網絡有可能運行至不希望 的吸引子或吸引環(huán)內，文中所提出的能量函數，當且僅當滿足一定條件時達到能 量函數的最小值0 ，因此在網絡進入穩(wěn)態(tài)之后通過判斷能量是否接近于0 來判斷 該穩(wěn)態(tài)是否是希望的吸引子，若不是則重新產生初值并運行網絡。如此循環(huán)反復 直到網絡進入希望的吸引子，得出兩圖同構，并由網絡穩(wěn)態(tài)輸出兩圖頂點之問的 對應關系；或者網絡運行的迭代次數太多，大于事先給出的門限，得出兩圖不同 構的結論為止。 該算法的獨到之處在于基本上避免了對頂點進行排列運算的情況，因而克服 了其他算法普遍存在的部分頂點全排列的問題。使用該方法處理不同的圖可能需 要選取不同的步長，不恰當的取值可能會導致迭代次數過多造成的誤判。 1 2 3 頂點度數序列法 該算法實際上是由文章”3 先后提出的兩個不同的算法，分別稱為關聯度 第一章| 呈| 的同構及其應用概況 序列法和出入度序列法，前者用于解決無向圖同構的問題，而后者用于解決有向 圖同構的問題，算法涉及到連通子圖，連通子圖的( 出入) 度數，連通子圖的( 出入) 度數序列等概念。 首先，算法定義了聆點連通子圖的概念，即如果由n 個點以及連接于這h 個頂點之間的邊組成的子圖是連通的，該子圖就被稱為n 點連通子圖。隨后，算 法引入了頂點合并的概念，即將兩個任意頂點i 與，重合，并使原來接于i 的邊 都接于，最后再消去這一過程中出現的自環(huán)。文章認為對于同構的有( 無) 向圖 而言，對由各自對應的幾個頊點組成的n 點連通子圖作頂點合并，得到的新圖也 是同構圖。n 點連通子圖作頂點合并后的那個頂點對應的( 出入) 度數，被稱為連 通子圖的( 出入) 度數。所有n 點依次取1 到的所有整數，為原圖頂點數) 連通子圖的( 出入) 度數集合被稱為連通子圖的( 出入) 度數序列。對于同構圖而氰 必然具有嚴格相等的( 出入) 度數序列，因為該序列反映了各個n 點連通子圖層次 卜的點與邊的關系，如果兩圖在結構上有稍許細微的差別，必然造成某一層次n 點連通子圖( 出入) 度數的差別。反之，具有相同的( 出入) 度數序列的兩圖也必然 同構。這一結論是該算法判定兩圖同構的基本依據。 1 3 應用簡介 生產管理、軍事、交通運輸、計算機和通訊網絡等方面許多離散問題的出 現，大大促進了圖論的發(fā)展。進入7 0 年代以后，特別是大型電子計算機的出現， 使大規(guī)模問題的求解成為可能。圖的理論及其在物理、化學、運籌學，計算機科 學、電子學、信息論、控制論、網絡理論、社會科學及經濟管理等幾乎所有學科 領域中各方面應用的研究都得到“爆炸性發(fā)展”。主要有一下三個原因： 1 圖論提供了一個自然的結構，由此而產生的數學模型幾乎適合于所有科 學( 自然科學和社會科學) 領域，只要這個領域研究的主題是“對象”與 “對象”之間的關系。 2 圖論己形成自己的豐富詞匯語言，它能簡潔地表示出各個領域中“對象一 關系”結構復雜而又難懂的概念。圖論的思想和方法越來越被許多科學 領域所接受，并已發(fā)揮且將日益發(fā)揮它的重要作用。反過來，這些得益 于圖論的科學領域又向圖論提出新的研究課題、新的概念和新的研究方 法。 3 圖論提供了大量令人躍躍欲試的智力挑戰(zhàn)性問題，小到初學者的簡單習 題，大到能使所有資深數學家感到棘手且懸而未決的難題。 第一章圖的同構及l(fā) 應用概況 作為圖論研究的一個重要課題，圖的同構判定也在許多應用領域中發(fā)揮著 重要的作用。 1 3 1 運動鏈的同構識別 任何機構的結構都可以用運動鏈結構簡圖表示，機構中構件與運動副的類 型，數量及相互關系，在運動鏈圖上都有明確的表示。機構運動鏈同構的識別是 機構學中的基本概念之一，對機構的結構類型綜合及優(yōu)選結構類型有重要意義： 若將非同構的運動鏈誤判為同構，則可能丟失有價值的新運動鏈：若將本為同構 的運動鏈視為不同，則可能會造成機構類型的重復而失去意義。 機構學在應用圖論進行類型綜合時，通常把機構的運動鏈抽象成拓撲圖， 也稱線圖。拓撲圖中每一個頂點對應機構運動鏈的一個構件，每一邊對應運動鏈 的一個運動副，與頂點關聯的邊數稱為頂點的度數，即為該構件所含運動副數， 如圖1 5 所示。 ( a ) 運動鏈簡圖 圖1 5 ( b ) 拓撲結構圖 有了以上模型，再利用運動鏈的一些特征，即可按照一些現有的運動鏈同 構判定算法n 3 ，“1 進行判別。 1 3 2 漢字的自動識別 漢字已有千年的歷史，也是世界上使用人數最多的文字，對于中華民族燦 爛文化的形成和發(fā)展有著不可磨滅的貢獻，并將繼續(xù)發(fā)揮重要的、其它文字形式 難以取代的作用。然而，漢字是非字母化、非拼音化的文字，在當今高度信息化 的社會里，如何快速高效地將漢字輸入計算機，已成為影響人一機交流信息效率 第一章圖的一構披其應用概況 的一一個重要瓶頸，用計算機來自動識別漢字或者其他象形文字，是當前比較熱門 的一個研究領域，而且取得了長足的進展。漢字的數量繁多，筆畫復雜，而且有 許多字形相近的字。 如圖1 6 所示的兩個漢字，字形就很相似。區(qū)分、識別這一類漢字，圖的同 構判定算法是一個有力的工具。這類漢字，字型雖然相近，但從圖的拓撲結構t 看，它們并不同構。 杭抗 ( a )( b ) 圖1 6 兩個相似的漢字 可以將這兩個漢字抽象成無向圖，并利用關聯度序列法1 進行圖的同構判 斷，具體的應用到這兩個字上，則給出了它們對應的關聯度序列作為這兩個字的 特征識別碼。這種方法已經被作者成功的應用于漢字( 包括印刷體和手寫體) 的識 別中“引6 ，”】，并取得了很好的識別效果。 第一二章任意圖同構判定的基本理論 第二章任意圖同構判定的基本理論 圖論中很多關于圖和同構的定義與討論往往僅限于不帶權值的無向圖。在 這樣的定義下，實際應用中針對不同的應用還需要對具體的圖做相應的限定以使 之能與定義相符合。 本文將在任意圖的框架下展丌同構問題判定及其應用的討論，研究的對象 是任意圖，這就需要重新定義圖論中的一些基本概念，以建立一個完備的對任意 圖的描述，如任意圖鄰接矩陣以及頂點的度等等，然后從這些對拓撲結構的描述 中分析出同構的任意圖所具有的一些性質。同時，因為本文將在電路理論的框架 下討論圖論中的同構問題，在本章中，也會對需要用到的電路相關理論( 主要是 節(jié)點電壓法) 做詳細的介紹。 2 1 任意圖的基本定義 本文所討論的圖的同構判定的對象是任意圖，任意圖包含了無向圖，有向圖， 帶權圖以及由它們組成的混合圖。混合圖中，邊可以是有向的，也可以是無向的， 可以是帶權的，也可以是不帶權的。在此定義下，其它圖均是它的特例。不失一 般性，以后的討論均針對混合圖。 在混合圖中，本文用歷表示有向邊集合，匕表示無向邊集合。從頂點v ，指 向v ，的有向邊用( v 。，v ，) 表示，其權值用，表示( 若無權值規(guī)定w ，可，x 為該圖最 大權值的兩倍) 。頂點q 與v ，之間的無向邊用 v i ，v ，) 表示，其權值用。，表示，對 無向邊顯然有m ，= m 。( 若無權值則規(guī)定m 。= 州。= 。 定義2 1 任意圖鄰接矩陣：具有n 個頂點的混合圖g ，其鄰接矩陣d 是p 階矩陣，矩陣中元素廈為： ，i ( 嘞，w g k , m # ，m 歸，m 婦)( h ，葉) 目或 v j ，o ) g o “1 0( v i , v ，) 萑日且“，v ，) 萑e o 其中，k 和p 分別表示該圖有k 重有向邊和p 重無向邊，w 。表示第k 重有 向邊的權值，m ，。表示第p 重無向邊的權值，權值與m 。內部分別按從小到大 的順序排列( 無權邊的x 靠前) ，這里w l ， 2 ( ，n o ， m 啦 m j ；p 。 與m ，之間用分號隔開，以顯式的區(qū)分有向邊和無向邊。如果兩頂點之間只有有 向邊沒有無向邊，則使用( ，w ，缸；) 表示，只有無向邊沒有有向邊則使用 ( ；m 心刪啦，m ，) 表示，如果既沒有有向邊又沒有無向邊，則簡單的以0 表示， 第一二章任意蚓同構判定的基奉理論 而不再繁瑣的使用( 0 ；o ) 表示了。 由于任意圖鄰接矩陣僅涉及頂點與頂點的關系，在后面的圖中，邊就不再 獨立標號了，對于帶權邊則僅使用數字標出其權值。為避免混淆，頂點使用數字 加圈的形式表示，如頂點1 使用表示。 如圖2 1 中的混合圖g 與g ，按上述規(guī)則它們對應的任意圖鄰接矩陣分別是 d 與d 。 1 2 d = 3 4 ( a ) 圖g( b ) 圖g 圖2 1 兩個任意圖同構的例子 ( 0 ) ( ；1 ) ( ；1 ) ( 0 ) ( 0 ) ( 2 ；) ( ；1 )( ；x ) ( 0 )( ；1 ) ( 1 ；)( ；x ) ( 0 ) ( x ，2 ；x ) ( ；x )( 0 ) 1 d ：2 3 4 ( 0 ) ( ；1 ) ( 0 )( ；1 ) ( ；1 ) ( 0 ) ( 1 ；)( ；x ) ( 0 ) ( 2 ；) ( 0 ) ( x ，2 ；x ) ( ；1 ) ( ；x ) ( ；x )( 0 ) 圖中g 與g 各有4 個頂點，于是它們的任意圖鄰接矩陣是4 4 階矩陣，以 g 為例在頂點到頂點之間有一條權值為2 的有向邊，一條不帶權值的有向邊， 以及一條不帶權值的無向邊，這里最大的權值為2 ，所以x - = 4 于是d 3 。：( x ，2 ；x ) 。 顯然這里無需作任何行、列交換，兩圖的鄰接矩陣d = d ，所以可以直接判定 這兩個圖同構。觀察圖2 1 ，可以發(fā)現本例中的兩個圖對應的頂點剛好為 l 一1 ，2 2 ，3 3 ，4 4 ，這和剛才的d = d 是等價的。 定義2 2 頂點v l 與毒條無向邊，d 。+ 屈條有向邊相接( 其中口。表示背離頂點 葉的有向邊，屈表示指向頂點q 的有向邊) ，亦即頂點v 的無向邊度數為毒，有 向邊出度為口，入度為屈，于是該頂點的度數集 = 口，屈；毒 。 以上兩個定義不失一般性的包含了所有可能的圖，當f - ，時( v ，v ，) 或 v ，v ， 表示的就是一個無向自環(huán)或有向自環(huán)，特別地，帶自環(huán)的情況將在第四章算法部 分末尾加以說明，因此下面討論的任意圖建模將暫不考慮自環(huán)情況，因此，鄰按 矩陣的對角元素保持全0 。 第二章任意圖同構判定的基t 本理論 由定義2 2 對頂點度數集的定義，可知圖2 1 的g 中4 個頂點的度數集分別 為：丑= 0 ，0 ；2 ) ，五= 1 ，1 ；2 ) ，也= 3 ，1 ；1 ) ，丑= o ，2 ；3 ) ，很明顯，g 中頂點的 度數集與g 一一對應相等。 實際上，定義任意圖頂點的度數集為任意圖同構的判定提供了一個重要的 必要條件，即兩個同構的任意圖所含相同度數集的頂點數相同。 由于采用了無向邊與有向邊及其對應的度分別定義的形式，同時在矩陣元 素的定義上又將權值和邊的重數分離開來，以上兩個定義所規(guī)定的任意圖鄰接矩 陣和度數集唯一的確定了一個混合圖，第一章所介紹的基礎圖，對稱有向圖和定 向圖，都可以通過這種方法唯一的確定，如圖2 2 所示，它們對應的任意圖鄰接 矩陣分別是d ，b 與協(xié)。 ( a ) 基礎圖g 7 心入 綹厶匈 ( b ) 對稱有向圖g d ( c ) 定向圖g 。 圖2 2 123 1 d2 d3 d 1 i ( 0 ) ( ；1 ) ( ；1 ) l d i ( o ) ( 1 ；) ( 1 ；) d = 2 i ( ；1 ) ( 0 ) ( ；1 ) id = 2 d i ( 1 ；) ( 0 ) ( 1 ；) 3 l ( ；1 ) ( ；1 ) ( o ) j3 。m ) ( 1 ；) ( o ) g ，q 和q 中各頂點的度數集分別為： = 0 ，0 ；2 ) 4 = 2 ，2 ；0 ) 如= ( o ，0 ；2 以= 2 ，2 ；0 如= o ，0 ；2 ) 五= 2 ，2 ；0 根據以上定義，得到以下定理。 1 h2 3 1 小o ) ( o ) ( 1 ；) 1 d = 2 。if 1 ：) ( 0 ) ( 0 ) j3 ：l i o ) ( 1 ；) ( o ) j = l ，1 ；0 如= l ，1 ；0 ) 厶= 1 ，1 ；0 ) 定理2 , 1 兩個任意圖g 與g 同構的充要條件是存在一個置換矩陣p ，使 得任意圖鄰接矩陣有 d = p d j p 即經過一定的行、列變換能夠使g 與g 對應的點處于鄰接矩陣中行與列的 相同位置。 顯然，同構圖經過一定的行、列變換后必然具有相同的任意圖鄰接矩陣。 第二章任意圖同構判定的基率理論 為了便于表述，在后面的討論中，直接用鄰接矩陣指代定義2 1 所規(guī)定的任 意圖鄰接矩陣。 將定義1 6 拓展到任意圖，得到如下同構定義 定理2 2 如果兩個圖g 與g 的點之間一一對應，邊之間一一對應，對應 點與對應邊之間保持相同的關聯關系，同時對應邊上具有相同的權值，那么g 與g 同構。 定理2 2 中所指的邊包含了有向邊與無向邊，權值包含了有向邊權值與無向 邊權值。 由定理2 1 ，經過一定的行、列變換能夠使同構圖g 與g 。對應的點處于鄰 接矩陣中行與列的相同位置。所以g 與g 的鄰接矩陣的“行列式”的值也相等。 因為定義2 1 所規(guī)定的鄰接矩陣并不是一個二維矩陣，無法直接得到對應的行列 式的值，需要對它作以下規(guī)定。 定義2 3 將鄰接矩陣d 按有向邊和無向邊的分類分為兩個矩陣d 和d ， 將n 和n 的空白處用0 填滿，使這兩個矩陣中所有元素的維數均達到各自矩陣 中包含的最大有向邊重邊數k 和無向邊重邊數p ，稱口為有向邊鄰接矩陣，皿為 無向邊鄰接矩陣，當k 與p 都不為1 時，d 1 和n 是兩個三維矩陣，按第三維分 別將d l 和d 2 兩個矩陣分為k 個兩維矩陣和p 個二維矩陣q ，d l ：，d l 。與 d 2 ，d 2 ：，d 2 。，如k 或p 等于1 ，則相應的矩陣不需要再做細分，于是d 的行 列式集i d l = f 日。i ，id 1 ：卜，i d , 。i ；i d ，卜，ld 2 ，j 。 如鄰接矩陣只含有向邊或無向邊，則與鄰接矩陣的表達一樣，直接留空， 分號照寫。 定理2 3同構圖鄰接矩陣的行列式集相等 對照定理2 2 ，定義2 3 規(guī)定的行列式集實際上是將求取任意圖的行列式問 題變成了求取有向圖行列式和無向圖行列式兩個問題，因為鄰接矩陣元素中有向 邊和無向邊如果帶重數的話，權值是分別按增序排列的，而這里的每一個二維矩 陣實際上都是一組相同排序的邊( 位于相同重數層次上的邊) 對應的鄰接矩陣的 行列式，所以兩個同構圖必須滿足所有細分出來的二維矩陣都要一一1 。對應相等， 所以它們的行列式集是相等的。 這是一個必要條件，不同構的圖也可能有相同的行列式集，而且對細分的 有向邊子圖和無向邊子圖而言，在混合圖中并沒有保證它們分別連通的限定，此 時每個子圖對應的鄰接矩陣行列式的值實際上都是0 ，但使用行列式集作為判據 對于大量實際應用中涉及到的圖而言，依然是較為有效的，可以用于初步篩選待 判定的圖。 以下頁圖2 3 ( a ) ( b ) e og 與g 為例，而顯然原拓撲圖是不同構的，其中存在 釜三量堡童里塑塑型塞竺苧查型墮 連通的無向子圖，于是在這里使用它們的鄰接矩陣d 和d 構造行列式集l d i 與 i d f 是有效的，并可直接得到不同構的結論，具體過程如下所示。 ( a ) 圖g 1 l ( 0 ) ( ；l ，2 ) ( ；1 ) d = 2 j ( 1 ，2 ) ( 0 ) ( ；1 ) j 3 l ( 2 ；1 ) ( 2 ；1 ) ( o ) j 圖2 3 ( b ) 圖g l 1 l ( 0 ) d = 2 j ( ；1 ) 3 l ( o ；2 ) 2 3 ( 2 ；1 ) ( 1 ；2 ) ( 0 ) ( ；1 ，2 ) j ( 1 ，2 ) ( 0 ) j 將d 按有向邊和無向邊分為兩個矩陣，并將矩陣空白處用0 填滿，使每個 元素的維數均達到該矩陣中包含的最大重邊數，得到有向邊關聯矩陣口，和無 1 l ( 0 ) ( 0 ) ( 0 ) |1 ( 0 ，o ) ( 1 ，2 ) ( 1 ，o ) d f = 2 ( 0 ) ( 0 ) ( 0 ) i砬= 2 2 ) ( 0 , 0 ) ( 1 ，0 ) 3 l ( 2 ) ( 2 ) ( o ) j3 l ( 1 ，0 ) ( 1 ，0 ) ( o ，0 ) i 對d f 矩陣，叱中不含重邊，直接寫成以下形式 1 10 0 0l d ij = 2 100 0l 對d 2 矩陣，d 2 ，中含兩個重邊，先后分兩次提出d 2 。中的邊，組成下面兩個 第二章任意幽同構判定的基本理論 昕卜弼o i d i 。i = ol d 2 ，i _ 2i d 2 ：i - o ， t & i d l = 0 ；2 ，0 ) 。 重復相同的步驟可得l d l _ 0 ；4 ，0 j ，i d l i d l ，所以可直接判定g 與g 不 2 2 線形時不變網絡的節(jié)點電壓分析法 在用“網絡拓撲”理論研究網絡時，首先將電網絡抽象成反映網絡結構的線 性圖( 拓撲圖) 。即用一個線段代替兩端元件，且稱之為支路，并用b k 表示第k 條 支路，用一個點代替元件問的連接點，且稱之為節(jié)點，并用胛表示第f 個節(jié)點。 一個節(jié)點和支路的集合，并且其中支路僅在節(jié)點相交，則此集合稱為線性圖或簡 稱為圖。 電學和電路的基本理論告訴我們： 對集中參數網絡的任一節(jié)點，流入或流出電流的代數和為零。這就是克?；?夫電流定律( k c l ) 。 對集中參數網絡的任一回路，其電壓降的代數和為零。這就是克希霍夫電壓 定律( k v l ) 。 節(jié)點電壓法是以節(jié)點電壓為求解電路的未知量，利用k c l 和支路的伏安關 系( v c r ) 導出仰一1 ) 個獨立節(jié)點電壓為未知量的方程，聯立求解，得出各節(jié)點電 壓，然后進一步求出網絡各待求量的方法。 節(jié)點電壓法適用于結構復雜、非平面電路、獨立回路選擇麻煩、以及節(jié)點少、 回路多的電路的分析求解。對于行個節(jié)點、坍條支路的電路，節(jié)點電壓法僅需 m 一1 ) 個獨立方程。 在網絡中，任選一個節(jié)點為參考節(jié)點( 一般選取編號最大的一個節(jié)點) ，其余 每個節(jié)點與參考節(jié)點之間的電壓，分別稱為該節(jié)點對應的的節(jié)點電壓。節(jié)點電壓 的參考極性均以所對應節(jié)點為正極性端，以參考節(jié)點為負極性端。顯然，節(jié)點電 壓數比節(jié)點數少一個。對于具有h 個節(jié)點的網絡，有n 一1 個節(jié)點電壓，其中節(jié)點 心對應的節(jié)