›
›

Bài giảng Đại số lý thuyết đồ thị - Trương Mỹ Dung

pdf 54 trang phuongnguyen 2500
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Đại số lý thuyết đồ thị - Trương Mỹ Dung", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdai_so_ly_thuyet_do_thi_truong_my_dung.pdf

Nội dung text: Bài giảng Đại số lý thuyết đồ thị - Trương Mỹ Dung

  1. ĐẠI SỐ LÝ THUYẾT ĐỒ THỊ
  2. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. CHÖÔNG 1. CAÙC KHAÙI NIEÄM CÔ BAÛN VEÀ ÑOÀ THÒ. 1.1 ÑÒNH NGHÓA & THÍ DUÏ. 1.1.1 ÑÒNH NGHÓA. 1.1.1.1 Ñoà thò coù ñònh höôùng. Moät ñoà thò G = G(X,U) ñöôïc xaùc ñònh bôûi § Taäp höõu haïn X = {x 1,x2, , xn} taäp caùc ñænh hay nuùt. § Taäp U = {u 1,u 2, ,u n} Ì X x X taäp caùc cung (caïnh). Ñoái vôùi moät cung u = (xi, xj), xi laø ñænh ñi, xj laø ñænh ñeán (hay coøn goïi laø goác vaø ñích). Cung u ñi töø xi vaø ñeán xj. Cung u döôïc bieåu dieãn moät caùch hình hoïc nhö sau : xi xj FIG.1.1. Cung u=(x i, xj) Moät cung (x i, xi) ñöôïc goïi laø moät voøng (khuyeân). Moät p-ñoà thò laø moät ñoà thò trong ñoù khoâng coù quaù p cung döôùi daïng (i,j) giöõa hai ñænh baát kyø. Thí duï. x1 u4 x4 u8 u7 u1 u3 u5 x5 u6 x2 u2 x3 FIG. 1.2. Ñoà thò xaùc ñònh bôûi (X,U), X = {x1, x 2, x3, x4, x5} ; U = {u1, u2, u3, u 4, u5, u6, u 7, u8} Tröông Myõ Dung 1
  3. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. 1.1.1.2 Ñoà thò khoâng ñònh höôùng. Khi khaûo saùt moät vaøi tính chaát, söï ñònh höôùng cuûa caùc cung khoâng ñoùng moät vai troø gì. Ta chæ quan taâm ñeán söï hieän dieän cuûa caùc cung giöõa hai ñænh maø thoâi (khoâng caàn ñònh roõ thöù töï). Moät cung khoâng ñònh höôùng ñöôïc goïi laø caïnh. Ñoái vôùi moät caïnh u = (xi,xj), u ñöôïc goïi laø CAÏNH TÔÙI cuûa hai ñænh xi vaø xj. Thí duï. x1 u6 x4 u7 u1 u2 u3 u4 x5 u8 x2 u5 x3 FIG. 1.3. Ñoà thò xaùc ñònh bôûi (X,U), X = {x 1, x2, x 3, x4, x 5} ; U = {u1, u 2, u3, u4, u 5, u6, u7, u8} Moät ñoà thò ñöôïc goïi laø ña ñoà thò neáu coù nhieàu hôn moät caïnh giöõa hai ñænh. Moät ñoà thò ñöôïc goïi laø ñôn neáu: 1. Khoâng phaûi laø ña ñoà thò ; 2. Khoâng toàn taïi moät voøng naøo. Hai caïnh u vaø v ñöôïc goïi laø song song khi chuùng cuøng laø caïnh tôùi cuûa hai ñænh phaân bieät. Kyù hieäu u ¦ v. Theo thí duï treân, ta coù u1 ¦ u2 Tröông Myõ Dung 2
  4. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. 1.1.1.3 Moät soá ñònh nghóa cô baûn. § AÙNH XAÏ ÑA TRÒ. v xj ñöôïc goïi laø ÑÆNH SAU (SUCCESSEUR) cuûa xi neáu (x i,x j) Î U; Taäp caùc ñænh sau cuûa xi kyù hieäu laø G(xi). v xj ñöôïc goïi laø ÑÆNH TRÖÔÙC (PREDECESSEUR) cuûa xi neáu -1 (xj,xi) Î U; Taäp caùc ñænh tröôùc cuûa xi kyù hieäu laø G (xi). v Aùnh xaï G ñöôïc ñònh nghóa :vôùi moïi phaàn töû cuûa X, töông öùng vôùi moät taäp con cuûa X ñöôïc goïi laø moät AÙNH XAÏ ÑA TRÒ. v Ñoái vôùi moät 1-ñoà thò, G coù theå hoaøn toaøn xaùc ñònh bôûi (X,G), ñaây laø moät kyù hieäu cô sôû thöôøng duøng trong caáu truùc döõ lieäu : DANH SAÙCH KEÀ. THÍ DUÏ. Trong ñoà thò ñöôïc ñònh nghóa ôû hình veõ sau. X = {x1,x2,x 3,x 4,x5}; G(x1) = x2 ; G(x2) = {x3,x4} ; G(x3)={x4,x 5} ; G(x 4)={x 1} ; G(x 5)={x4}. x1 x4 x5 x2 x3 FIG. 1.4. Ñoà thò xaùc ñònh bôûi (X,G) § KEÀ. v Hai ñænh ñöôïc goïi laø keà neáu chuùng ñöôïc noái bôûi moät cung (caïnh). v Hai cung (caïnh) ñöôïc goïi laø keà neáu chuùng coù ít nhaát moät ñænh chung. § BAÄC CUÛA ÑÆNH. + v Nöûa baäc ngoaøi cuûa ñænh x i , kyù hieäu d (xi) laø soá caùc cung khôûi ñaàu töø + (hay ñi ra töø) xi . Ta coù d (xi) = card (G(x i)). (kyù hieäu card(A) chæ soá phaàn töû cuûa taäp A). - v Nöûa baäc trong cuûa ñænh xi , kyù hieäu d (xi) laø soá caùc cung keát thuùc taïi - -1 (hay ñi vaøo töø) xi . Ta coù d (xi)=card(G (xi)). + - v Baäc cuûa ñænh xi , d(xi) = d (x i) + d (xi). Baäc cuûa moät ñænh trong moät ñoà thò khoâng ñònh höôùng laø toång soá caùc caïnh tôùi cuûa noù. Baäc cuûa moät ñænh coù voøng ñöôïc coäng theâm 2 cho moãi voøng. THÍ DUÏ. [xem FIG. 1.4]. + - d (x 2)= 2 ; d (x2)= 1 ; d(x 2)=3. Tröông Myõ Dung 3
  5. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. + - d (x 4)= 1 ; d (x4)= 3 ; d(x 4)=6. (Vì taïi ñænh x4 coù moät voøng). v Ñænh coù baäc = 0 ñöôïc goïi laø ñænh coâ laäp. v Ñænh coù baäc = 1 ñöôïc goïi laø ñænh treo vaø cung (caïnh) tôùi cuûa noù ñöôïc goïi laø caïnh treo. v ÑÒNH LYÙ (coâng thöùc lieân heä giöõa baäc vaø soá caïnh). 1. Toång baäc caùc ñænh = 2 x soá caïnh. 2. Xeùt ñoà thò coù ñònh höôùng G = (X, U). Ta coù å d +(x) = å d-(x) = card(U) (soá cung). CHÖÙNG MINH. Truy chöùng theo ñænh. v HEÄ QUAÛ. Soá ñænh baäc leû laø soá chaún. CHÖÙNG MINH. å d(ñænh baäc leû) + å d(ñænh baäc chaún) = 2 x soá caïnh. § ÑOÀ THÒ BUØ. G = (X, U) vaø `G = (X,`U). (xi,xj) Î U Þ (xi,xj) Ï `U et (x i,x j) ÏU Þ (xi,xj) Î`U. `G ñöôïc goïi laø ñoà thò buø cuûa G. § ÑOÀ THÒ RIEÂNG PHAÀN (BOÄ PHAÄN). G=(X,U) vaø U p Ì U. G p=(X,U p) laø moät ñoà thò rieâng phaàn cuûa G ; § ÑOÀ THÒ CON. G=(X,U) vaø X s Ì X. G s=(X s,V) laø moät ñoà thò con cuûa G; trong ñoù V laø thu heïp cuûa haøm ñaëc tröng cuûa U treân Xs. V={(x,y)/(x,y) Î UÇXs x X s}. "xi Î X s, Gs(xi)=G(xi)ÇXs. § ÑOÀ THÒ CON RIEÂNG PHAÀN. Toång hôïp hai ñònh nghóa treân. THÍ DUÏ. Maïng giao thoâng ñöôøng boä caû nöôùc. v Maïng xe bus : ñoà thò rieâng phaàn. v Maïng giao thoâng ñöôøng boä T.P. Hoà Chí Minh: ñoà thò con. v Maïng xe bus T.P. Hoà Chí Minh: ñoà thò con rieâng phaàn. Tröông Myõ Dung 4
  6. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. § ÑOÀ THÒ ñoái xöùng : (x i,x j) Î U Þ (xi,xi) Î U. § ÑOÀ THÒ phaûn ñoái xöùng : (x i,xj) Î U Þ (xj,xi) Ï U. § ÑOÀ THÒ phaûn chieáu : (x i,x i) Î U, " x i Î U. § ÑOÀ THÒ baéc caàu : (xi,xj) Î U, (x j,x k) Î U Þ (x i,xk) Î U. § ÑOÀ THÒ ñaày ñuû : (xi,xj) Ï U Þ (xj,xi) Î U (coù duy nhaát moät caïnh giöõa hai ñænh). Moät ñoà thò ñuû coù n ñænh seõ coù n(n-1)/2 caïnh. Kyù hieäu Kn. § CLIQUE :Taäp caùc ñænh cuûa moät ñoà thò con ñaày ñuû. § ÑOÀ THÒ HAI PHAÀN (LÖÔÕNG PHAÂN) G=(X,U) neáu : 1. X phaân hoaïch thaønh X1 vaø X2. 2. " (x1,x2) Î U thì x1 Î X1, x 2 Î X2. Neáu Card(X1) = n, Card(X 2) = m, kyù hieäu Kn,m . Thí duï : Ñoà thò sau löôõng phaân, nhöng khoâng ñaày ñuû. K 2,2 K3,2 § ÑEÀU. Laø ñoà thò maø moïi ñænh coù cuøng baäc. THÍ DUÏ. x2 x1 x4 x3 FIG. 1.5. Ñoà thò phaûn chieáu , phaûn ñoái xöùng, baéc caàu vaø ñaày ñuû. Tröông Myõ Dung 5
  7. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. 1.1.2 THÍ DUÏ. § THÍ DUÏ 1. Ñöôøng ñi ngaén nhaát. Baøi to aùn 1. Cho moät ñoà thò coù ñònh höôùng, G = (X,U), moät ñònh giaù v : U ® R vaø s, t laø hai ñænh phaân bieät cuûa X. Baøi toaùn ñaët ra . Tìm ñöôøng ñi ngaén nhaát giöõa s vaø t ? Lôøi giaûi. Thuaät giaûi Dijkstra, Bellman-Ford (xem Chöông 3). ` § THÍ DUÏ 2. Caây phuû toái thieåu. Xeùt baøi toaùn treân moät maïng, chaúng haïn maïng cung caáp ñieän, nöôùc töø moät nguoàn duy nhaát. Baøi toaùn 2. Moät ñoà thò khoâng ñònh höôùng G = (X,U), moät haøm ñònh giaù troïng löôïng v : U ® R+ vaø hai ñænh phaân bieät s, t cuûa X. Baøi toaùn ñaët ra . Tìm moät caây phuû vôùi trong löôïng toái thieåu ? Lôøi giaûi : Thuaät giaûi Kruskal, Prim (xem Chöông 2). Tröông Myõ Dung 6
  8. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. 1.2 BIEÅU DIEÃN ÑOÀ THÒ. Coù raát nhieàu caùch ñeå bieåu dieãn ñoà thò. Tuy nhieân, caùc caùch bieåu dieãn naøy khoâng töông ñöông vôùi nhau theo quan ñieåm cuûa caùc thuaät toaùn. Ngöôøi ta, phaân bieät moät vaøi caùch bieåu dieãn chính, chaúng haïn bieåu dieãn baèng ma traän keà, ma traän tôùi ñænh – cung (hay ñænh – caïnh trong tröôøng hôïp khoâng ñònh höôùng) vaø baèng danh saùch keà. 1.2.1 Bieåu dieãn baèng caùch söû duïng caùc Baûng. 1.2.1.1. Ma traän keà. Xeùt moät 1 - ñoà thò coù n ñænh. Ma traän keà laø moät ma traän (n x n) coù n haøng töông öùng vôùi caùc ñænh khôûi ñaàu vaø n coät töông öùng vôùi caùc ñænh keát thuùc, ñöôïc ñònh nghóa nhö sau : xij = 1 (True) neáu coù moät cung (caïnh) noái x i vaø xj. = 0 (False) ngöôïc laïi. THÍ DUÏ. x 2 u2 u 1 u4 x1 u3 x3 FIG.1.6. 1. Ñoà thò. Ma traän keà cuûa ñoà thò naøy nhö sau : x1 x2 x3 ¬ keát thuùc x1 0 1 1 x2 1 0 1 x3 0 0 0 • khôûi ñaàu Tröông Myõ Dung 7
  9. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. 1.2.1.2. Ma traän tôùi ñænh – cung (ñænh – caïnh). v Doøng « ñænh. v Coät « cung (caïnh). Cho ñoà thò G = (X, U). Moät ma traän tôùi A = [aij]] ñöôïc ñònh nghóa nhö sau : Neáu caïnh u = (x i, xj)  U thì treân coät u, aiu = 1, aju = -1, ngöôïc laïi thì coù giaù trò 0. THÍ DUÏ. Ñoái vôùi 1. Ñoà thò ôû hình FIG .1.6. ta coù : U1 u2 u3 u4 x1 1 -1 1 0 x2 -1 1 0 1 x3 0 0 -1 -1 CHUÙ YÙ : Toång caùc doøng baèng khoâng (moät cung coù ñænh goác vaø moät ñænh keát thuùc). Taát caû caùc ma traän con vuoâng ñeàu coù ñònh thöùc baèng 1, -1 hay 0. Coù moät caùch khaùc cho ma traän tôùi nhö sau : Cho ñoà thò G = (X, U). Moät ma traän tôùi A = [aij]] ñöôïc ñònh nghóa nhö sau : aiu = 1 neáu u = (xi,xj) Î U = 0 ngöôïc laïi. THÍ DUÏ. Ñoái vôùi 1. Ñoà th ò ôû hình FIG .1.6. ta coù : u1 u2 u3 u4 x1 1 0 1 0 x2 0 1 0 1 x3 0 0 0 0 CHUÙ YÙ : Toång caùc doøng baèng soá caùc cung tôùi. 1.2.2 Bieåu dieãn baèng caùch söû duïng caùc con troû. Lôïi ích cuûa caùch bieåu dieãn baèng con troû hay Danh saùch keà (nhôø vaøo aùnh xaï ña trò G) laø giaûm thieåu choå trong boä nhôù. THÍ DUÏ. Ñoái vôùi 1.ñoà thò cuûa hình FIG.1.6. ta coù : x1 x2 x3 x2 x1 x3 z x3 Tröông Myõ Dung 8
  10. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. 1.3 PHEÙP DUYEÄT ÑOÀ THÒ. (Parcours de graphes). Nhieàu baøi toaùn treân ñoà thò caàn khaûo saùt söï veùt kieät caùc ñænh vaø caùc cung (caïnh) cuûa ñoà thò. Coù 2 caùch duyeät ñoà thò : pheùp duyeät theo chieàu saâu (Parcours en profondeur) vaø pheùp duyeät theo chieàu roäng (Parcours en largeur). 1.3.1. DUYEÄT THEO CHIEÀU SAÂU. NGUYEÂN LYÙ : Khôûi töø moät ñænh, ñi theo caùc cung (caïnh) xa nhaát coù theå. Trôû laïi ñænh sau cuûa caïnh xa nhaát, tieáp tuïc duyeät nhö tröôùc, cho ñeán ñænh cuoái cuøng. Thí duï. Ta coù ñoà thò theo hình veõ sau : s7 s1 s5 s8 s6 s3 s2 s4 s9 FIG. 1.7. Pheùp duyeät theo chieàu saâu thöïc hieän treân ñoà thò ôû hình FIG.1.7 nhö sau : § Khôûi töø ñænh s1. Ñænh ñaàu tieân ñöôïc duyeät laø s3. § Khôûi töø ñænh s3. Ñænh ñöôïc duyeät laø s2. Ñænh sau cuûa s3 laø s6. § Khôûi töø ñænh s6. Ñænh sau cuûa s1 laø s5. § Khôûi töø ñænh s5. Ñænh sau cuûa s1 laø s7. § Khôûi töø ñænh s7. § Khôûi töø ñænh s4. Ñænh ñöôïc duyeät laø s9. § Khôûi töø ñænh s8. § Keát thuùc vì taát caû caùc ñænh ñaõ ñöôïc duyeät. Tröông Myõ Dung 9
  11. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. Kyù hieäu : s[k], k : 1 n laø taäp ñænh coù n phaàn töû, ñöôïc ñaùnh soá thöù töï töø 1 ñeán n. Mark[k], k : 1 n laø haøm nguyeân : = 1 neáu ñænh ñaõ ñöôïc duyeät (coù nghóa ñaõ ñöôïc ñaùnh daáu), = 0 ngöôïc laïi. Ma traän keà a, ñöôïc ñònh nghóa nhö sau : a[i,j] = 1, neáu (i,j) laø moät cung (caïnh ) cuûa ñoà thò G. = 0 ngöôïc laïi. Daïng ñeä qui. Chöông trình chính : For (int i =1; i £ n ;i++) Mark[i] = 0 ; For (int i =1; i £ n ;i++) if( Mark[i] == 0) then DFS(i) ; Thuû tuïc ñeä qui : Duyeät theo chieàu saâu baét ñaàu töø ñænh k. Thuû tuïc DFS(int k) ; { Mark[k] = 1 // Duyeät caùc ñænh trong ma traän keà cuûa ñænh k For (int j =1; j £ n ;j++) if (Mark[j] == 0 && a[k][j]==1) DFS(j) ; } End DFS Ñoä phöùc taïp cuûa giaûi thuaät :Ñoà thò coù n ñænh vaø m cung(caïnh). § Tröôøng hôïp löu tröõ ñoà thò döôùi daïng ma traän keà : O(n2). § Tröôøng hôïp löu tröõ ñoà thò döôùi daïng danh saùch keà : O(max(n,p) ). Tröông Myõ Dung 10
  12. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. 1.6.2. DUYEÄT THEO CHIEÀU ROÄNG. NGUYEÂN LYÙ : § Khôûi töø moät ñænh s baát kyø, ta duyeät taát caû nhöõng ñænh sau cuûa S,taäp G+(s) trong tröôøng hôïp ñoà thò coù ñònh höôùng (taäp G(s) :taäp taát caû caùc ñænh keà cuûa s trong tröôøng hôïp ñoà thò khoâng ñònh höôùng) . § Sau ñoù xeùt v Î G+(s) (hay G(s) ) vaø aùp duïng laïi caùch duyeät gioáng nhö s. Thí du ï1. Ta coù ñoà thò theo hình veõ FIG 1.7. Duyeät theo chieàu roäng nhö sau : s1 s8 s3 s5 s6 s7 s4 s2 s9 Thí duï 2. Ta coù ñoà thò theo hình veõ sau : Duyeät theo chieàu roäng nhö sau : 1 2 3 1 2 4 5 3 4 5 6 7 8 7 8 6 Tröông Myõ Dung 11
  13. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. 1.4 TÍNH LIEÂN THOÂNG CUÛA ÑOÀ THÒ. 1.4.1. Daây chuyeàn - Chu trình. Moät daây chuyeàn trong moät ñoà thò khoâng coù ñònh höôùng laø moät daõy lieân tieáp caùc caïnh, sao cho moãi moät caïnh coù moät ñænh chung vôùi caïnh tieáp theo. Moät chu trình laø moät daây chuyeàn maø coù ít nhaát moät caïnh coù ñænh khôûi ñaàu vaø ñænh keát thuùc truøng nhau. Thí duï. x1 u6 x4 u7 u1 u2 u3 u4 x5 u8 x2 u5 x3 FIG.1.8. laø moät daây chuyeàn, laø moät chu trình. 1.4.2. Ñöôøng – Maïch. Ñöôøng vaø maïch laø khaùi nieäm daây chuyeàn vaø chu trình trong tröôøng hôïp ñoà thò coù ñònh höôùng. THÍ DUÏ. x1 u3 x5 u 4 u 1 u2 u6 x4 u7 x2 u5 x 3 FIG.1.9. laø moät ñöôøng, laø moät maïch. Taäp con caùc ñænh lieân keát cuûa moät ñöôøng ñöôïc goïi laø BAO CHUYEÀN. Tröông Myõ Dung 12
  14. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. Thuaät ngöõ HAØNH TRÌNH (PARCOURS) ñeå chæ nhoùm laïi caùc ñöôøng, caùc daây chuyeàn, caùc maïch vaø caùc chu trình. Moät haønh trình ñöôïc goïi laø : v SÔ CAÁP : Neáu Taát caû caùc ñænh hôïp thaønh ñeàu phaân bieät. v ÑÔN : Neáu taát caû caùc caïnh ñeàu phaân bieät. v HAMILTON : Ñi qua ñuùng moät laàn ñoái vôùi moãi ñænh cuûa ñoà thò. v EULER : Ñi qua ñuùng moät laàn taïi moãi caïnh cuûa ñoà thò. v TIEÀN HAMILTON: Ñi qua it nhaát moät laàn ñoái vôùi moãi ñænh cuûa ñoà thò. v TIEÀN EULER (CHINOIS) : Ñi qua ít nhaát moät laàn taïi moãi caïnh cuûa ñoà thò. 1.4.3. Tính lieân thoâng . Moät ñoà thò khoâng ñònh höôùng ñöôïc goïi laø LIEÂN THOÂNG (CONNEXE) neáu vôùi moïi caëp ñænh ñeàu coù ñöôøng noái. THAØNH PHAÀN LIEÂN THOÂNG laø moät ñoà thò con lieân thoâng toái ñaïi. THÍ DUÏ : x1 x2 x3 x4 x 5 FIG.1.10. Ñoà thò coù hai thaønh phaàn lieân thoâng. ÑÒNH LYÙ 1 Moät ñoà thò laø lieân thoâng neáu vaø chæ neáu noù coù moät thaønh phaàn lieân thoâng. Chöùng minh. Hieãn nhieân. ÑÒNH LYÙ 2. Moät ñoà thò coù ñuùng hai ñænh baäc leû thì phaûi coù moät ñöôøng noái hai ñænh naøy. Tröông Myõ Dung 13
  15. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. Chöùng minh. Chöùng minh baèng phaûn chöùng. 1.4.4. Lieân thoâng maïnh. Moät ñoà thò coù ñònh höôøng ñöôïc goïi laø lieân thoâng maïnh neáu vôùi moïi caëp ñænh phaân b ieät coù moät ñöôøng noái chuùng. Moät thaønh phaàn lieân thoâng maïnh (CFC) laø ñoà thò con toái ñaïi lieân thoâng maïnh. ÑÒNH LYÙ Moät ñoà thò laø lieân thoâng neáu vaø chæ neáu noù coù moät thaønh phaàn lieân thoâng maïnh. Chöùng minh. Hieãn nhieân. 1.5 ÑOÀ THÒ EULER. 1.5.1. Baøi toaùn 7 chieác caàu. Ñaây laø tình huoáng coù thaät ôû Konigsberg (nöôùc Ñöùc), coù hai vuøng bò ngaên caùch bôûi moät doøng soâng vaø coù hai cuø lao ôû giuõa soâng, 7 chieác caàu noái nhöõng vuøng naøy vôùi nhau nhö minh hoïa trong hình veõ treân. Ngöôøi daân trong vuøng thaùch ñoá nhau laø thöû tìm caùch xuaát phaùt töø moät vuøng ñi daïo qua moãi chieác caàu ñuùng moät laàn vaø trôû veà nôi xuaát phaùt. Naêm 1736, nhaø toaùn hoïc Euler ñaõ moâ hình hoùa baøi toaùn naøybaèng moät ñoà thò voâ höôùng vôùi moãi ñænh öùng vôùi moät vuøng, moãi caïnh öùng vôùi moät chieác caàu. Baøi toùan ñöôïc phaùt bieåu laïi cho ñoà thò trong hình veõ beân döôùi, haõy tìm moät ñöôøng ñi trong ñoà thò ñi qua moät laàn trong taát caû caùc caïnh vaø sau ñoù trôû veà ñænh xuaát phaùt. Vieäc giaûi baøi toaùn ñöa ñeán caùc ñònh lyù EULER. A C D B FIG. 1.11. Baøi toaùn 7 chieác caàu. Tröông Myõ Dung 14
  16. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. 1.5.2. Ñònh nghóa. Ñoà thò khoâng ñònh höôùng (coù ñònh höôùng) EULER laø ñoà thò khoâng ñònh höôùng (coù ñònh höôùng) coù chöùa moät maïch (chu trình) EULER. Thí duï. A B F C E D FIG. 1.12. laø maïch EULER. Ñoà thò sau ñaây khoâng coù maïch EULER, nhöng coù caùc ñöôøng EULER. A B F C E FIG. 1.13. laø moät ñöôøng EULER. 1.5.3. Ñònh lyù EULER. § Ñònh lyù 1. Moät ñoà thò khoâng ñònh höôùng, lieân thoâng laø ñoà thò EULER neáu vaø chæ neáu moïi ñænh cuûa G coù baäc chaún. § Ñònh lyù 2. Cho G= (X,U) laø moät ñoà thò coù ñònh höôùng, lieân thoâng maïnh. Khi ñoù G laø ñoà thò Euler neáu vaø chæ neáu ta coù : d+(x) = d- (x) vôùi moïi ñænh x. Tröông Myõ Dung 15
  17. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. § Ñònh lyù 3. Cho G=(X,U) laø moät ñoà thò khoâng ñònh höôùng, lieân thoâng. Khi ñoù G coù ñöôøng Euler neáu vaø chæ neáu G coù ñuùng 2 ñænh coù baäc leû. Thí duï. A B F C E D FIG.1.14. Ñoà thò khoâng ñònh höôùng coù moïi ñænh coù baäc chaún neân laø ñoà thò EULER A B F C E FIG. 1.15. Ñoà thò coù 2 ñænh baäc leû neân khoâng phaûi laø ñoà thò Euler, thoûa ñònh lyù 3 neân ñoà thò seõ coù moät ñöôøng Euler. Tröông Myõ Dung 16
  18. Simpo PDF Merge and Split Unregistered Version - 1. Caùc Khaùi nieäm cô baûn veà Ñoà thò. 1.6 ÑOÀ THÒ HAMILTON. Khaùi nieäm ñöôøng ñi Hamilton ñöôïc xuaát phaùt töø baøi toaùn « Xuaát phaùt töø moät ñænh cuûa khoái thaäp nhò dieän ñeàu, haõy ñi doïc theo caùc caïnh cuûa khoái ñoù sao cho ñi qua ñuùng moät laàn taát caû caùc ñænh cuûa ñoà thò ». Baøi toaùn naøy ñöôïc nhaø Toaùn hoïc Hamilton ñöa vaøo naêm 1859. 1.6.1. Ñònh nghóa. Ñoà thò HAMILTON laø ñoà thò coù chöùa moät chu trình HAMILTON. 1.6.2. Tính chaát. § Ñònh lyù 1. Ñoà thò ñaày ñuû laø ñoà thò Hamilton. Vôùi n leû ³ 3 thì Kn coù (n –1)/2 chu trình Hamilton ñoâi moät khoâng coù caïnh chung. Chöùng minh. Hieãn nhieân. § Ñònh lyù 2. Giaû söû G laø ñoà thò ñôn khoâng coù ñònh höôùng coù n ñænh, vôùi n ³ 3. Neáu vôùi moïi caëp ñænh x, z sao cho z khoâng laø ñænh keà cuûa x , ta coù : d(x) + d(z) ³ n Thì G laø moät ñoà thò Hamilton. Chöùng minh. Baøi taäp. § Ñònh lyù 3. Giaû söû G laø ñoà thò ñôn khoâng coù ñònh höôùng coù n ñænh, vôùi n ³ 3. Neáu vôùi moïi ñænh coù baäc ³ n/2 thì G laø moät ñoà thò Hamilton. Chöùng minh. Suy töø ñònh lyù 2. § Ñònh lyù 4. Gi aû söû G laø ñoà thò ñôn khoâng coù ñònh höôùng coù n ñænh vaø m caïnh. Neáu m ³ (n 2 – 3n + 6) /2 thì G laø moät ñoà thò Hamilton. Chöùng minh. Aùp duïng ñònh lyù 2. Tröông Myõ Dung 17
  19. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. CHÖÔNG 2. CAÁU TRUÙC CAÂY. 2.1 ÑÒNH NGHÓA & THÍ DUÏ. 2.1.1 CAÂY. Caây laø moät ñoà thò khoâng ñònh höôùng, lieân thoâng vaø khoâng coù chu trình. THÍ DUÏ. FIG. 2.1. Caây. ƒ Chieàu daøi cuûa ñöôøng noái hai ñænh laïi vôùi nhau ñöôïc goïi laø khoaûûng caùch giöõa hai ñænh. TÍNH CHAÁT. ƒ Giöõa hai ñænh baát kyø cuûa moät caây seõ coù duy nhaát moät daây chuyeàn noái chuùng laïi vôùi nhau. ƒ Moät caây n ñænh seõ coù n –1 caïnh. Coäng theâm vaøo caây moät caïnh giöõa hai ñænh baát kyø seõ taïo neân moät chu trình duy nhaát. 2.1.2 RÖØNG. Laø moät ñoà thò khoâng ñònh höôùng vaø khoâng coù chu trình (Khoâng lieân thoâng maïnh) Moãi thaønh phaàn lieân thoâng cuûa moät röøng laø moät caây. Tröông Myõ Dung 18
  20. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. 2.1.3 CAÁU TRUÙC CAÂY (CAÂY COÙ GOÁC). Laø moät ñoà thò coù ñònh höôùng sao cho moãi ñænh ñeàu coù moät ñænh tröôùc tröø moät phaàn töû duy nhaát khoâng coù , ñöôïc goïi laø GOÁC. Vôùi moïi ñænh x thì coù duy nhaát moät ñöôøng töø goác ñi ñeán x. Xeùt moät ñænh x cuûa moät caây T coù goác laø r : ƒ Moät ñænh y baát kyø naèm treân ñöôøng höôùng töø goác ñeán x, ñöôc goïi laø caùc ÑÆNH TRÖÔÙC (ANCETRE ) cuûa x, vaø x ñöôïc laø ÑÆNH SAU (DESCENDANT) cuûa y. ƒ Neáu (x,y) laø moät caïnh cuûa T, ta goïi x laø CHA cuûa y vaø y laø CON cuûa x. Hai ñænh cuøng cha ñöôïc goïi laø ANH EM. Moät ñænh khoâng coù con ñöôïc goïi laø LAÙ. Nhöõng ñænh khoâng laø LAÙ ñöôïc goïi laø ÑÆNH TRONG. ƒ Chieàu daøi cuûa ñöôøng töø goác ñeán ñænh ñöôïc goïi laø ñoä saâu cuûa ñænh ñoù. ƒ Möùc (Niveau) cuûa moät ñænh trong T laø khoaûng caùch töø goác ñeán x. ™ Möùc cuûa nuùt goác = 0. ™ Möùc cuûa nuùt khaùc goác = Möùc cuûa caây con nhoû nhaát chöùa noù + 1. ƒ Chieàu cao hay ñoä saâu (Hauteur, profondeur) cuûa caây laø giaù trò lôùn nhaát cuûa möùc cuûa caùc ñænh trong caây. ƒ Neáu moãi ñænh trong caây coù toái ña hai con, thì ta goïi ñoù laø caây nhò phaân. ƒ Baäc cuûa nuùt & baäc cuûa caây (Degreùe). ™ Baäc cuûa nuùt laø soá caây con cuûa nuùt ñoù. ™ Baäc cuûa caây laø baäc lôùn nhaát cuûa caùc nuùt cuûa caây. Neáu caây coù baäc laø n, ta goïi laø caây n-caønh. THÍ DUÏ . Caây 3 – caønh coù goác,vôùi 8 ñænh vaø coù ñoä cao laø 4. 1 d(1) = 3 Möùc 0. 2 d(4)=2 4 3 d(3)=0 Möùc 1. d( 2)=0 d(5)=2 5 9 Möùc 2. d(9)=0 6 7 d(6)=0 d(7) =1 Möùc 3. d(8)=0 8 Möùc 4. FIG.2.2. Caây coù goác. 2.1.4. THÍ DUÏ. Tröông Myõ Dung 19
  21. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. ƒ Ñoâi khi ta coù theå bieåu dieãn moät quan heä bao haøm thöùc cuûa nhieàu taäp hôïp baèng moät caáu truùc caây. Thí duï. Bao haøm cuûa caùc taäp hôïp sau coù theå bieåu dieãn thaønh caáu truùc caây nhö sau : B, C, D ⊂ A. A E, F, G, H ⊂ B. M, N ⊂ D. D C B I ⊂ E. J,K ⊂ F. M N E F G H L ⊂ H. I J K L ƒ Moät Bieán coù caáu truùc coù theå bieåu dieãn döôùi daïng caây. SINH VIEÂN TRÖÔØNG CMNN CAO ÑAÚNG ÑAÏI HOÏC HOÏ TEÂN SINH NGAØY NOI N T N TP Q ƒ Bieåu thöùc soá hoïc. Bieåu thöùc + X = (x – (2* y) +((x+(y+z)) *z) - * coù theå bieåu dieãn thaønh hình caây x * + z nhö sau : 2 y x + y z ƒ Voøng loaïi trong moät cuoäc thi ñaáu boùng baøn. ™ Voøng 1. J ñaáu vôùi T, F ñaáu vôùi M, L ñaáu vôùi P. J ™ Voøng 2. J ñaáu vôùi M, L ñaáu vôùi Ph J Ph ™ Voøng 3. J ñaáu Ph. J M L Ph ™ Cuoái cuøng J thaéng. J T F M P L ƒ Caâu trong ngoân ngöõ töï nhieân (hay trong ngoân ngöõ laäp trình) Ferme Ñoái vôùi caâu « Le Pilote ferme la porte » Pilote porte Coù theå bieåu dieãn döôùi daïng Le la ƒ Töï ñieãn coù theå toå chöùc theo hình caây. . Chaúng haïn töï ñieãn goàm caùc töø ART, ART COU ARTICLE, ASTISTE, COU, COUR, COUTEAU, COUVE, COUVENT, * I * R TEAU VE COUVER coù theå bieåu dieãn theo hình veõ sau. Kyù töï «*» chæ chaám döùt CLE STE * * * NT R moät töø. Chuù yù, thöù töï ALPHABET theo thöù töï töø phaûi sang traùi. * * * * Tröông Myõ Dung 20
  22. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. 2.2 TÍNH CHAÁT CÔ BAÛN. 2.2.1 ÑÒNH LYÙ 1. Cho G laø moät caây baäc n > 1. Caùc tính chaát sau ñaây töông ñöông vôùi nhau : 1. G lieân thoâng vaø khoâng coù chu trình. 2. G lieân thoâng vaø coù n –1 caïnh. 3. G khoâng coù chu trình vaø coù n – 1 caïnh. 4. G khoâng coù chu trình vaø neáu theâm vaøo moät caïnh giöõa hai ñænh khoâng keà seõ taïo moät chu trình duy nhaát giöõa chuùng. 5. G lieân thoâng toái thieåu(coù nghóa laø neáu xoùa ñi moät caïnh baát kyø thì G khoâng coøn lieân thoâng nöõa) 6. Moïi caëp ñænh coù duy nhaát daây chuyeàn noái chuùng. CHÖÙNG MINH. Baøi taäp. 2.2.2 ÑÒNH LYÙù 2. Moät ñoà thò G = (X,U) laø moät ñoà thò coù chöùa moät ñoà thò rieâng phaàn neáu vaø chæ neáu G lieân thoâng. CHÖÙNG MINH. Baøi taäp. 2.2.3 ÑÒNH LYÙ 3. Moïi Caáu truùc caây laø moät caây. CHÖÙNG MINH. Baøi taäp. Tröông Myõ Dung 21
  23. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. 2.3 CAÂY NHÒ PHAÂN. 2.3.1. ÑÒNH NGHÓA (THEO ÑEÄ QUI). Moät caây nhò phaân B hoaêc laø ∅ hoaëc coù daïng : B = trong ñoù : O : goác, B1 : caây con traùi vaø B2 : caây con phaûi. 2.3.2. BIEÅU DIEÃN CAÂY NHÒ PHAÂN. THÍ DUÏ. a b c d e f g ™ SÖÛ DUÏNG BAÛNG. Coù theå ñònh nghóa kieåu döõ lieäu nhö sau : Type Arbtab = Array [1 n] of Record v : t ; G : integer ; D : integer ; End ; Vôùi thí duï ôû treân, ta coù : Traùi Phaûi 1 2 d 0 8 3 a 5 6 4 e 0 9 5 b 2 0 6 c 4 0 7 8 f 0 0 9 g 0 0 10 ™ SÖÛ DUÏNG CON TROÛ. Coù theå ñònh nghóa kieåu döõ lieäu nhö sau : Type Pt = ^nut ; nut = Record G : Pt ; Val : t ; D : Pt ; End ; Tröông Myõ Dung 22
  24. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. 2.3.3. DUYEÄT MOÄT CAÂY NHÒ PHAÂN. Coù 3 caùch duyeät moät caây nhò phaân (phuï thuoäc theo goác). 1. THÖÙ TÖÏ TRÖÔÙC (PREFIXEÙ). ƒ Xöû lyù goác. ƒ Duyeät caây con traùi. ƒ Duyeät caây con phaûi. 2. THÖÙ TÖÏ GIÖÕA (INFIXEÙ). ƒ Duyeät caây con traùi. ƒ Xöû lyù goác. ƒ Duyeät caây con phaûi. 3. THÖÙ TÖÏ SAU (POSTFIXEÙ). ƒ Duyeät caây con traùi. ƒ Duyeät caây con phaûi. ƒ Xöû lyù goác. THÍ DUÏ. Theo caây ôû thí duï treân , ta coù : ƒ Tröôùc : a b d f c e g. ƒ Giöûa : d f b a e g c. ƒ Sau : f d b g e c a. 2.4 CAÂY PHUÛ. 2.4.1. ÑÒNH NGHÓA. Cho moät ñoà thò voâ höôùng G. Moät caây H goïi laø caây phuû cuûa G neáu H laø caây rieâng phaàn cuûa G chöùa moïi ñænh cuûa G. 2.4.2. ÑÒNH LYÙ. Ñoà thò G coù caây phuû neáu vaø chæ neáu G lieân thoâng. Tröông Myõ Dung 23
  25. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. 2.4.3. GIAÛI THUAÄT TÌM CAÂY PHUÛ. Xeùt moät ñoà thò G. GIAÛI THUAÄT. ƒ Böôùc 1. Choïn tuøy yù moät ñænh cuûa G ñaët vaøo H. ƒ Böôùc 2. Neáu moïi ñænh cuûa G ñeàu naèm trong H thì döøng. ƒ Bööùc 3. Neáu khoâng, tìm moät ñænh cuûa G khoâng naèm trong H maø noù coù theå noái noù vôùi moät ñænh cuûa H baèng moät caïnh. Theâm ñænh vaø caïnh naøy vaøo H. Quay veà böôùc 2. THÍ DUÏ . Cho ñoà thò G theo hình veõ sau : x3 x2 x1 x6 x4 x5 FIG. 2.3. ™ Khôûi töø x1. T= ∅. ™ Böôùc 1. Choïn x2, T = {(x1,x2)}. ™ Böôùc 2. Choïn x3, T = {(x1,x2), (x2,x3)}. ™ Böôùc 3. Choïn x4, T = {(x1,x2), (x2,x3), (x3,x4)}. ™ Böôùc 4. Choïn x5, T = {(x1,x2), (x2,x3), (x3,x4), (x4,x5)}. ™ Böôùc 5. Choïn x6, T = {(x1,x2), (x2,x3), (x3,x4), (x4,x5), (x5,x6)}. Keát quaû : T laø caây phuû cuûa G . 2.4.4. ÑÒNH LYÙ. Coi moät caây phuû H cuûa G. Theâm vaøo H moät caïnh cuûa G (khoâng thuoäc H), ta ñöôïc moät chu trình trong H. Huõy moät caïnh baát kyø treân chu trình naøy ra khoûi H, ta nhaän ñöôïc moät caây phuû môùi cuûa G. Tröông Myõ Dung 24
  26. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. 2.4.5. GIAÛI THUAÄT KIEÅM TRA TÍNH LIEÂN THOÂNG. Xeùt moät ñoà thò khoâng ñònh höôùng G. Aùp duïng giaûi thuaät treân vaøo G. Khi giaûi thuaät döøng. ƒ Neáu H chöùa moïi ñænh cuûa G thì G lieân thoâng vaø H laø moät caây phuû cuûa G. ƒ Neáu H khoâng chöùa moïi ñænh cuûa G thì G khoâng lieân thoâng vaø H laø moät caây phuû cuûa moät thaønh phaàn lieân thoâng cuûa G. THÍ DUÏ 1. Tröôøng hôïp ñoà thò G ôû hình FIG. 2.3. thì ta coù G lieân thoâng. THÍ DUÏ 2. Cho ñoà thò G theo hình veõ sau : x3 x2 x1 x6 x4 x5 ™ Khôûi töø x1. T= ∅. ™ Böôùc 1. Choïn x3, T = {(x1,x3)}. ™ Böôùc 2. Choïn x4, T = {(x1,x3), (x3,x4)}. Thuaät toaùn döøng. T laø caây phuû cuûa moät thaønh phaàn lieân thoâng cuûa G maø thoâi. 2.4.6. GIAÛI THUAÄT TÌM THAØNH PHAÀN LIEÂN THOÂNG THEO CAÙCH DUYEÄ T THEO CHIEÀU SAÂU. Do thuû tuïc duyeät theo chieàu saâu PROF(s) cho pheùp thaêm taát caû caùc ñænh thuoäc cuøng moät thaønh phaàn lieân thoâng vôùi ñænh s, neân soá thaønh phaàn lieân thoâng cuûa ñoà thò chính baèng soá laàn goïi ñeán thuû tuïc naøy. Vaán ñeà coøn laïi laø caùch ghi nhaän caùc ñænh trong töøng thaønh phaàn lieân thoâng baèng caùch caûi tieán thuû tuïc chieàu theo chieàu saâu PROF(s) nhö sau : THUÛ TUÏC DFS(int k) ; //Duyeät theo chieàu saâu baét ñaàu töø ñænh k { Mark[k] = socomp; For (int i = 1;i ≤ n ;i++) if (a[i][k]==1 && (Mark[i]= =0) DFS(i); } Tröông Myõ Dung 25
  27. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. THUÛ TUÏC CONNEXE ; { // Khôûi taïo soá lieäu ban ñaàu cho Mark (caùc ñænh ñaõ duyeät roài) vaø socomp (soá thaønh phaàn lieân thoâng For (int j= 1 ;j≤ n ;j++) { Mark[j] =0 ; Socomp =0 ;} //Goïi thuû tuïc ñeå xaùc ñònh caùc thaønh phaàn lieân thoâng For (int i= 1 ;i≤n ;i++) If Mark [i] = =0 { Socomp = Socomp +1 ; DFS(i) ; } //In keát quaû } THÍ DUÏ. s8 s1 s2 s3 s7 s6 s4 s5 ™ Khôûi töø s1 . Goïi DFS(1) , ta coù Taäp ñaùnh daáu {s1, s2, s6, s7, s8}. ™ i= 3 Goïi DFS(3) , ta coù Taäp ñaùnh daáu {s3, s4, s5}. ™ Keát quaû. Coù 2 thaønh phaàn lieân thoâng. C1 = {s1, s2, s6, s7, s8}. C2 = {s3, s4, s5}. Tröông Myõ Dung 26
  28. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. 2.5 CAÂY PHUÛ TOÁI THIEÅU. BAØI TOAÙN 1. Cho moät ñoà thò lieân thoâng G = (X,U), vaø,vôùi moïi caïnh u lieân keát vôùi moät con soâ l(u) maø ta goïi laø chieàu daøi (trong löôïng). Vaán ñeà ñaët ra laø tìm moät caây rieâng phaàn H=(X,V) cuûa G sao cho toång chieàu daøi ∑l(u) laø nhoû nhaát. u THÍ DUÏ. Baøi toaùn naøy thöôøng gaëp trong vieãn thoâng vaø trong nhieàu tröôøng hôïp khaùc. Chaúng haïn, baøi toaùn ñaët ra cho chuùng ta laø Tìm ñöôøng daây caùp ngaén nhaát ñeå noái n thaønh phoá laïi vôùi nhau ? Caùc thaønh phoá ñöôïc bieåu dieãn laø ñænh cuûa moät ñoà thò vaø l( (x,y) laø khoaûng caùch giöõa thaønh phoá x vaø y. Maïng daây caùp noái baét buoäc phaûi lieân thoâng. ÔÛ ñaây, vaán ñeà laø tìm caây rieâng phaàn coù toång chieàu daøi nhoû nhaát noái taát caû caùc ñænh ? BOÅ ÑEÀ. Neáu G = (X,U) laø moät ñoà thò ñaày ñuû vaø neáu taát caû caùc chieàu daøi l(u) töông öùng cuûa caùc caïnh ñeàu phaân bieät thì khi aáy, Baøi toaùn 1 coù moät lôøi giaûi duy nhaát (X, V). Taäp V={v1,v2, ,vn-1} nhaän ñöôïc theo caùch sau ñaây : ƒ Choïn v1 laø caïnh coù chieàu daøi nhoû nhaát. ƒ v2 laø caïnh coù chieàn daøi nhoû nhaát sao cho v2 ≠ v1 vaø V2 = {v1,v2} khoâng chöùa chu trình. ƒ v3 laø caïnh nhoû nhaát sao cho v3 ≠ v2 ≠ v1 vaø V3 = {v1,v2,v3} khoâng chöùa chu trình. ƒ Cöù theá, tieáp tuïc. Tröông Myõ Dung 27
  29. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. 2.5.1. THUAÄT TOAÙN PRIM . Kyù hieäu : ♦ A = Ma traän keà bieåu dieãn ñoà thò, coù troïng löôïng, ñöôïc ñònh nghóa nhö sau : A= [ ai,j] = l(i,j) = chieàu daøi cuûa caïnh cung öùng u=(i,j) ∈ U ∝ u=(i,j) ∉ U 0 , i=j ♦ M = Taäp ñænh chöa ñaùnh daáu (coù soá phaàn töû laø n0). ♦ Pr(p) = Ñænh tröôùc ñænh p. ♦ d = Taäp chieàu daøi cuûa Caây phuû coù chòeâ&u daøi ngaén nhaát. ♦ Mark = Taäp ñænh ñaõ ñaùnh daáu (ñaõ xeùt roài), ñònh nghóa nhö sau : Mark[i]= 1, neáu ñænh ñaõ xeùt roài, 0, ngöôïc laïi. NGUYEÂN LYÙ THUAÄT TOAÙN. 1. Khôûi taïo : Xuaát phaùt töø ñænh 1. T = ∅, M = {2, n} Pr = [1,1, 1] d = a[1,j], j=1 n (Doøng ñaàu cuûa ma traän keà A) Mark = [1,0 0] 2. ÔÛ moãi böôùc laëp, choïn ñænh ñaùnh daáu laø ñænh coù ñoä daøi ngaén nhaát. ™ k = Argminx ∈ M d[x]. ™ Mark[k]=1. ™ Caäp nhaät laïi d[i], Pr[i] vôùi i∈ M \{k} theo coâng thöùc: • d[i] = a[k,i] neáu d[i] > a[k,i]. • Pr[i] = k. ™ Thay M := M\{k}. Neáu M = ∅. Döøng. Neáu khoâng , quay laïi 2. Ñoä phöùc taïp : O(m log n). Tröông Myõ Dung 28
  30. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. THÍ DUÏ. Ta coù Ma traän keà A, bieåu dieãn Ñoà thò ôû FIG. 2.3., nhö sau : 1 2 3 4 5 6 1 0 2 3 11 5 8 2 2 0 1 10 ∞ 9 A = 3 3 1 0 6 12 ∞ 4 11 10 6 0 4 ∞ 5 5 ∞ 12 4 0 7 6 8 9 ∞ ∞ 7 0 Caùc böôùc cuûa thuaät toaùn thöïc hieän nhö sau : ƒ Gaùn ban ñaàu cho : M, d, Pr : M = { 2, 3, 4, 5, 6} d = [0, 2, 3, 11, 5, 8] Pr = [1, 1, 1, 1, 1, 1] ƒ Böôùc 1. Choïn ñænh s2 . Caäp nhaät M, d, Pr : M = { , 3, 4, 5, 6} d = [0, 2, 1, 10, 5, 8] Pr = [1, 1, 2 2, 1, 1] ƒ Böôùc 2. Choïn ñænh s3 . Caäp nhaät M, d, Pr : M = { , , 4, 5, 6} d = [0, 2, 1, 6, 5, 8] Pr = [1, 1, 2, 3, 1, 1] ƒ Böôùc 3. Choïn ñænh s5 . Caäp nhaät M, d, Pr : M = { , , 4, , 6} d = [0, 2, 1, 4, 5, 7] Pr = [1, 1, 2, 5, 1, 5] ƒ Böôùc 4. Choïn ñænh s4 . Caäp nhaät M, d, Pr : M = { , , , , 6} d = [0, 2, 1, 4, 5, 7] Pr = [1, 1, 2, 5, 1, 5] Ta coù Keát quaû nhö sau : ƒ Caây Phuû coù ñoä daøi ngaén nhaát theo caùc Böôùc laëp : T= (x1, x2), (x2,x3), ), (x1,x5) , ), (x5,x4), (x5,x6)} vaø coù ñoä daøi l(T) = 19 ƒ Caây Phuû coù ñoä daøi ngaén nhaát ñoïc keát quaû theo d vaø Pr : T= (x1, x2), (x2,x3), ), (x5,x4), (x1,x5) , ), (x5,x6)} vaø coù ñoä daøi l(T) = 19 Tröông Myõ Dung 29
  31. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. 10 x3 1 x2 x2 3 x1 2 9 2 6 8 x6 x1 11 x1 12 5 7 Caây khôûi ñaàu x4 4 x5 Caïnh theâm vaøo thöù 1 Caây ban ñaàu x3 1 x2 x3 1 x2 2 2 x1 x1 5 x5 Caïnh theâm vaøo thöù 2 Caïnh theâm vaøo thöù 3 1 x3 1 x2 x3 x2 2 2 x6 x1 x1 5 5 7 4 4 x4 x5 x4 x5 Caïnh theâm vaøo thöù 4 Caïnh theâm vaøo thöù 5. FIG. 2.3. Tìm Caây phuû coù ñoä daøi ngaén nhaát theo PRIM (s=1). Tröông Myõ Dung 30
  32. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. 2.5.2. THUAÄT TOAÙN KRUSKAL (1956). Cho ñoà thò G = (X, U) laø ñoà thò lieân thoâng khoâng ñònh höôùng, coù troïng löôïng. Giaû Söû ñaõ saép xeáp caùc caïnh cuûa ñoà thò theo thöù töï khoâng giaûm theo chieàu daøi. YÙ töôûng cuûa thuaät toaùn KRUSKAL ôû moãi böôùc laëp, ta boå sung vaøo taäp caïnh cuûa caây phuû H =(X, T) sao cho khoâng taïo thaønh chu trình. Thuaät toaùn döøng khi taát caû caùc ñænh cuûa ñoà thò ñeàu ñöôïc noái, nghóa laø soá caïnh cuûa H baèng n – 1. Ñaây laø thuaät toaùn « haùu aên », theo nghóa laø ôû moãi böôùc, ta choïn moät lôøi giaõi toái öu ñòa phöông vaø mong muoán lôøi giaûi toái öu ñòa phöông naøy laø toái öu toaøn cuïc. Caây nhaän ñöôïc laø duy nhaát neáu taát caû caùc caïnh coù chieàu daøi khaùc nhau. Ñoä phöùc taïp : O(m log m). THUÛ TUÏC KRUSKAL ; Begin T := {∅} ; While Card(T) < (n-1) and (U ≠ ∅) Do Begin Chon u laø caïnh coù ñoä daøi nhoû nhaát trong U ; U := U\{u} ; If (T ∪ {u}) khoâng chöùa chu trình) then T := T∪ {u} ; End ; If (Card(T) < n-1 ) Then Ñoà thò khoâng lieân thoâng. End ; THÍ DUÏ 1. Xem hình FIG. 2.3. Ta coù : U={(x2, x3),(x1,x2),(x1,x3),(x4,x5),(x1,x5),(x3,x4), (x5,x6),(x1,x6),(x2,x6),(x2,x4),(x1,x4),(x3,x5)} L(U) = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} Caùc böôùc cuûa thuaät toaùn thöïc hieän nhö sau : ƒ Böôùc 1. T= {(x2, x3)}, L(T) = { 1} ƒ Böôùc 2. T= {(x2, x3),(x1,x2)}, L(T) = { 1, 2 } ƒ Böôùc 3. T= {(x2, x3),(x1,x2), ),(x4,x5)}, L(T) = { 1, 2 , 4 } ƒ Böôùc 4. T= {(x2, x3),(x1,x2), ),(x4,x5) ,(x1,x5)}, L(T) = { 1, 2 , 4, 5 } ƒ Böôùc 5. T= {(x2, x3), (x1,x2), ),(x4,x5) ,(x1,x5) , (x5,x6)} Keát thuùc vì Card(T) = 5 = 6 (ñænh) –1. Toång chieàu daøi nhoû nhaát = 19. Chuù yù. Trong thí duï naøy, ta tìm laïi caây phuû gioáng nhö trong thuaät toaùn PRIM. Nhöng, trong tröôøng hôïp toång quaùt, ta coù theå tìm thaáy moät caây phuû khaùc nhöng coù cuøng toång troïng löôïng. Tröông Myõ Dung 31
  33. Simpo PDF Merge and Split Unregistered Version - 2. Caáu truùc Caây. 10 x3 1 x2 x2 , x3 9 x1 2 9 2 x1 3 8 x6 1 6 8 x6 6 11 12 5 11 12 5 7 7 x4 4 x5 x4 4 x5 x1, x2, x3 2 6 5 8 x6 4 7 x4 4 x5 x1, x2, x3 x1,x2, x3, x4, x5 5 8 x6 5 7 x4, x5 x6 FIG. 2.4. Tìm caây phuû coù chieàu daøi ngaén nhaát theo thuaät toaùn KRUSKAL. Tröông Myõ Dung 32
  34. Simpo PDF Merge and Split Unregistered Version - 3. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. CHÖÔNG 3. BAØI TOAÙN TÌM ÑÖÔØNG ÑI NGAÉN NHAÁT. Nhöõng baøi toaùn tìm ñöôøng ñi trong caùc ñoà thò (ñaëc bieät laø tìm ñöôøng ñi ngaén nhaát) ñöôïc keå laø moät trong nhöõng baøi toaùn kinh ñieãn, coå trong lyù thuyeát ñoà thò vaø coù nhieàu öùng duïng nhaát. 3.1. ÑÒNH NGHÓA. Cho G = (X, U) laø moät ñoà thò coù ñònh giaù; töông öùng vôùi moãi cung u=(i, j), coù moät chieàu daøi (hay troïng löôïng) l(u) hay lij . Baøi toaùn tìm ñöôøng ñi ngaén nhaát giöõa i vaø j laø tìm moät ñöôøng µ(i, j) töø i ñeán j sao cho : l(µ) = ∑ l(u) u laø ngaén nhaát. Dieãn giaûi l(µ) : Chi chí vaän chuyeãn, Chi phí xaây döïng, thôøi gian caàn thieát ñeå ñi khaép, CHUÙ YÙ. Baøi toaùn tìm ñöôøng ñi ngaén nhaát töông töï vôùi baøi toaùn tìm ñöôøng ñi daøi nhaát. Nhöõng thuaät toaùn khaùc nhau theo nhöõng tính chaát sau ñaây : ♦ l(u) ≥ 0, ∀ u ∈ U. ♦ l(u) baèng nhau ⇔ l(u) = 1, ∀ u ∈ U.(Baøi toaùn ñöôøng ñi ngaén nhaát theo soá cung) ♦ G khoâng coù chu trình. ♦ G vaø l(u) baát kyø. Tröông Myõ Dung 33
  35. Simpo PDF Merge and Split Unregistered Version - 3. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. Vaø loaïi baøi toaùn sau ñöôïc xeùt : ♦ Tìm ñöôøng ñi ngaén nhaát töø moät ñænh ñeán caùc ñænh coøn laïi, ♦ Tìm ñöôøng ñi ngaén nhaát giöõa caùc caëp ñænh. 3.2. NGUYEÂN LYÙ TOÁI ÖU. Nguyeân lyù toái öu phaùt bieåu theo söï kieän laø taäp ñöôøng ñi con cuûa taäp ñöôøng ñi ngaén nhaát laø nhöõng ñöôøng ngaén nhaát. BOÅ ÑEÀ. Xeùt ñoà thò G = (X,U) vaø moät haøm troïng löôïng l : X x X → R, Cho C = « x1, x2, ,xk » laø ñöôøng ñi ngaén nhaát töø x1 ñeán xk vaø vôùi moïi (i, j) sao cho 1≤ i≤ j≤ k, Cho Cij = « xi, xi+1, ,xj » laø ñöôøng con cuûa C töø xi ñeán xj. Khi aáy Cij laø moät ñöôøng ngaén nhaát töø xi ñeán xj. Nguyeân lyù cuûa nhöõng thuaät toaùn tìm ñöôøng ñi ngaén nhaát : ♦ Moät khoaûng caùch d(i) töông öùng vôùi ñænh xi. ♦ ÔÛ cuoái thuaät toaùn, khoaûng caùch naøy bieåu dieãn chieàu daøi ngaén nhaát töø goác ñeán ñænh ñang xeùt. 3.3. CAÙC DAÏNG CUÛA BAØI TOAÙN: TÖØ MOÄT ÑÆNH ÑEÁN CAÙC ÑÆNH COØN LAÏI. Baøi toaùn naøy coøn ñöôïc goïi laø baøi toaùn tìm ñöôøng ñi ngaén nhaát töø goác duy nhaát. Nhieàu baøi toaùn khaùc cuõng coù theå duøng thuaät toaùn naøy ñeå giaûi : ♦ Ñöôøng ñi ngaén nhaát ñeán ñích duy nhaát. ♦ Ñöôøng ñi ngaén nhaát töø caëp ñænh cho tröôùc. ♦ Ñöôøng ñi ngaén nhaát cho moïi caëp ñænh (thuaät toaùn goác duy nhaát töø moãi ñænh). Tröông Myõ Dung 34
  36. Simpo PDF Merge and Split Unregistered Version - 3. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. 3.3.1. THUAÄT TOAÙN DIJKSTRA-MOORE (1959). Giaû thieát laø caùc caïnh (cung) (l(u) ≥ 0). Giaû söû G coù n ñænh ñaùnh soá thöù töï töø 1 tôùi n. Baøi toaùn ñaët ra laø tìm ñöôøng ñi ngaén nhaát töø ñænh 1 ñeán caùc ñænh coøn laïi trong ñoà thò. Kyù hieäu : ♦ n0 = soá phaàn töû chöa choïn; ♦ A = Ma traän keà bieåu dieãn ñoà thò, coù troïng löôïng, ñöôïc ñònh nghóa nhö sau : A = [ ai,j] = l(i,j) = chieàu daøi cuûa caïnh cung öùng u=(i,j) ∈ U ∝ u=(i,j) ∉ U 0 , i=j ♦ Pr(p) = ñænh tröôùc ñænh p theo ñöôøng ñi ngaén nhaát töø goác ñeán ñænh p. ♦ d = khoaûng caùch ngaén nhaát töø goác ñeán caùc ñænh coøn laïi trong ñoà thò. Qui öôùc ∞ cho caùc ñænh khoâng coù ñöôøng ñi töø goác ñeán noù. ♦ Mark = Taäp ñænh ñaõ ñaùnh daáu (ñaõ xeùt roài), ñònh nghóa nhö sau : Mark[i] = 1, neáu ñænh ñaõ xeùt roài, 0, ngöôïc laïi. NGUYEÂN LYÙ THUAÄT TOAÙN. 1. Khôûi taïo : Xuaát phaùt töø ñænh 1 ; n0 = n – 1 : Pr = [1,1, 1] d = a[1,j], j=1 n (Doøng ñaàu cuûa ma traän keà A) Mark = [1,0 0] 2. ÔÛ moãi böôùc laëp, choïn ñænh ñaùnh daáu laø ñænh coù ñoä daøi ngaén nhaát trong nhöõng ñænh chöa ñaùnh daáu, nghóa laø choïn ñænh k sao cho : d[k] = Min {d[i] : Mark[i]= 0 } ; Mark[k]=1. Caäp nhaät laïi d[j], Pr[j] vôùi nhöõng ñænh j chöa ñaùnh daáu (Mark[j]=0) theo coâng thöùc: • d[j] = d[k] + a[k,j] neáu d[j] > d[k] +a[k,j]. • Pr[j] = k. Neáu taát caû moïi ñænh ñaõ ñöôïc choïn, nghóa laø n0 = 0. Döøng. Neáu khoâng , quay laïi 2. THUÛ TUÏC DIJKSTRA – MOORE ; //Giaû söû ñaõ nhaäp ma traän chieàu daøi l theo daïng ma traän keà A //Gaùn ban ñaàu cho d, Pr, Mark, n0 . For (int j= 1; j≤ n ; j++) { d[j] = a(1,j) ; pr[j]=1 ; Mark[j] = 0;} Mark[1] =1 ; n0 = n-1 ; WHILE (n0 > 0) {d[k] = Min {d[j] : Mark[j]= 0 } ; // Caäp nhaät laïi n0 , d vaø Pr, Mark Mark[k] =1 ; n0 = n0 - 1 ; For (int j= 1; j≤ n ; j++) if (Mark [j] = 0) && (d[k]+ a[k,j] < d[j]) { d[j] = d[k] +a[k,j] ; pr[j]=k} } Ñoä phöùc taïp : O(n²) hay O(mlogn) Tröông Myõ Dung 35
  37. Simpo PDF Merge and Split Unregistered Version - 3. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. THÍ DUÏ. Ma traän keà A : 1 2 3 4 5 6 1 1 0 10 3 ∝ 6 ∝ 0 2 0 ∝ ∝ ∝ ∝ ∝ 1 10 2 A = 3 ∝ 4 0 ∝ 2 ∝ 3 4 ∝ ∝ 1 0 3 ∝ 2 6 4 5 ∝ 0 ∝ ∝ 0 1 6 0 3 6 2 1 ∝ ∝ ∝ 0 1 2 1 5 3 4 FIG.3.1. Ñoà thò coù ñònh höôùng, coù troïng löôïng. Gaùn Ban ñaàu. Cho Mark, d, Pr : Mark = [1, 0, 0, 0, 0, 0] d = [0, 10, 3, ∝, 6, ∝] Pr = [1, 1, 1, 1, 1, 1] Böôùc 1. Choïn ñænh s3. Caäp nhaät Mark, d, Pr : Mark = [1, 0, 1, 0, 0, 0] d = [0, 7, 3, ∝, 5, ∝] Pr = [1, 3, 1, 1, 3, 1] Böôùc 2 . Ñænh hieän thôøi laø s3. Choïn ñænh s5. Caäp nhaät Mark, d, Pr : Mark = [1, 0, 1, 0, 1, 0] d = [0, 5, 3, ∝, 5, 6] Pr = [1, 5, 1, 1, 3, 5] Böôùc 3 . Ñænh hieän thôøi laø s5 . Choïn ñænh s2. Caäp nhaät Mark, d, Pr : Mark = [1, 1, 1, 0, 1, 0] d = [0, 5, 3, ∝, 5, 6] Pr = [1, 5, 1, 1, 3, 5] Böôùc 4 . Ñænh hieän thôøi laø s2 . Choïn ñænh s6. Caäp nhaät Mark, d, Pr : Mark = [1, 1, 1, 0, 1, 1] d = [0, 5, 3, ∝, 5, 6] Pr = [1, 5, 1, 1, 3, 5] Thuaät toaùn keát thuùc vì ñænh s4, ta coù d[s4] = Min {d[j] : Mark[j]= 0}= d[s4] = ∝. Töø thuaät toaùn , ta coù keát quaû sau : d = [0, 5, 3, ∝, 5, 6] Pr = [1, 5, 1, 1, 3, 5] Ñöôøng ñi ngaén nhaát töø s1 ñeán s2 : s1 → s3 → s5 → s2 vaø ñoä daøi laø 5 Ñöôøng ñi ngaén nhaát töø s1 ñeán s3 : s1 → s3 vaø ñoä daøi laø 3 Ñöôøng ñi ngaén nhaát töø s1 ñeán s5 : s1 → s3 → s5 vaø ñoä daøi laø 5 Ñöôøng ñi ngaén nhaát töø s1 ñeán s6 : s1 → s5 → s6 vaø ñoä daøi laø 6 Khoâng coù ñöôøng ñi ngaén nhaát töø ñænh s1 ñeán s4 (d[s4] = ∝) , vì khoâng coù ñöôøng noái töø s1 ñeán s4. Tröông Myõ Dung 36
  38. Simpo PDF Merge and Split Unregistered Version - 3. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. GHI CHUÙ. Giaû thieát « Haøm troïng löôïng khoâng aâm » laø baét buoäc. Chaúng haïn, söû duïng thuaät toaùn Dijktra-Moore cho ñoà thò ôû hình FIG.3.2, daãn ñeán keát quaû sai neáu ta choïn goác laø ñænh s1. Thaät vaäy, ñaàu tieân, ta choïn ñænh s2, (s1 → s2) trong khi ñoù, ñöôøng ñi ngaén nhaát laø ñöôøng ñi töø ñænh s1 ñeán s2 qua s3 . 3 3 - 5 1 2 2 FIG. 3.2. Ñoà thò coù ñònh höôùng, coù troïng löôïng baát kyø. Tröông Myõ Dung 37
  39. Simpo PDF Merge and Split Unregistered Version - 3. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. 3.3.2. THUAÄT TOAÙN BELLMAN-FORD (1958-1962) Söï hieän dieän cuûa daáu baát kyø cuûa troïng löôïng (hay chieàu daøi ) cho pheùp, chaúng haïn, coù theå caûi tieán chi phí hay lôïi nhuaän. Thuaät toaùn DIJKSTRA-MOORE khoâng cho pheùp xeùt tôùi nhöõng caïnh (cung) coù troïng löôïng khoâng aâm, vì trong tröôøng hôïp moät caïnh ñöôïc ñaùnh daáu, thì ta khoâng theå thay ñoåi gì cho nhöõng böôùc laëp tieáp theo. Thuaät toaùn DIJKSTRA-MOORE coøn ñöôïc goïi laø gaùn nhaõn coá ñònh . Ñeå giaûi quyeát cho tröôøng hôïp ñoà thò coù troïng löôïng baát kyø, ta moät xeùt thuaät toaùn cho pheùp moät ñaùnh daáu chæ ñöôïc xaùc ñònh hoaøn toaøn khi thuaät toaùn keát thuùc. Moät kieåu thuaät toaùn nhö vaäy ñöôïc goïi laø ñieàu chænh nhaõn. Thuaät toaùn BELLMAN-FORD chæ coù giaù trò cho caùc ñoà thò khoâng coù chu trình, coù troïng löôïng baát kyø. Kyù hieäu : ♦ Taäp ñænh ñöôïc ñaùnh soá thöù töï töø 1 n. ♦ Pr(p) = ñænh tröôùc ñænh p theo ñöôøng ñi ngaén nhaát töø goác ñeán ñænh p. ♦ d = khoaûng caùch ngaén nhaát töø goác ñeán caùc ñænh coøn laïi trong ñoà thò. ♦ Mark = Taäp ñænh ñaõ ñaùnh daáu (ñaõ xeùt roài), ñònh nghóa nhö sau : Mark[i] = 1, neáu ñænh ñaõ xeùt roài, 0, ngöôïc laïi. Khoaûng caùch ngaén nhaát töø goác ñeán moät ñænh v chæ ñöôïc tính khi taát caû caùc phaàn töû tröôùc cuûa v (Γ -(v)) ñaõ ñöôïc ñaùnh daáu roài. Moät ñænh baát kyø, khi chöa ñaùnh daáu, thì khoaûng caùch töø goác ñeán ñænh ñoù chöa bieát (chöa tính). NGUYEÂN LYÙ THUAÄT TOAÙN 1. Gaùn caùc giaù trò ban ñaàu. Choïn ñænh s1 laøm goác. Mark = [1,0 0] ; d[1] = 0 ; Pr[1] = 1. 2. ÔÛ moãi böôùc laëp : Choïn ñænh k chöa ñaùnh daáu sao cho taát caû ñænh tröôùc cuûa k ñaõ ñaùnh daáu roài , nghóa laø : Mark[k] = 0 vaø ∀ j ∈ Γ -(k) : Mark[j]= 0 Caäp nhaät Mark : Mark[k] =1 ; Tính d[k] = min { d[i] + a[i, k]: i ∈ Γ - (k)}, vaø Pr[k] laø chæ soá ñaït min. ÑOÄ PHÖÙC TAÏP : O(nm). O(n3) Cho caùc ñoà thò daày, i.e., nhöõng ñoà thò maø m ≈ n². Tröông Myõ Dung 38
  40. Simpo PDF Merge and Split Unregistered Version - 3. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. THÍ DUÏ. 3 Gaùn ban ñaàu : Mark, d, Pr : 2 -2 4 Mark = [1, 0, 0, 0, 0, 0}, d[1] = 0 ; 1 5 -5 Pr [1] = 1 1 1 6 Γ - (2) ={1,3};Γ- (3)={1};Γ- (4)={2,3,6} -2 Γ - (5) ={3} ; Γ- (6) ={2,5} -1 3 4 5 FIG.3.1. Ñoà thò coù ñònh höôùng, coù troïng löôïng baát kyø, khoâng coù chu trình, goác ñænh 1. Böôùc 1. Choïn ñænh 3 vì Γ- (3)={1} . Caäp nhaät Mark[3], Tính d[3] vaø Pr[3] : Mark[3] = 1 ; d[3] = -2 ; Pr[3] = 1; Böôùc 2. ÔÛ böôùc laëp naøy, ta coù theå choïn ñænh 5 (hay ñænh 2). Caäp nhaät Mark[5], Tính d[5] vaø Pr[5] : Mark[5] = 1 ; d[5] = 2 ; Pr[5] = 3; Böôùc 3. Choïn ñænh 2 . Caäp nhaät Mark[2], Tính d[2] vaø Pr[2] : Mark[2] = 1 ; d[2] = -1 ; Pr[2] = 3; Böôùc 4. Choïn ñænh 6 . Caäp nhaät Mark[6], Tính d[6] vaø Pr[6] : Mark[6] = 1 ; d[6] = 1; Pr[6] = 5 Böôùc 5. Choïn ñænh 4 . Caäp nhaät Mark[4], Tính d[4] vaø Pr[4] : Mark[4] = 1 ; d[4] = - 4 ; Pr[4] = 6 Thuaät toaùn keát thuùc vì taát caû caùc ñænh ñaõ ñöôïc choïn roài. Töø thuaät toaùn , ta coù keát quaû sau : d = [0, -1, -2, -4, 2, 1] Pr = [1, 3, 1, 6, 3, 5] Ñöôøng ñi ngaén nhaát töø s1 ñeán s2 : s1 → s3 → s2 vaø ñoä daøi laø -1 Ñöôøng ñi ngaén nhaát töø s1 ñeán s3 : s1 → s3 vaø ñoä daøi laø -2 Ñöôøng ñi ngaén nhaát töø s1 ñeán s4 : s1 → s3 → s5 → s6 → s4 vaø ñoä daøi laø - 4 Ñöôøng ñi ngaén nhaát töø s1 ñeán s5 : s1 → s3 → s5 vaø ñoä daøi laø 2 Ñöôøng ñi ngaén nhaát töø s1 ñeán s6 : s1 →s3 → s5 → s6 vaø ñoä daøi laø 1 Tröông Myõ Dung 39
  41. Simpo PDF Merge and Split Unregistered Version - 3. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. 3.4. GIÖÕA TAÁT CAÛ CAÙC CAËP ÑÆNH: THUAÄT TOAÙN FLOYD (1962). Ta seõ tính moät ma traän khoaûng caùch n x n. Neáu taát caû chieàu daøi khoâng aâm (l(u)≥ 0) ta coù theå aùp duïng n laàn thuaät toaùn Dijktra-Moore cho moãi ñænh i. . Neáu ñoà thò coù chöùa chieàu daøi aâm (l(u) < 0) ta coù theå aùp duïng n laàn thuaät toaùn Bellman-Ford cho moãiñænh i. Thuaät toaùn Floyd coù caùch tieáp caän khaùc coù lôïi cho tröôøng hôïp ma traän daày. Kyù hieäu : A : ma traän troïng löôïng, ñöôïc gaùn giaù trò ban ñaàu nhö sau : 0 neáu i = j A[i,j] = l(i, j) neáu (i, j) ∈ U ∞ nguôïc laïi. P : ma traän caùc ñænh tröôùc, ñöôïc gaùn giaù trò ban ñaàu nhö sau : P[i,j] = i, trong ñoù P[i,j] laø ñænh tröôùc cuûa ñænh j treân ñöôøng ñi töø goác i ñeán j Khi keát thuùc thuaät toaùn, ta coù : P[i,j] = ñænh tröôùc cuûa j treân ñöôøng ñi ngaén nhaát töø goác i ñeán ñænh j, vôùi chieàu daøi töông öùng laø A[i,j]. THUÛ TUÏC FLOYD(L, P) For (k =1; k≤ n ; k++) For (i =1 ;i≤ n ; i++) For (j =1 ;j≤ n ; j++) If (a[i,k] + a[k,j] < a[i,j]) { a[i,j] := a[i,k] + a[k,j] ; p[i,j] :=p[k,j] ;} Ñoä phöùc taïp : O(n3). Tröông Myõ Dung 40
  42. Simpo PDF Merge and Split Unregistered Version - 3. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. THÍ DUÏ. 1 2 2 -1 6 -2 -4 5 4 5 3 Gaùn ban ñaàu : cho caùc ma traän A, P. 1 2 3 4 1 2 3 4 1 0 2 ∝ 6 1 1 1 1 A0 = 2 ∝ 0 -2 ∝ P0 = 2 2 2 2 3 ∝ 5 0 5 3 3 3 3 4 -4 -1 ∝ 0 4 4 4 4 Caùc böôùc laëp : k =1. 1 2 3 4 1 2 3 4 1 0 2 ∝ 6 1 1 1 1 A1 = 2 ∝ 0 -2 ∝ P1 = 2 2 2 2 3 ∝ 5 0 5 3 3 3 3 4 -4 -2 ∝ 0 4 1 4 4 k = 2 1 2 3 4 1 2 3 4 1 0 2 0 6 1 1 2 1 A2 = 2 ∝ 0 -2 ∝ P2 = 2 2 2 2 3 ∝ 5 0 5 3 3 3 3 4 -4 -2 -4 0 4 1 2 4 k =3 1 2 3 4 1 2 3 4 1 0 2 0 5 1 1 2 3 A3 = 2 ∝ 0 -2 3 P3 = 0 2 2 3 3 ∝ 5 0 5 0 3 3 3 4 -4 -2 -4 0 4 1 2 4 k = 4 1 2 3 4 1 2 3 4 1 0 2 0 5 1 1 2 3 A4 = 2 -1 0 -2 3 P4 = 0 2 2 3 3 1 3 0 5 4 1 3 3 4 -4 -2 -4 0 4 1 2 4 Tröông Myõ Dung 41
  43. Simpo PDF Merge and Split Unregistered Version - 3. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. Caùch nhaän bieát ñöôøng ñi ngaén nhaát. Ñeå nhaän ñöôïc ñöôøng ñi ngaén nhaát töø s1 ñeán sj , ta söû duïng doøng thöù i cuûa ma traän P. Chaúng haïn, ta muoán nhaän ñöôïc ñöôøng ñi ngaén nhaát µ : s4 → s3, ta tham khaûo ma traän P nhö sau : P[4,3]=2 :s2 laø ñænh tröôùc cuûa s3 ; P[4,2]=1 : s1 laø ñænh tröôùc cuûa s2 ; P[4,1]=4 :s4 laø ñænh tröôùc cuûa s1 . Cuoái cuøng, keát quaû laø µ = s4 → s1 → s2→ s3. Moät trong öùng duïng cuûa Thuaät toaùn FLOYD laø tìm ñöôøng ñi giuõa hai ñænh. Thuaät toaùn naøy ñöôïc WARSHALL phaùt trieãn cuøng naêm (1962), vaø thuaät toaùn thöôøng mang teân FLOYD-WARSHALL ». Kyù hieäu : A = ma traän keà cuûa ñoà thò, ñöôïc gaùn giaù trò ban ñaàu nhö sau : l neáu (i, j) ∈ U A[i,j] = 0 nguôïc laïi. P = ma traän caùc ñænh tröôùc, ñöôïc gaùn giaù trò ban ñaàu nhö sau : 0 neáu a[i,j] = 0, P[i,j] = 1 nguôïc laïi. Khi keát thuùc thuaät toaùn : P[i,j] = ñænh tröôùc cuûa j treân ñöôøng ñi töø ñænh i ñeán ñænh j (nghóa laø a[i,j]=1). THUÛ TUÏC FLOYD-WARSHAL(A, P) For (k =1 ;k≤ n ; k++) For (i =1 ;i≤ n ; i++) For (j =1 ;j≤ n ; j++) If (a[i,j] = = 0) { a[i,j] = a[i,k] *a[k,j] ; p[i,j] =p[k,j] } Ñoä phöùc taïp : O(n3). Tröông Myõ Dung 42
  44. Simpo PDF Merge and Split Unregistered Version - 3. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. THÍ DUÏ. 1 2 4 3 Gaùn ban ñaàu : cho caùc ma traän A, P. 1 2 3 4 1 2 3 4 1 0 1 0 1 0 1 0 1 A0 = 2 0 0 1 0 P0 = 0 0 2 0 3 0 1 0 1 0 3 0 3 4 1 1 0 0 4 4 0 0 Caùc böôùc laëp : k =1. 1 2 3 4 1 2 3 4 1 0 1 0 1 0 1 0 1 A1 = 2 0 0 1 0 P1 = 0 0 2 0 3 0 1 0 1 0 3 0 3 4 1 1 0 1 4 4 0 1 k = 2 1 2 3 4 1 2 3 4 1 0 1 1 1 0 1 2 1 A2 = 2 0 0 1 0 P2 = 0 0 2 0 3 0 1 1 1 0 3 2 3 4 1 1 1 1 4 4 2 1 k =3 1 2 3 4 1 2 3 4 1 0 1 1 1 0 1 2 1 A3 = 2 0 1 1 1 P3 = 0 3 2 3 3 0 1 1 1 0 3 2 3 4 1 1 1 1 4 4 2 1 k = 4 1 2 3 4 1 2 3 4 1 1 1 1 1 4 1 2 1 A4 = 2 1 1 1 1 P4 = 4 3 2 3 3 1 1 1 1 4 3 2 3 4 1 1 1 1 4 4 2 1 Tröông Myõ Dung 43
  45. Simpo PDF Merge and Split Unregistered Version - 3. Ñoà thò phaúng vaø Baøi toaùn Toâ maøu. CHÖÔNG 4. ÑOÀ THÒ PHAÚNG & BAØI TOAÙN TOÂ MAØU. 4.1. ÑINH NGHÓA VEÀ ÑOÀ THÒ PHAÚNG. Ñoà thò phaúng laø moät ñoà thò coù theå bieåu dieãn treân moät maët phaúng (hay treân hình caàu) sao cho hai cung (hay hai caïnh) khoâng caét nhau. Ghi chuù. Hai caïnh coù chung moät ñænh ñöôïc goïi laø khoâng caét nhau. Caét nhau Khoâng caét nhau . Thí duï. Ñoà thò G1 laø ñoà thò phaúng vaø G2 , G3 laø caùc bieåu dieãn phaúng cuûa G1. Ñoà thò G1 Bieåu dieãn G2, G3 cuûa G1. Tröông Myõ Dung 43
  46. Simpo PDF Merge and Split Unregistered Version - 3. Ñoà thò phaúng vaø Baøi toaùn Toâ maøu. Cho G laø ñoà thò phaúng. Moät maët (FACE) cuûa G laø moät mieàn, giôùi haïn bôûi caùc caïnh, khoâng coù ñænh laãn caïnh ôû beân trong. Trong caùc maët naøy luoân luoân coù moät vaø chæ moät maët voâ haïn. Ñöôøng bieân (CONTOUR) cuûa moät maët r laø chu trình hôïp thaønh töø caùc caïnh bieân cuûa r. Hai maët r vaø s ñöôïc goïi laø KEÀ (ADJACENTES) neáu ñöôøng bieân cuûa chuùng coù chung ít nhaát moät caïnh. Hai maët khoâng coù chung moät ñænh naøo thì seõ khoâng keà. THÍ DUÏ. Moät baûn ñoà ñòa dö laø moät ñoà thò phaúng (vôùi ñieàu kieän laø khoâng coù ñaûo). Ñoà thò naøy ñaëc bieät moãi ñænh coù baäc ≥ 3. Maët h laø maët voâ haïn, nhöõng maët coøn laïi a, b, c, d, e, f, g laø nhöõng maët höõu haïn. h g A a c a b d e f FIG. 4.1. ÑOÀ THÒ PHAÚNG. Baøi toaùn ba laøng vaø ba nhaø maùy. Ta coù 3 laøng a, b, c, maø ta muoán ñaët ñöôøng noái vôùi 3 nhaø maùy : moät nhaø maùy cung caáp nöôùc d, moät nhaø maùy cung caáp ga e, moät nhaø maùy cung caáp ñieän f. Vaán ñeà ñaët ra laø , ta coù theå ñaët treân moät maët phaúng sao cho caùc ñöôøng daãn khoâng giao nhau ngoaøi caùc ñænh cöïc bieân ? Ñoà thò bieåu dieãn 3 laøng vaø 3 nhaø maùy cho pheùp ñònh nghóa moät lôùp caùc ñoà thò khoâng phaúng. a b c d e f FIG 4.2. ÑOÀ THÒ KHOÂNG PHAÚNG LOAÏI 1 : K3,3. Tröông Myõ Dung 44
  47. Simpo PDF Merge and Split Unregistered Version - 3. Ñoà thò phaúng vaø Baøi toaùn Toâ maøu. 4.2. COÂNG THÖÙC EULER , HEÄ QUAÛ & THÍ DUÏ. 4.2 1. COÂNG THÖÙC EULER. Cho moät ñoà thò phaúng lieân thoâng coù n ñænh, m caïnh vaø f maët, ta coù n - m + f = 2 Chöùng minh. Truy chöùng treân soá caïnh : m = 1. Ta coù n= 2 ñænh vaø f=1 maët. Ta coù n – m + f = 2 – 1 + 1 = 2 Vaäy coâng thöùc EULER ñuùng cho tröôøng hôïp m = 1. Giaû söû coâng thöùc EULER ñuùng cho tröôøng hôïp ñoà thò Gi-1 coù mi – 1 caïnh. Ta seõ chöùng minh coâng thöùc EULER cuõng ñuùng cho tröôøng hôïp ñoà thò coù mi caïnh. Goïi caïnh u = (x,y) laø caïnh veõ theâm vaøo Gi-1 ñeå coù Gi. Hieãn nhieân laø coù it nhaát moät ñænh thuoäc Gi-1 vaø u=(x,y) thuoäc moät maët K cuûa Gi-1. Giaû söû x ∈ Gi-1. Coù 2 tröôøng hôïp xaõy ra : 1. y ∈ K. Do ñoù ta coù : x fi = fi-1 + 1. ni = ni-1 K mi = mi-1 + 1 Ta coù : y ni - mi + fi = ni – (mi-1 + 1) + (fi-1 + 1). = ni – mi-1 + fi-1 = 2 Vaäy coâng thöùc EULER ñuùng. 2. y ∉ K. Ta coù : fi = fi-1 . ni = ni-1 + 1 mi = mi-1 + 1 Ta coù : ni - mi + fi = (ni + 1) – (mi-1 + 1) + fi-1 = ni – mi-1 + fi-1 = 2 Vaäy coâng thöùc EULER ñuùng. Vaäy coâng thöùc EULER ñuùng vôùi moïi m. Tröông Myõ Dung 45
  48. Simpo PDF Merge and Split Unregistered Version - 3. Ñoà thò phaúng vaø Baøi toaùn Toâ maøu. 4.2.2. Heä quaû. Trong moät ñoà thò ñôn giaûn phaúng, lieân thoâng baát kyø coù n ñænh, m caïnh (m > 2) vaø f maët. Khi aáy, ta coù : 3f/2 ≤ m ≤ 3n - 6. (1) Chöùng minh. Moãi maët bò bao ít nhaát 3 caïnh, moãi caïnh thuoäc 2 maët. Ba caïnh xaùc ñònh toái ña 2 maët. Vaäy soá maët toái ña laø 2m/3. Ta coù f ≤ 2m/3. Duøng coâng thöùc EULER suy ra baát ñaúng thöùc (1). 4.2.3. Heä quaû. Trong taát caû caùc ñoà thò phaúng ñôn giaûn, coù ít nhaát moät ñænh coù baäc ≤ 5. Chöùng minh. Giaû söû moïi ñænh coù baäc > 6. Khi aáy 2m > 6n ⇒ m > 3n > 3n – 6. Maâu thuaån. 4.2.4. THÍ DUÏ. Duøng coâng thöùc EULER, ta seõ chöùng minh laø taát caû ñoà thò ñaày ñuû 5 ñænh K5 laø khoâng phaúng. FIG 4.3. ÑOÀ THÒ KHOÂNG PHAÚNG LOAÏI 2 : K5. Chöùng minh. Ta coù soá ñænh n = 5, Soá caïnh m = n(n-1)/2 = 10. Neáu K5 phaúng, aùp duïng heä quaû 3.2.2 ta coù : 10 = m ≤ 3n – 6 = 3x5 – 6 = 9. Maâu thuaån. Vaäy K5 khoâng phaúng. Tröông Myõ Dung 46
  49. Simpo PDF Merge and Split Unregistered Version - 3. Ñoà thò phaúng vaø Baøi toaùn Toâ maøu. Nhaän xeùt. Ñoà thò nhöõng laøng vaø nhöõng nhaø maùy (Loaïi 1 : K3,3) vaø ñoà thò ñaày ñuû 5 ñænh (loaïi 2 :K5) cho pheùp ñònh nghóa taát caû nhöõng ñoà thò maø khoâng phaúng. K5, K3,3 cuøng laø ñoà thò ñeàu. Ñoà thò K5 khoâng phaúng vôùi soá ñænh nhoû nhaát, ñoà thò K3,3 laø ñoà thò khoâng phaúng coù soá caïnh nhoû nhaát, vaø caû hai laø ñoà thò khoâng phaúng ñôn giaûn nhaát. 4.3. BAÁT ÑAÚNG THÖÙC CAÏNH- ÑÆNH. 4.3.1. THÍ DUÏ. Ta xeùt baøi toaùn xaùc ñònh xem ñoà thò G cho tröôùc coù phaúng khoâng ? THÍ DUÏ 1. Cho ñoà thò K4 K4 phaúng. THÍ DUÏ 2. Cho ñoà thò G sau : a b c d h g f e G phaúng vì ta coù theå veõ laïi nhö sau : g b f a c h d e THÍ DUÏ 3. Ñoà thò sau ñaây khoâng phaúng. a b c Tröông Myõ Dung 47
  50. Simpo PDF Merge and Split Unregistered Version - 3. Ñoà thò phaúng vaø Baøi toaùn Toâ maøu. 1 2 3 4.3.2. BAÁT ÑAÚNG THÖÙC CAÏNH – ÑÆNH. Cho G laø moät ñoà thò phaúng lieân thoâng coù n ñænh, m caïnh vaø ñöôøng bieân cuûa caùc maët coù soá caïnh g ≥ 3. Khi aáy, ta coù : m ≤ (n-2) g/ (g-2). Chöùng minh. Giaû söû ma traän keà caïnh- maët coù daïng : f1 f2 . fj fF m1 . m2 . A = . . mI . . . mij . mf trong ñoù : mij = 1 neáu mI laø caïnh bieân cuûa fj, 0 ngöôïc laïi. Xeùt haøng thöù i, ta coù : Σ mij ≤ 2 ( vì mij laø caïnh bieân cuûa nhieàu nhaát 2 maët) Suy ra Σ Σ mij ≤ 2m (1) Xeùt coät thöù j, ta coù : Σ mij ≥ g (vì maët fj coù it nhaát g caïnh bieân) Suy ra Σ Σ mij ≥ gf (2) Theo coâng thöùc EULER, ta coù : n - m + f = 2 (3) Theo (2), (1), ta coù : gf = g(2 + m - n) ≤ 2m (2 + m - n) ≤ 2m/g ⇔ m(1-2/g) ≤ n – 2 ⇔ m ≤ (n-2) g/(g-2) BÑT ñaõ chöùng minh xong. Tröông Myõ Dung 48
  51. Simpo PDF Merge and Split Unregistered Version - 3. Ñoà thò phaúng vaø Baøi toaùn Toâ maøu. THÍ DUÏ. Nhôø Baát ñaúng thöùc treân, ta seõ chöùng minh ñöôïc raèng ñoà thò 3 laøng vaø 3 nhaø maùy K3,3 , xem hình FIG. 4.2. khoâng phaúng. Thaät vaäy, nhaän xeùt raèng moïi chu trình trong K3,3 coù soá caïnh ít nhaát laø 4. Vaäy neáu K3,3 phaúng moïi maët phaûi coù soá caïnh ít nhaát laø 4. Theo Baát ñaúng thöùc treân, ta coù : 9 = m ≤ (6-2) 4/(4-2) = 8. Maâu thuaån. Vaäy K3,3 khoâng phaúng. 4.4. PHEÙP ÑOÀNG DAÏNG. 4.4.1. ÑÒNH NGHÓA. Hai ñoà thò ñöôïc goïi laø ñoàng daïng vôùi nhau neáu ñoà thò naøy coù ñöôïc baèng caùch bieán ñoåi ñoà thò kia theo caùch theâm ñænh baäc 2 hoaëc boû ñi ñænh baäc 2. THÍ DUÏ. a b → a c b → a b Theâm Bôùt Ñænh c baäc 2 vaøo ab Ñænh c baäc 2 khoûi acb. 4.4.2. BOÅ ÑEÀ. Giaû söû H laø ñoà thò con cuûa G. Khi aáy : Neáu G phaúng thì H phaúng. Neáu H khoâng phaúng thì G cuõng khoâng phaúng. 4.4.3. BOÅ ÑEÀ. Moïi ñoà thò laø phaúng neáu ñoàng daïng cuûa noù laø phaúng. 4.5. ÑÒNH LYÙ KURATOWSKI. Ñoà thò G laø phaúng neáu vaø chæ neáu G khoâng chöùa moät ñoà thò con ñoàng caáu vôùi K5 cuõng nhö vôùi K3,3. Tröông Myõ Dung 49
  52. Simpo PDF Merge and Split Unregistered Version - 3. Ñoà thò phaúng vaø Baøi toaùn Toâ maøu. 4.6. BAØI TOAÙN TOÂ MAØU ÑOÀ THÒ. 4.6.1. ÑÒNH NGHÓA. Pheùp toâ maøu moät ñoà thò laø pheùp gaùn maøu cho caùc ñænh cuûa ñoà thò sao cho hai ñænh keà nhau coù maøu khaùc nhau. Moät caùch hình thöùc coù theå ñònh nghóa pheùp toâ maøu nhö sau : Pheùp toâ maøu laø moät aùnh xaï γ : X → N sao cho ∀ (x, y) ∈ X, γ(x) ≠ γ (y). THÍ DUÏ. FIG 4.4. Soá maøu (phaân bieät) ít nhaát caàn thieát ñeå toâ maøu caùc ñænh cuûa ñoà thò G ñöôïc goïi laø Saéc toá (CHROMATIQUE) vaø kyù hieäu laø γ (G). Moät ñoà thò G γ (G) ≤ k ñöôïc goïi laø k-saéc toá. Chaän treân cuûa saéc toá ñöôïc cho bôûi d + 1 vôùi d baäc lôùn nhaát cuûa ñænh. γ (G) ≤ d + 1 4.6.2. CAÙC ÖÙNG DUÏNG. XEÁP LÒCH THI. Giaû söû ta khaûo saùt vieäc thi vaán ñaùp cuûa moät kyø thi. Coù nhöõng raøng buoäc sau : ♦ Moät thaày , moät luùc chæ coù theå hoûi thi moät em. ♦ Moät thí sinh thi vôùi moät thaày vaøo moät thôøi gian ñaõ ñònh tröôùc. Söï phaân boá thí sinh thi vôùi thaày naøo ñaõ ñöôïc aán ñònh tröôc. (Thaày Pi thí sinh Ej) : THÍ DUÏ. (P1, E1), (P1, E2), (P1, E3), (P2, E1), (P2, E2), BAÛN ÑOÀ ÑÒA DÖ. Moät baøi toaùn heát söùc lyù thuù laø toâ maøu caùc baûn ñoà sao cho hai vuøng khaùc nhau khoâng cuøng moät maøu. Tröông Myõ Dung 50
  53. Simpo PDF Merge and Split Unregistered Version - 3. Ñoà thò phaúng vaø Baøi toaùn Toâ maøu. 4.6.3. THUAÄT TOAÙN TOÂ MAØU. DÖÕ LIEÄU : Ñoà thò G = (X, U). KEÁT QUAÛ : Moät pheùp toâ maøu γ : X → N. BEGIN. Cho τ = x1, x2, ,xn laø moät pheùp ñaùnh soá thöù töï caùc ñænh cuûa G. Cho C = {1 , 2, , k} taäp caùc maøu. FOR i=1 To n Do γ(xi) = Min{k ∈ C :∀ ñænh y keà x,, γ(y) ≠ k} END. 4.6.4. ÑÒNH LYÙ. Neáu G coù chöùa moät ñoà thò con ñaúng hình vôùi Km thì γ (G) ≥ m. CHÖÙNG MINH. Hieãn nhieân. 4.6.5. ÑÒNH LYÙ 5 MAØU (KEMPE-HEAWOOD). Moïi ñoà thò phaúng ñeàu coù 5-saéc toá. Tröông Myõ Dung 51
  54. Simpo PDF Merge and Split Unregistered Version - 3. Ñoà thò phaúng vaø Baøi toaùn Toâ maøu. 4.6.6. BAØI TOAÙN 4 MAØU. GIAÛ THIEÁT BAØI TOAÙN 4 MAØU. Treân moät baûn ñoà baát kyø, ta noùi noù ñöôïc toâ maøu neáu moãi mieàn cuûa baûn ñoà ñöôïc toâ moät maøu xaùc ñònh sao cho 2 mieàn keà nhau (chung moät phaàn bieân) phaûi ñöôïc toâ baèng hai maøu khaùc nhau. Vaán ñeà ñaët ra laø caàn duøng toái thieåu bao nhieâu maøu ñeå toâ ñöôïc moät baûn ñoà baát kyø. Vaán ñeà naøy ñöôïc ñaët ra töø naêm 1852 do giaùo sö De Morgan ñaët ra : « Moïi baûn ñoà ñeàu coù theå toâ baèng 4 maøu sao cho hai nöôùc naèm keà nhau phaûi ñöôïc toâ baèng hai maøu khaùc nhau ». Sau ñoù coù raát nhieàu coá gaéng cuûa caùc nhaø toaùn hoïc ñeå giaûi baøi toaùn naøy nhöng ñeàu khoâng ñi ñeán keát quaû cuoái cuøng. Cho ñeán naêm 1976, moät nhoùm caùc nhaø toaùn hoïc (K. Appel, W. Haken, J.Koch) ñaõ xaây döïng moät lôøi giaûi döïa treân keát quaû do maùy tính IBM cung caáp ñaõ khaúng ñònh ñöôïc giaû thieát 4 maøu laø ñuùng. LIEÂN QUAN GIÖÕA BAØI TOAÙN 4 MAØU & SAÉC TOÁ ÑOÀ THÒ PHAÚNG. Cho moät ñoà thò phaúng G lieân thoâng, khoâng coù ñænh coâ laäp. Ta xaây döïng moät ñoà thò ñoái ngaãu cuûa noù goïi laø G nhö sau : Moãi ñænh x* cuûa G töông öùng ñuùng vôùi moät maët s cuûa G. Môõi caïnh u* cuûa G noái 2 ñænh cuûa G töông öùng vôùi 2 vuøng keà nhau vaø caét caïnh chung cuûa hai vuøng ñoù. G ñöôïc xaây döïng nhö treân laø moät ñoà thò phaúng, vaø cuõng khoâng coù ñænh coâ laäp. Chuù yù : Ñoái ngaãu cuûa G laø G. HEÄ QUAÛ. Trong taát caû caùc baûn ñoà ñòa dö, coù ít nhaát moät maët coù ñöôøng bieân coù soá caïnh ≤ 5. Chöùng minh. Chuyeån baûn ñoà ñòa dö thaønh ñoà thò ñoái ngaãu. Giaû thieát trôû thaønh « coù it nhaát moät ñænh coù baäc 5 ≤ ». aùp duïng Heä quaû 4.2.3. suy ra keát luaän cuûa heä quaû treân. ÑÒNH LYÙ 4 MAØU. Moïi ñoà thò phaúng coù saéc toá γ (G) ≤ 4. Tröông Myõ Dung 52