1、會計學1圖和子圖圖和子圖第一頁，共65頁。第1頁/共65頁第二頁，共65頁。第2頁/共65頁第三頁，共65頁。第3頁/共65頁第四頁，共65頁。Knigsberg七橋問題電網絡(wnglu) 四色猜想第4頁/共65頁第五頁，共65頁。12,v vv L Leee,21defG = (V, E)p q abc k 第5頁/共65頁第六頁，共65頁。defG = (V, E)p q abc k 第6頁/共65頁第七頁，共65頁。( )( ) , ( )( ) .GV GGE G defG = (V, E)p q abc k 第7頁/共65頁第八頁，共65頁。2第8頁/共65頁第九頁，共65頁。第9

2、頁/共65頁第十頁，共65頁。 a y zx wb c d e G=(V, E) x d w a b c y e z F=(V, E) x w b c d e a yz H=(V, E) 第10頁/共65頁第十一頁，共65頁。)()(:FVGV)()(:FEGE( )( ) ( ), ( )euveuvE G a y zx wb c d e G=(V, E) x w b c d e a yz H=(V, E) x d w a b c y e z F=(V, E) 第11頁/共65頁第十二頁，共65頁。注注 兩個圖同構是指兩個圖同構是指”它們有相同的結構它們有相同的結構”，僅在頂點及邊的標號上或

3、兩個圖的畫法上有，僅在頂點及邊的標號上或兩個圖的畫法上有 所不同所不同(b tn)而已。往往將同構慨念引伸到非標號圖中，以表達兩個圖在結構上是否相同。而已。往往將同構慨念引伸到非標號圖中，以表達兩個圖在結構上是否相同。注注 判定兩個圖是否同構是個未解決的困難問題（判定兩個圖是否同構是個未解決的困難問題（open problem）。）。 a y zx wb c d e G=(V, E) x w b c d e a yz H=(V, E) x d w a b c y e z F=(V, E) 第12頁/共65頁第十三頁，共65頁。K1K2K3K4K5第13頁/共65頁第十四頁，共65頁。二部圖K3

4、,3K1,5K2,2,2第14頁/共65頁第十五頁，共65頁。第15頁/共65頁第十六頁，共65頁。 第16頁/共65頁第十七頁，共65頁。 圖 1 圖 2 圖 3 第17頁/共65頁第十八頁，共65頁。n kmk2112()第18頁/共65頁第十九頁，共65頁。nnvvvHVuuuGV,)(,)(2121奇數)()()(jGiGjiududHEvv),(EVGVwvuEuwEvwuv,2第19頁/共65頁第二十頁，共65頁。第20頁/共65頁第二十一頁，共65頁。eeeeeeeM Gvvvv123456712341100101111000000110010001120( ) e1e2e3e4

5、e5e6v1v2v3v4G = (V, E)e7第21頁/共65頁第二十二頁，共65頁。vvvvAGvvvv123412340211201011011011( )第22頁/共65頁第二十三頁，共65頁。的關聯邊。第23頁/共65頁第二十四頁，共65頁。( )2 .v Vd v 第24頁/共65頁第二十五頁，共65頁。( ), .d vkvV 0-正則圖1-正則圖2-正則圖3 -正則圖第25頁/共65頁第二十六頁，共65頁。第26頁/共65頁第二十七頁，共65頁。vvv,21diin1第27頁/共65頁第二十八頁，共65頁。第28頁/共65頁第二十九頁，共65頁。第29頁/共65頁第三十頁，共6

6、5頁。 fea bc dghG=(V, E) x wvyuGu,w,x Gu,w,x,y Gc,d,eGf, c 第30頁/共65頁第三十一頁，共65頁。 fea bc dghG=(V, E) x wvyubc dhx wvyufeac hxwvyuxfeahwvyu第31頁/共65頁第三十二頁，共65頁。第32頁/共65頁第三十三頁，共65頁。第33頁/共65頁第三十四頁，共65頁。第34頁/共65頁第三十五頁，共65頁。uvyxweabdhcfg第35頁/共65頁第三十六頁，共65頁。uyvywvyxyx第36頁/共65頁第三十七頁，共65頁。),(vunjivvvvvW,10vvuvn

7、,0jivv ji njivvvvvW,110),(vu第37頁/共65頁第三十八頁，共65頁。圖 G 第38頁/共65頁第三十九頁，共65頁。n稱 G為非連通圖(G) 1。第39頁/共65頁第四十頁，共65頁。SSS第40頁/共65頁第四十一頁，共65頁。S第41頁/共65頁第四十二頁，共65頁。n一個不連通一個不連通(lintng)的的(/2-1)正則簡單圖。正則簡單圖。jivv ,1221第42頁/共65頁第四十三頁，共65頁。第43頁/共65頁第四十四頁，共65頁。第44頁/共65頁第四十五頁，共65頁。第45頁/共65頁第四十六頁，共65頁。uvyxweabdhcfg第46頁/共65

8、頁第四十七頁，共65頁。第47頁/共65頁第四十八頁，共65頁。證明：設G的2-劃分為（X, Y），由G的定義，G的任一圈中，X和Y的頂點一定交錯出現，從而其長必為偶數。：不妨設G為 連通(lintng)的。 任取一頂點u,令 X = xV d(u, x) = 偶數 , Y = yV d(u, y) = 奇數。易見，(X, Y)為V的2-劃分，第48頁/共65頁第四十九頁，共65頁。PQuP Quvw第49頁/共65頁第五十頁，共65頁。21)(ud)()(uGuG第50頁/共65頁第五十一頁，共65頁。第51頁/共65頁第五十二頁，共65頁。第52頁/共65頁第五十三頁，共65頁。第53頁/

9、共65頁第五十四頁，共65頁。)(GEew ee E H( )()第54頁/共65頁第五十五頁，共65頁。第55頁/共65頁第五十六頁，共65頁。n v u 0 者者 .n得得 S1 = S0 u1 , P1 = u 0u1 .Sk第56頁/共65頁第五十七頁，共65頁。Sk1Sk1Sk1第57頁/共65頁第五十八頁，共65頁。 Sk = Sk-1 uk , Pk = Pj ujuk 某 j 1,2，k-1 。update 進行(jnxng)下一 步時，只要更新 l(v) 即可： l( v ) min l( v ) , l( uk ) + w( ukv ) 對 v Sku 0u jvu kS k-1S k-1S k第58頁/共65頁第五十九頁，共65頁。Sk第59頁/共65頁第六十頁，共65頁。S第60頁/共65頁第六十一頁，共65頁。復雜性n=1020304050n3.001sec .008sec .027sec.064sec.125secn5.1sec3.2sec24.3sec1.7min5.2min2n.001sec1.0sec17.9min 12.7days35.7year