Lí thuyết đồ thị part 6

Chia sẻ: ágffq ằefgsd | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

99
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Năm 1845, Gustav Kirchhoff đưa ra Định luật Kirchhoff cho mạch điện để tính điện thế và cường độ dòng điện trong mạch điện. Năm 1852 Francis Guthrie đưa ra bài toán bốn màu về vấn đề liệu chỉ với bốn màu có thể tô màu một bản đồ bất kì sao cho không có hai nước nào cùng biên giới được tô cùng màu. Bài toán này được xem như đã khai sinh ra lí thuyết đồ thị, và chỉ được giải sau một thế kỉ vào năm 1976 bởi Kenneth Appel và Wolfgang Haken. Trong khi cố gắng giải...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lí thuyết đồ thị part 6

Edge[i] = Vertex[alpha[i]]; Vertex[beta[i]] = Vertex[alpha[i]]; } else if (Vertex[alpha[i]] != Vertex[beta[i]]) { Edge[i] = Vertex[alpha[i]]; Tempt = Vertex[beta[i]]; for (j = 1; j
´’ a ım a ˙ a a 4.3.4 Thuˆt to´n t` tˆ t ca c´c cˆy bao tr` m a u . Viˆc phˆn t´ c´c mach d iˆn vˆ co. ban c´ thˆ’ d u.a vˆ b`i to´n t` tˆ t ca c´c cˆy bao tr`m ˙ . ¯e ` ` a a ım a ˙ a a ´’ ˙ o e¯ ’ e a ıch a .e e u . cua d` thi (xem [19]). Do tˆm quan trong cua n´, c´ nhiˆu thuˆt to´n kh´c nhau giai quyˆt ` ˙ oo ` ´ ˙ ¯o . ’ˆ ’ ˙ ’ a e a a a e . . .ng phu.o.ng ph´p l` ho´n d o’i c´c chu tr` nhu. sau: Xuˆ t ph´t ˙a ´ b`i to´n n`y. Mˆt trong nh˜ aaa o u a a a ¯ˆ ınh a a . t`. mˆt cˆy bao tr`m T n`o d ´. V´.i mˆ i canh khˆng nˇ m trˆn cˆy T, khi thˆm v`o cˆy n`y ˜ ` uoa u a ¯o o o . o a ea e aaa . ´o ´ ˙o. ’. s˜ tao ra duy nhˆ t mˆt chu tr` e. a ınh. X´a bo mˆt canh bˆ t k` trong chu tr` n`y s˜ cho ta o ay ınh a e . mˆt cˆy bao tr`m m´.i. oa u o . Do sˆ c´c cˆy bao tr`m l` rˆ t l´.n thˆm ch´ ca v´.i nh˜.ng d` thi nho, t´ hiˆu qua ´ ´ ı˙o’ ˙ ınh e ’ ˙ ’ oa a u aa o a u ¯o . ˆ . . ˙ a nh˜.ng thuˆt to´n giai quyˆt b`i to´n rˆ t quan trong (xem [14]). Mˆt tˆ’ng quan cua c´c ˙ ´aaa ´ ’ ˙ ’ ˙a ’ cu u a a e oo . . . phu.o.ng ph´p n`y l` mˆt luˆn ´n tiˆn s˜ cua Chase [12]. Chase d ˜ chı ra rˇ ng thuˆt to´n ` ´ e ı˙ ’ ¯a ˙ ’ aaao aa a a a . . . .a ra bo.i Minty c´ hiˆu qua nhˆ t: liˆn tiˆp thu gon d` thi bˇ ng c´c ph´p to´n xo´ mˆt ` ´ ´ ˙’ ˙ ’ du ¯ oe a e e . ¯ˆ . a o a e a ao . . canh v` ho.p nhˆ t c´c d ınh d` u cuˆi cua n´. T`. c´c cˆy bao tr`m cua c´c d` thi thu gon ´ ´’ a a ¯˙ ’ ¯a o ˙ o ua a ˙ a ¯o . ’ a. ˆ u ˆ . . (m` nho ho.n rˆ t nhiˆu) ta c´ thˆ’ du.ng d u.o.c tˆ t ca c´c cˆy bao tr`m cua d` thi ban d` u. ˙ ´ ` ´’ ˙ ’ ¯. a ˙a a ˙ ¯ˆ . ’o a a e oe. u ¯ˆ a Dˆ’ bao d am thuˆt to´n kˆt th´c, c´c d` thi c´ k´ thu.´.c du.´.i mˆt ngu.˜.ng cho tru.´.c s˜ - e ˙ ¯˙ ˙’ ´ ’ a ae u a ¯o . o ıch ˆ o o o o oe . . .o.c thu gon thˆm; thay v`o d ´ l` c´c cˆy bao tr`m cua ch´ng d u.o.c suy ra. ˙ ’ khˆng d u . o¯ e a ¯o a a a u u ¯. . Hˆ co. so. cua c´c chu tr` d oc lˆp ˙˙ ’’a 4.3.5 e ınh ¯ˆ a . .. Nhˇc lai rˇ ng chu sˆ cua d` thi vˆ hu.´.ng G c´ n d ınh, m canh, p th`nh phˆn liˆn thˆng ´ ` ´’ ˆ ` o ˙ ¯o . o o o ¯˙ ’ a.a a ae o . ` ng c(G) = m − n + p−ch´ l` sˆ cu.c d ai c´c chu tr` d oc lˆp. Phˆn du.´.i d ˆy ta xˆy ´ . ¯. a ` bˇ a ınh a o ınh ¯ˆ a a o ¯a a .. du.ng thuˆt to´n t` hˆ co. so. cua c´c chu tr` d oc lˆp du.a trˆn cˆy bao tr`m cua d` thi. ˙˙a ’’ ˙ ¯ˆ . ’o a a ım e ınh ¯ˆ a ea u . . . .. . Khˆng giam tˆ’ng qu´t, c´ thˆ’ gia thiˆt d` thi G liˆn thˆng, v` trong tru.`.ng ho.p tr´i lai, ˙ ˙’ ´ˆ ˙ ’ aoe˙ o o e ¯o . e o ı o a. . .ng th`nh phˆn liˆn thˆng. Y tu.o.ng o. d ˆy l` ´ ` ˙ ’ ˙ ¯a a ’ th` ta x´t t` ı eu a ae o 1. Xˆy du.ng cˆy bao tr`m T := (V, ET ). a a u . 2. Gia su. e1 , e2 , . . . , em−n+1 l` c´c canh cua E m` khˆng thuˆc cˆy T. Khi thˆm mˆt canh ˙˙ ’’ ˙ ’ aa . ao oa e o. . . bˆ t k` trong c´c canh n`y, chˇng han canh ek , v`o cˆy T ta d u.o.c mˆt v` chı mˆt chu ˙ ’ ´ oa˙o ’. ay a. a a aa ¯. . . . tr` µk . C´c chu tr` µ1 , µ2 , . . . , µm−n+1 l` d ˆc lˆp v` mˆ i chu tr` ch´.a mˆt canh ˜ ınh a ınh a ¯o a ı o ınh u o. .. . khˆng thuˆc c´c chu tr` kia; mˇt kh´c ta c´ (m − n + 1) = c(G) chu tr` nhu. vˆy, o oa ınh a a o ınh a . . . .o.c hˆ co. so. cua c´c chu tr` d ˆc lˆp. ˙˙a ’’ nˆn ta d ˜ x´c d .nh d u . e e ¯a a ¯i ¯ ınh ¯o a . .. Nhu. vˆy b`i to´n d u.a vˆ t` c´c chu tr` µk khi thˆm canh ek v`o cˆy T. Trong khi ` ım a a a a¯ e ınh e aa . . kiˆ’m tra canh ek = (αk , βk ) trong thuˆt to´n 4.3.3, nˆu d iˆu kiˆn 3 d ung (t´.c l` ca hai d ınh ˙ e ¯` ´ ua˙ ’ ¯˙’ e a a e e ¯´ . . . ´t hiˆn trong c`ng cˆy Ti ) th` thay cho viˆc loai bo canh n`y ch´ng ta cˆn t`` ım . ˙.’ αk v` βk xuˆ a a e u a ı e a u a . . c´c canh trong Ti m` tao th`nh dˆy chuyˆn gi˜.a hai d ınh αk v` βk . Dˆy chuyˆn n`y c`ng ` ` ¯˙’ a. a. a a e u a a eau v´.i canh (αk , βk ) tao th`nh mˆt chu tr` co. ban. Vˆ n d` ch´ o. d ay l` t` dˆy chuyˆn ´e ` ˙ ’ a ¯ˆ ınh ˙ ¯ˆ a ım a ’ o. a o ınh e . . 112
n`y. C´ nhiˆu phu.o.ng ph´p hiˆu qua giai quyˆt b`i to´n, trong sˆ d ´ thuˆt to´n cua Paton o` ´ ´ ˙˙ ’’ a˙ ’ a e a e eaa o ¯o a . . ´ ˙ ’a [50] l` hiˆu qua nhˆ t. ae . Thuˆt to´n Paton t` hˆ co. so. cua c´c chu tr` d oc lˆp ˙˙ ’’a a a ım e ınh ¯ˆ a . . .. Ch´ng ta c˜ng s˜ kiˆ’m tra mˆ i canh c´ tao th`nh chu tr` v´.i nh˜.ng canh trong cˆy d u.o.c ˙ ˜ u u ee o. o. a ınh o u a¯. . .ng trong qu´ tr` thu.c hiˆn thuˆt to´n, nhu.ng thay viˆc lˆ y c´c canh theo th´. tu. ´ xˆy du a a ınh . e a a eaa. u. . . . . . trong Thuˆt to´n 4.3.3), ta chon mˆt d ınh z v` kiˆ’m tra c´c canh liˆn thuˆc v´.i ˙ o ¯˙ .’ tu` y (nhu y´ a a ae a. e oo . . . - ınh z l` d ınh v`.a d u.o.c thˆm v`o cˆy). Dˆ’ d o.n gian, ta s˜ su. dung ma trˆn kˆ A biˆ’u -e¯˙ ˙ ` ˙’ ˙ ’ ˙ ’ ˙. ’ n´. (D o a¯ u¯. e aa e ae e . .o.c xˆy du.ng o. bu.´.c n`o d o ˜ ¯o . y e diˆn d` thi. K´ hiˆu T l` tˆp hiˆn h`nh c´c d ınh trong cˆy d u . a a ¯˙’ ˙ ’ eˆ aa ea a¯ o a ¯´ . . . . .a d u.o.c kiˆ’m tra (t´.c l` nh˜.ng d ınh thuˆc T hoˇc khˆng nhu.ng ˙ a a a ¯˙ ’ ¯˙ ’ v` W l` tˆp c´c d ınh chu ¯ . a e uau o a o . . . c´ ´ nhˆ t mˆt canh liˆn thuˆc v´.i n´ chu.a d u.o.c kiˆ’m tra). ˙ ´o. o ıt a e ooo ¯. e . . Ch´ng ta kho.i d` u thuˆt to´n bˇ ng c´ch d at T = {v1 } v` W = V. Dınh v1 s˜ l` gˆc -˙ a` ´ ˙ ¯a ’ˆ ’ u a a a ¯ˇ a ea o . . ˙ a cˆy. Sau qu´ tr` kho.i tao, thu.c hiˆn c´c bu.´.c sau: ’a ˙. ’ cu a ınh ea o . . 1. Nˆu T ∩ W = ∅ thuˆt to´n d`.ng. ´ e a au . ´ . ¯˙ ’ 2. Nˆu T ∩ W = ∅ chon d ınh z ∈ T ∩ W. e 3. Kiˆ’m tra z bˇ ng c´ch x´t mˆ i canh liˆn thuˆc v´.i n´. Nˆu khˆng c´ canh n`o, khu. z ˙ ` ˜ ´ ˙’ e a a e o. e oooe o o. a . . W v` chuyˆ’n sang Bu.´.c 1. ˙ t` u a e o 4. Nˆu tˆn tai canh (z, p) ∈ E kiˆ’m tra z c´ thuˆc T khˆng. ˙ e`.. ´o e o o o . 5. Nˆu p ∈ T t` chu tr` co. ban gˆm canh (z, p) v` mˆt dˆy chuyˆn (duy nhˆ t) t`. ´ ˙` ` ´u ’o e ım ınh aoa e a . . z dˆn p trong cˆy d ang d u.o.c xˆy du.ng. Xo´ canh (z, p) khoi d` thi v` chuyˆ’n sang ˙ ´ ˙ ¯o . a ’ˆ ¯e a¯ ¯. a a. e . Bu.´.c 3. o 6. Nˆu p ∈ T thˆm canh (z, p) v`o cˆy v` d ınh p v`o T. Xo´ canh (z, p) khoi d` thi v` ´ a a a ¯˙ ’ ˙ ¯o . a ’ˆ e / e a a. . ˙n sang Bu.´.c 3. ’ chuyˆ e o Nhu. d a d` cˆp, vˆ n d` co. ban l` Bu.´.c 5. Ch´ng ta phai t` dˆy chuyˆn t`. z dˆn p ´e ` u ¯e ´ ˙a ’ ˙ ım a ’ ¯˜ ¯ˆ a e. a ¯ˆ o u e . thˆ n`o? Thu tuc sau s˜ tra l`.i cˆu hoi n`y. ´ ˙. ’ e ˙o a ’ ˙a ’ nhu e a Ch´ng ta su. dung mˆt ngˆn xˆp (stack) T W = T ∩ W dˆ’ lu.u tr˜. c´c d ınh trong cˆy ˙ ´ ˙. ’ u a ¯˙’ u o ae ¯e a . .ng chu.a d u.o.c kiˆ’m tra. Dınh d u.o.c thˆm gˆn d ay nhˆ t v`o cˆy s˜ d u.o.c ch`n v`o d` u -˙ ˙ ` ¯ˆ ´ a a e¯ . ’ ¯. nhu ¯. e e a a e a ¯a ˆ ngˆn xˆp. Mˆ i lˆn mˆt d ınh d u.o.c kiˆ’m tra d u.o.c lˆ y ra khoi t`. d ınh cua ngˆn xˆp. Ta su. ˙ ˜a ´ o` ´ ´ o ¯˙ ’ ¯. ˙ u ¯˙ ’ ’ ˙ ’ ˙ ’ ae e ¯. a ae . ´n t´ d ˆ d`i n : mang l[j ] l` khoang c´ch t`. gˆc v1 dˆn d ınh vj ´ ´ ¯˙ ˙’ ˙ ’ ˙ ’ ’ dung thˆm hai mang tuyˆ ınh ¯o a e e a a uo ¯e . . trong cˆy bao tr`m; v` Pred[j ] l` d ınh vi sao cho canh (vi , vj ) l` mˆt canh trong cˆy v´.i a ¯˙’ a u a ao. ao . . vi gˆn gˆc ho.n vj . N´i c´ch kh´c, Pred[j ] l` d ınh liˆn tru.´.c d ınh vj trong dˆy chuyˆn t`. ` ´ ` `u a ¯˙’ o ¯˙ ’ ao oa a e a e 113
v1 dˆn vJ . Nh˜n l[J ] = −1 nˆu v` chı nˆu d ınh vj khˆng thuˆc tˆp T. Kho.i tao l[1] = 0 v` ´ ´ ’´ ’ e a ˙ e ¯˙ ˙. ’ ¯e a o oa a .. .i moi j = 2, 3, . . . , n. l[j ] = −1 v´ o . Trong Bu.´.c 5, khi x´t d ınh z v` canh (z, p) d u.o.c t` thˆ y v´.i p ∈ T. Dˆ’ x´c d .nh chu - e a ¯i ˙ ´ e ¯˙’ o a. ¯ . ım a o tr` co. ban sinh bo.i canh (z, p) ch´ng ta lˆn theo dˆy chuyˆn t`. z dˆn p trong cˆy bˇ ng a` ` ` u ¯e ´ ˙ ’ ˙. ’ ınh u a a e a ´. ´ ` ´ ´ c´ch t` liˆn tiˆp c´c “tiˆn bˆi” Pred[z ], Pred[Prede[z ]], . . . cho dˆn khi ch´ng ta bˇt gˇp a ım e ea eo ¯e u aa Pred[p]-tiˆn bˆi cua p. N´i c´ch kh´c, nhu. chı ra trong H` ??, chu tr` co. ban d u.o.c tao ` ´’ eo˙ ˙ ’ ˙ ¯. . ’ oa a ınh ınh ra l` a z, Pred[z ], Pred[Pred[z ]], . . . , Pred[p], p, z. Cˆn ch´ y rˇ ng tiˆn bˆi Pred[k ] cua moi d ınh k ∈ T l` mˆt d ınh m` hoˇc d ˜ d u.o.c ` ` ` ´ ˙ ’ . ¯˙’ a o ¯˙ ’ a u´ a eo a a ¯a ¯ . . . ˙m tra hoˇc d ang d u.o.c kiˆ’m tra. T´.c l`, nˆu k ∈ T ∩ W th` ’ ˙ ´ kiˆ e a¯ ¯. e uae ı . nhu.ng Pred[k ] ∈ T. Pred[k ] ∈ W / Thu tuc FundamentalCircuits() minh hoa c´c bu.´.c d a tr` b`y o. trˆn. ˙. ’ o ¯˜ ınh a ˙ e ’ .a Th`.i gian thu.c hiˆn cua thuˆt to´n bi chˇn trˆn bo.i nν trong d ´ gi´ tri thu.c ν ∈ [2, 3] e˙ ’ ˙ ’ o a a.a e ¯o a . . . . . . ´u tr´c cua d` thi c˜ng nhu. c´ch d anh nh˜n c´c d ınh [50]. ˙ ¯ˆ . u ’o ˙ ’ phu thuˆc v`o cˆ oaa u a ¯´ a a¯ . . Mˇc d` dˆ’ d o.n gian ch´ng ta d a gia su. G liˆn thˆng, tuy nhiˆn thuˆt to´n c´ thˆ’ ˙ ˙ ˙ ’ ¯˜ ˙ ˙ ’’ a u ¯e ¯ u e o e a aoe . . ˜ d`ng cai biˆn cho tru.`.ng ho.p tˆ’ng qu´t. D` u tiˆn, thuˆt to´n s˜ tao ra tˆ t ca c´c chu -ˆ ˙ ´’ ˙ ’e a ˙a dˆ a e o .o a a e a a e. . tr` co. ban trong th`nh phˆn liˆn thˆng ch´.a d ınh xuˆ t ph´t v1 . Sau d ´ ta chon d ınh y ` ´ ˙ ’ u ¯˙ ’ . ¯˙’ ınh a ae o a a ¯o .i y l` gˆc cua cˆy bao tr`m th´. hai. Thuˆt to´n lˇp lai cho dˆn ´ˆ m` l[y ] = −1 v` bˇt d` u v´ ´’ ´ ao ˙ a a a a ¯a o u u a aa. ¯e . . ´t ca c´c d ınh d u.o.c g´n nh˜n l kh´c −1. ˙ a ¯˙ ¯ . a ’ ’ khi tˆa a a Cˆy bao tr` m tˆi thiˆ’u ˙ ´ 4.4 a u o e Dinh ngh˜ 4.4.1 Gia su. G l` d` thi c´ trong sˆ. Cˆy bao tr`m tˆi thiˆ’u cua G l` mˆt -. ˙˙ ´a ´ ˙˙ ’’ ’ ıa a ¯o . o . ˆ o u o e ao . .i trong lu.o.ng nho nhˆ t. ´ ˙ ’ ˙ ’a cˆy bao tr`m cua G v´ a u o . . ˙ ’ ´ B`i to´n n`y rˆ t hay gˇp trong thˆng tin liˆn lac v` trong c´c ng`nh kh´c. Chˇng han aaaa a o e.a a a a a . . . sau: d ˆ d`i dˆy d iˆn ngˇn nhˆ t cˆn thiˆt dˆ’ nˆi n th`nh phˆ d a d inh ˙o ´ a` ´a e ¯e ´ ´ ´ ˙ ’ ta d at cˆu hoi nhu ¯ˇ a ¯o a a ¯ e a a o ¯˜ ¯. . . . l` bao nhiˆu? Khi d ´ coi c´c th`nh phˆ l` c´c d ınh cua d` thi v` w(a, b) l` khoang c´ch ´ o a a ¯˙ ’ ˙ ¯ˆ . a ’ ˙’ a e ¯o a a o a a .a c´c th`nh phˆ a v` b. Mang dˆy d iˆn cˆn phai liˆn thˆng, v` v` d o d`i ` ´ a ¯e ` ˙e ’ t´ bˇ ng km gi˜ a ınh a u a o a a o a ı ¯ˆ a . . . ’. ¯´ a o a ˙ ¯a ´ a ¯e ` ´ ` dˆy d iˆn cˆn ngˇn nhˆ t nˆn n´ khˆng c´ chu tr` a a aeoo o ınh: vˆy mang d o l` mˆt cˆy. O d ˆy ta cˆn a a . . . . ´i thiˆ’u” c´ thˆ’ d u.o.c v` l` mˆt d` thi bˆ phˆn cua d` thi d` y d u c´ n d ınh. ˙ ˙ ¯ . a a o ¯o . o a ˙ ¯ˆ . ¯a ¯ ˙ o ¯˙ ’o ’ ’ t` mˆt cˆy “tˆ ım o a o e oe .ˆ ˆ . . . Mˆt u.ng dung gi´n tiˆp: b`i to´n t` cˆy bao tr`m tˆi thiˆ’u l` bu.´.c trung gian trong viˆc ˙ ´ ´ o´ a e a a ım a u o eao e . . . .i giai cua b`i to´n ngu.`.i du lich-mˆt b`i to´n thu.`.ng xuˆ t hiˆn trong thu.c tˆ. ´e ´ ˙˙aa ’’ t` l` ım o o oaa o a e . . . . 114
C` n ch´ y rˇ ng, cˆy bao tr`m tˆi thiˆ’u cua d` thi khˆng liˆn quan dˆn cˆy sinh bo.i ˙ ˙ ¯o . o ` ´ ´ ’ˆ ˙ ’ ˆ a u´ a a u o e e ¯e a . mˆt d ınh cho tru.´.c. Do d ´, d` thi trong H` 4.10(a), ´ ´’ ` ´ tˆ t ca c´c dˆy chuyˆn ngˇn nhˆ t t` o ¯˙ a ˙a a au.’ e a o ¯o ¯ˆ .o ınh v´.i c´c sˆ trˆn c´c canh tu.o.ng u.ng c´c trong lu.o.ng canh, cˆy sinh ra bo.i d u.`.ng d i ngˇn ´ ´ ˙ ¯o ’ oaoea. ´ a a ¯ a . . . ´t t`. d ınh cho tru.´.c, chˇng han v1 , trong H` 4.10(b); ngu.o.c lai, cˆy bao tr`m tˆi thiˆ’u ˙ ˙ ’ ´ ˙ ’ nhˆ u ¯ a o a ınh ..a uo e . cho trong H` 4.10(c). ınh v1 v1 v1 ..•.. ..•.. •. .... .. .... .. . ........ ........ . . . . . ... . ... ... . ... . . ... . ... ... . ... . . . . ... . .... .. ... ... . ... .. ... . . . ... . ... . . .. ... . ... ... .. ... . . . 5................... 5 ... . . . ... ... . . . ... ... ... . . . ... . ... . . ... ... ... . . . ... . ... . ... . . ... . ... ... . ... . . 3 . .. . . .. . ... . . ... ... . .. . ... . .. ... ... . . . . ... . ... . ... ... . ... ... . ... . . ... . . . ... . ... ... . ... . ... . ... ... . ... . . ... . . . ... ... . ... . ... ... . . ... ... . . . ... ... ... . . . ... . ... . ... ... . ... . . ... . . ... ... 3 3 ... . . ... . . ... ... . . ... . ... . ... ... . . ... .. . . .. . v4 • • v2 v4 • • v2 v4 • • v2 ... . • • • ................................................................... ... . . ... ... . . ... . . ................................................................... .. . ................................................................... .... .. . . .................................................................. .. . . . ... ... ... ... . ... v5 v5 v5 ... ... ... . ... ... . ... ... ... . ... ... ... . . . ... ... . ... ... ... ... ... ... . . . . ... ... ... . ... ... ... ... ... . . .. .. .. ... .. .. .. ... . . ... ... ... ... ... ... . ... ... . ... ... ... . ... ... ... ... . ... 5 . ... ... ... ... ... ... . ... ... . ... ... ... . ... ... ... ... . ... . ... ... ... ... ... ... . ... 5 3 ... . .. .. .. . .. .. .. ... . ... ... ... ... . ... ... ... . ... ... . ... . ..... ... ... ... . ..... ... ... ... ... . ... ... ... . ... ... . ... .. .. . . . • • • ... ... . ..... ... ... .... . v3 v3 v3 (a) (b) (c) H` 4.10: (a) D` thi G. (b) Cˆy sinh bo.i d u.`.ng d i ngˇn nhˆ t xuˆ t ph´t t`. v1 . (c) Cˆy bao -ˆ . ´ ´ ´ ˙ ¯o ¯ ’ ınh o a a a a au a ´ ˙ ’a tr`m nho nhˆ t. u T` cˆy bao tr`m tˆi thiˆ’u l` mˆt trong nh˜.ng b`i to´n cua l´ thuyˆt d` thi c´ thˆ’ ˙ ˙ ´ ´ˆ ˙y ’ ım a u o eao u aa e ¯o . o e . .o.c tao ra trong qu´ tr` xˆy du.ng giai quyˆt triˆt dˆ’. Do d o, d at Ti v` Tj l` hai cˆy con d u . . ˙ ´ ˙ ’ e e ¯e ¯´ ¯ˇ a a a ¯ a ınh a . . . .o.c su. dung dˆ’ biˆ’u diˆn tˆp c´c d ınh cua cˆy con th` ∆ cˆy bao tr`m tˆi thiˆ’u. Nˆu Ti d u . ˙ . ˙ ˙˙ ˜ a a ¯˙ ´ ´ ’ ’ ˙a ’ a uo e e ¯ ¯e e e. ı ij c´ thˆ’ d .nh ngh˜ l` khoang c´ch ngˇn nhˆ t t`. mˆt d ınh trong Ti dˆn mˆt d ınh trong Tj ; ˙ ´ ´ ´ ˙ ’ a u o ¯˙ .’ o ¯˙ .’ o e ¯i ıa a a a ¯e .c l` t´ a u ∆ij := min [ min {w(vi , vj )}], i = j. (4.1) vi ∈Ti vj ∈Tj Khi d o, dˆ d`ng ch´.ng minh rˇ ng lˇp lai ph´p to´n sau s˜ cho ta cˆy bao tr`m tˆi ¯´ ˜ a ` ´ e u a a. e a e a u o . thiˆ’u: ˙ e Ph´p to´n I. V´.i cˆy con Ts n`o d o, t` cˆy con Tj ∗ sao cho ∆sj ∗ = minTj [∆sj ], v` d at e a oa a ¯´ ım a a ¯ˇ . .o.ng u.ng gi´ tri ∆ ∗ trong (4.1) d at d u.o.c. Khi d ´ (v , v ∗ ) thuˆc (vs , vj ∗ ) l` canh tu a. ´ a . sj ¯. ¯ . ¯o s j o . cˆy bao tr`m tˆi thiˆ’u v` c´ thˆ’ d u.o.c thˆm v`o v´.i c´c canh kh´c trong qu´ tr` ˙ ˙ ´ a u o e a o e¯ . e aoa. a a ınh lˇp dˆ’ tao ra cˆy bao tr`m tˆi thiˆ’u. ˙ ˙ ´ a ¯e . a u o e . Thˆt vˆy, gia su. c´c canh trong c´c cˆy con o. bu.´.c k n`o d o thuˆc cˆy bao tr`m tˆi ´ ˙˙a . ’’ ˙ ’ aa aa o a ¯´ oa u o .. . ˙u Tm o. bu.´.c cuˆi c`ng. Gia su. canh (vs , vj ∗ ) d u.o.c chon nhu. trˆn khˆng thuˆc cˆy bao ’ ´ ˙ ’ ˙˙. ’’ thiˆ e o ou ¯. e o oa . . 115
tr`m tˆi thiˆ’u Tm . Theo d inh ngh˜ cˆy con Ts o. bu.´.c cuˆi c`ng d u.o.c nˆi v´.i cˆy con kh´c ˙ ´ ´ ´ ˙ ’ uo e ¯. ıa, a o o u ¯. o o a a n`o d o bˇ ng canh (vi , vj ) trong d ´ vi ∈ Ts v` vj ∈ Ts v` ngo`i ra Ts phai ch´.a trong cˆy ` ˙ ’ a ¯´ a ¯o a / a a u a . bao tr`m tˆi thiˆ’u Tm . Xo´ canh (vi , vj ) khoi cˆy Tm s˜ cho ta hai th`nh phˆn liˆn thˆng ˙ ´ ` ˙a ’ u o e a. e a ae o ˙.i canh (vs , vj ∗ ) s˜ tao mˆt cˆy m´.i c´ trong lu.o.ng nho ho.n trong lu.o.ng cˆy ’. ˙ ’ v` thay n´ bo a o e. oa oo. a . . . . Tm , mˆu thuˆn. Vˆy, v´.i nh˜.ng gia thiˆt trˆn, ta c´ thˆ’ thˆm canh (vs , vj ∗ ) dˆ’ tao th`nh ˙ ˙ ˜ ´e ˙ ’ a a a o u e oee ¯e . a . . cˆy (ch´.a trong cˆy bao tr`m tˆi thiˆ’u) o. bu.´.c k v` tiˆp tuc v´.i bu.´.c (k + 1). C˜ng cˆn ˙’ ´ ´ ` e˙ a u a u o o ae . o o u a ch´ y rˇ ng, phu.o.ng ph´p trˆn khˆng phu thuˆc v`o cˆy Ts d u.o.c chon. Ho.n n˜.a, do bu.´.c u´ ` a a e o oaa ¯. u o . . . .i tao (t´.c l` tru.´.c khi bˆ t c´. canh n`o d u.o.c chon) gia thiˆt l` khˆng tˆn tai (v` do d ´ ´ ´ `. ˙ ’ ˙ ’ kho . ua o au. a¯. ea o o a ¯o . ´i c`ng s˜ tao ra cˆy bao tr`m tˆi thiˆ’u. ˙ ´ d ung) nˆn lˇp lai thuˆt to´n trˆn cuˆ u ¯´ ea. a a e o e. a u o e . . Hˆu hˆt c´c phu.o.ng ph´p t` cˆy bao tr`m tˆi thiˆ’u d` u du.a trˆn nh˜.ng tru.`.ng ho.p ˙e ` ea a´ ´ a ım a uo e ¯ˆ e u o . . - ` u tiˆn, trong sˆ d o l` phu.o.ng ph´p cua Kruskal [39] nhu. sau. ´ e˙ .’ ˙. ’ a˙ ’ d ac biˆt cua thu tuc trˆn. Dˆ ¯ˇ e a e o ¯´ a . 4.4.1 Thuˆt to´n Kruskal a a . Y tu.o.ng cua thuˆt to´n Kruskal t` cˆy bao tr`m trong d` thi liˆn thˆng c´ trong sˆ G ´ ´ ˙ ’ ˙ ’ a a ım a u ¯o . e ˆ o o. o . . sau: Kho.i tao v´.i d` thi T gˆm tˆ t ca c´c d ınh cua G v` khˆng c´ canh. Tai mˆ i bu.´.c ˜ ` ´’ ˙ . o ¯o . ’ o a ˙ a ¯˙ ’ ˙ ’ nhu ˆ ao o. .o o .o.ng nho nhˆ t lˆn cˆy T m` khˆng tao th`nh chu ´ ˙ ’ lˇp ch´ng ta thˆm mˆt canh c´ trong lu . a u e o. o. aea ao a . . . .ng khi T c´ (n − 1) canh. tr` trong T. Thuˆt to´n d` ınh a au o . . 1. [Kho.i tao] Gia su. T l` d` thi gˆm n d ınh v` khˆng c´ canh. a ¯o . ` ˙. ’ ˙˙ ’’ ¯˙’ ˆ o ao o. 2. [Sˇp xˆp] Sˇp xˆp th´. tu. c´c canh cua d` thi G theo th´. tu. trong lu.o.ng tˇng dˆn. ´´ ´´ ` ˙ ¯o . ’ˆ ae ae u.a . u. . a a . 3. [Thˆm canh] Thˆm canh (bˇt d` u t`. canh d` u tiˆn) trong danh s´ch c´c canh d u.o.c ´ˆ e e a ¯a u . ¯ˆa e a a. ¯. . . sˇp xˆp v`o cˆy T sao cho khˆng tao th`nh chu tr` trong T khi thˆm. (Canh d u.o.c ´´ aeaa o a ınh e ¯. . . .o.c). ´ thˆm v`o goi l` chˆ p nhˆn d u . e a .a a a¯ . 4. [Kˆt th´c] Nˆu T c´ (n − 1) canh th` thuˆt to´n d`.ng; T l` cˆy bao tr`m tˆi thiˆ’u. ˙ ´ ´ ´ e u e o ı a au aa u o e . . Thuˆt to´n n`y thˆm v`o cˆy T nh˜.ng canh c´ trong lu.o.ng nho nhˆ t chˆ p nhˆn d u.o.c ´ ´ ˙a ’ a aa e aa u o. a a¯. . . . . .n l` thˆm canh gi˜.a mˆt cˆy con cua T, chˇng han T , v` mˆt cˆy con n`o kh´c (nhu. ˙ ’ ˙ ’ ho a e u oa a aoa a a . . . . s chı ra trong Ph´p to´n I). Hiˆ’n nhiˆn canh d u.o.c chon c´ trong lu.o.ng nho nhˆ t gi˜.a mˆt ˙ ´u ˙’ ˙ ’ e a e e. ¯. .o. a o . . ´ ´ ˙ ’ cˆy con n`o d ´ v` bˆ t k` cˆy con kh´c, nˆn nguyˆn tˇc chon cua thuˆt to´n Kruskal l` mˆt a a ¯o a a y a a e ea a a ao . . . tru.`.ng ho.p d ac biˆt cua Ph´p to´n I. Tuy nhiˆn c´ thˆ’ xay ra tru.`.ng ho.p canh e d u.o.c ˙’ e˙ ’ eoe˙ o . ¯ˇ e a o ¯. . . . . kiˆ’m tra dˆ’ thˆm v`o liˆn thuˆc gi˜.a hai d ınh cua c`ng mˆt cˆy con v` do d o n´ s˜ tao ra ˙ ˙ ¯˙ ’ ˙u ’ e ¯e e ae o u oa a ¯´ o e . . . .c l` canh e l` khˆng chˆ p nhˆn d u.o.c. V` vˆy, trong Bu.´.c 3, ´ ´ mˆt chu tr` nˆu thˆm v`o; t´ a . o ınh e e au ao a a¯. ıa o . . . ` n d u.o.c kiˆ’m tra t´ chˆ p nhˆn cua n´ tru.´.c khi thˆm v`o T. Tiˆn tr` kiˆ’m ˙ ˙ ´ ´ a˙o ’ c´c canh cˆ ¯ . a. a e ınh a o e a e ınh e . .c hiˆn hiˆu qua bˇ ng c´ch su. dung thuˆt to´n xˆy du.ng cˆy bao tr`m tra n`y c´ thˆ’ thu ˙. ˙` ’a ˙. ’ aoe e e a a aa a u . . . . .a trˆn hai mang tuyˆn t´ nhu. d a tr` b`y trong Phˆn 4.3.3. ´ ` ˙ ’ du e e ınh ¯˜ ınh a a . 116
V´ du 4.4.2 X´t d` thi trong H` 4.11(a). Sˇp xˆp c´c canh theo trong lu.o.ng tˇng dˆn ´´ ` ı. e ¯ˆ . o ınh aea. a a . . . dung hai mang tuyˆn t´ α v` β ) ta d u.o.c ´ ˙ ’ ˙ ’ (su . e ınh a ¯. k 1 2 3 4 5 6 7 8 9 α c a e a c a b c d β d c f e f b d e f Trong lu.o.ng 1 2 2 3 3 4 5 6 6 . . ınh) d u.o.c thˆm v`o cˆy T theo th´. tu. l` C´c canh (khˆng tao th`nh chu tr` a. o a ¯. e aa u.a . (c, d), (a, c), (e, f ), (a, e), (a, b). T l` cˆy bao tr`m nho nhˆ t c´ trong lu.o.ng 12 (H` 4.11(b)). ´ ˙ ’ao. aa u ınh . a a 4 4 b b • • • • .................................................................. .................................................................. .................................................................. .................................................................. . . . ... . ... . . ... . ... . . . . . ... . ... . ... . ... . . . . . ... . ... . ... ... . . . . . . . . . ... ... . . ... ... . . . 2 5 2 . . . . . . . . ... ... . ... ... . . . . . . . . ... ... . . . 3 1 3 1 ... ... . . . . . . . . . ... ... . . ... ... . . . . . . . . . ... ... . . . ... ... . • • • • . . ................................................................. .. . ................................................................. . . ... ... .. . ............................................................... ... ... ......... ........................................................... ......... .... . .. . . . . ... ... .... ... ... ... .... .... .... . c c .. . . . . ... .... ... ... .... .... ... ... ... .... d d .... . .... .. .. . . .. .... .. ... .... ... ... ... .... .... ... ... .... .... .. 3 .. .... 6 .... ... ... 6 ... ... ... .... .... ... .... .... ... ... ..... ... ... ..... ... ... .... .... ... .......... ... .......... ... ... .... .... . . . .. ... .... ... ... .. ... .... .... ... .. ... ..... • . • • • .. . .......................................................................................... ...................................................................................... ......................................................................................... ....................................................................................... . ... .. . .. . e e f f 2 2 (a) (b) H` 4.11: ınh Bˆ’ d` 4.4.3 Nˆu Kn = (V, E ) l` d` thi d` y d u , v` nˆu tˆ t ca c c´c trong lu.o.ng cu a c´c ˙e ´ ´´’ a ¯ˆ . ¯ˆ ¯ ˙ a e a ˙ a ’ ˙a ’ o ¯ˆ e o a . . ˙u T = (V, ET ). ’ ı` . ´oa ´ canh kh´c nhau th` tˆn tai duy nhˆ t mˆt cˆy bao tr`m tˆi thiˆ a o a uo e . . Ch´.ng minh. K´ hiˆu Ek := {e1 , e2 , . . . , ek } l` tˆp c´c canh d u.o.c thˆm v`o cˆy T trong u ye aa a . ¯. e aa . . . bu.´.c lˇp th´. k, 1 ≤ k ≤ n − 1. Hiˆ’n nhiˆn theo c´ch xˆy du.ng, T l` d` ˙ ˙ ’ Thuˆt to´n 4.4.1 o a a oa u e e a a a ¯o ˆ . . . ˙ a Kn . ’ thi c´ (n − 1) canh v` khˆng c´ chu tr` nˆn T l` cˆy bao tr`m cu .o ao o ınh e aa u . Gia su. T = (V, ET ) l` cˆy bao tr`m tˆi thiˆ’u, ta ch´.ng minh ET = En−1 . Thˆt vˆy, ˙ ´ ˙˙ ’’ aa u o e u aa .. . ngu.o.c lai tˆn tai chı sˆ k nho nhˆ t sao cho canh e khˆng thuˆc E . Khi d ´ theo `. ´ ´ ˙˙ ’’ ˙o ’ ˙ ’ gia su ..o a o o ¯o . . k T ınh a ˙ a ` . ` . o a ˙ o ´’ ’. t´ chˆ t cua cˆy, tˆn tai tˆn tai mˆt v` chı mˆt chu tr` µ trong T ∪ {ek }. Trˆn chu tr` o o ınh e ınh . .o.c lai tˆn tai mˆt chu tr` n`y c´ mˆt canh e0 m` e0 ∈ En−1 , v` nˆu ngu . . ` . ´ aoo. a / ıe o o ınh, l` µ, trong cˆy a a . . 117
˜ T −mˆu thuˆn. Nˆu d at ET := (ET ∪ {ek }) \ {e0 }) th` d` thi T := (V, ET ) khˆng c´ chu ´. a a e ¯ˇ ı ¯ˆ . o o o tr` v` c´ (n − 1) canh nˆn n´ l` mˆt cˆy. ınh a o e oa o a . . Mˇt kh´c Ek−1 ∪ {e0 } ⊂ ET nˆn Ek−1 ∪ {e0 } khˆng ch´.a chu tr` a a e o u ınh. Suy ra . w(e0 ) > w(ek ). Nhu.ng cˆy T nhˆn d u.o.c t`. cˆy T b` ng c´ch thay canh e0 th`nh canh ek nˆn W (T ) < a a ¯. ua ˇ a a a e . . . ˙u. ’ ˜ ´ W (T ). Mˆu thuˆn v` T l` cˆy bao tr`m tˆi thiˆ a aı aa u o e Dinh l´ 4.4.4 Thuˆt to´n Kruskal l` d ung; t´.c l`, kˆt th´c thuˆt to´n T l` cˆy bao tr`m -. ´u y aa a ¯´ uae aa aa u . . tˆi thiˆ’u. ˙ ´ o e Ch´.ng minh. Thˆt vˆy tru.´.c hˆt ta thu xˆp dˆ’ moi canh d` u c´ d ˆ d`i kh´c nhau; chˇng ˙ ˙ ’ ´ ´ u aa oe e ¯e . . ¯ˆ o ¯o a e a a .. . ´u w(e1 ) = w(e2 ) = · · · = w(es ) th` thu.c hiˆn ph´p biˆn d o’i: ˙ ´ ¯ˆ han nˆ e ı. e e e . . w(e1 ) = w(e1 ) + , w(e2 ) = w(e2 ) + 2 , . . . w(es ) = w(es ) + s , trong d o l` sˆ du.o.ng d u b´ sao cho khˆng l`m d ao lˆn th´. tu. vˆ quan hˆ gi˜.a trong lu.o.ng ´ u.` ¯˙ e ’ a ¯˙ o ’. ¯´ a o o e eu . . . ˙a. ’ cua c´c canh. C˜ng thˆ, ta c˜ng c´ thˆ’ thˆm c´c canh f v´.i trong lu.o.ng d u l´.n w(f ) > ˙ ´ ¯˙ o ’ u e u oee a. o w(e) . . e∈E .o.c K = (V, E ) l` d` y d u. v` kh´c nhau sao cho d` thi nhˆn d u . a ¯ˆ ¯ ˙ ’ aa ¯ˆ . a ¯ o a . n Theo Bˆ’ d` 4.4.3 tˆn tai duy nhˆ t mˆt cˆy bao tr`m tˆi thiˆ’u T trong d` thi Kn . Mˇt ˙e ˙ `. ´oa ´ o ¯ˆ o a uo e ¯o . ˆ a . . .o.ng khˆng vu.o.t qu´ kh´c, moi cˆy bao tr`m cua d` thi G c´ trong lu . ˙ ¯o . ’ˆ a a u o. o a e∈E w(e) v` moi cˆy a.a . . bao tr`m cua G c˜ng l` cˆy bao tr`m cua Kn . Suy ra T l` cˆy bao tr`m tˆi thiˆ’u cua G. ˙˙ ´ ˙ ’ ˙ ’ ’ u u aa u aa u o e Nhˆn x´t rˇ ng, c´ thˆ’ d`ng phu.o.ng ph´p d oi ngˆ u: loai dˆn c´c canh c´ trong lu.o.ng ˙ ae` ˜ ´ .`a. a o eu a ¯ˆ a a o. . . .n nhˆ t cua d` thi m` khˆng l`m mˆ t t´ liˆn thˆng cua n´ cho dˆn khi khˆng thˆ’ loai ˙ ´’ˆ ´ ´ a ˙ ¯o . a o ˙o ’ l´ o a a ınh e o ¯e o e. canh d u.o.c n˜.a. ¯. u . Dˆ ph´.c tap t´ to´n cua thuˆt to´n Kruskal phu thuˆc v`o Bu.´.c 2: d` thi c´ m - o u . ınh a ˙ ’ a a oa o ¯o . o ˆ . . . . ˙ thu.c hiˆn sˇp xˆp mang theo trong lu.o.ng tˇng dˆn. Tuy ’. .´´ ` ` ˙ ’ canh cˆn m log2 m ph´p to´n dˆ a e a ¯e eae a a . . . ` n duyˆt to`n bˆ mang v` cˆy bao tr`m tˆi thiˆ’u gˆm (n − 1) ˙` ´ ˙’ nhiˆn, n´i chung ta khˆng cˆ e o o a e ao ıa u o eo . . canh chˆ p nhˆn d u.o.c nˆn chı cˆn kiˆ’m tra r < m phˆn tu. d` u tiˆn cua mang. Do d o ta c´ ˙ ´ ˙` ` ’a a ˙ ¯a ’ˆ e˙ ’ ˙ ’ a a¯. e e ¯´ o . . ˙ cai tiˆn thuˆt to´n n`y dˆ’ tˇng tˆc d o thu.c hiˆn (xem [14], [36]). ’˙ e ˙a ´ ´ ¯ˆ . thˆ ’ e a a a ¯e o. e . . Mˇc d` c´ nh˜.ng cai tiˆn, nhu.ng thuˆt to´n Kruskal chı th´ ho.p v´.i nh˜.ng d` thi ’´ ˙e ˙ ıch . ’ a uo u a a o u ¯ˆ . o . . .o.ng d ˆi thu.a. V´.i nh˜.ng d` thi kh´c, chˇng han d` thi d` y d u c´ sˆ canh m = n(n − 1)/2, ˙ ’ ´ ´ . ¯o . ¯ˆ ¯ ˙ o o . ’ tu ¯o o u ¯ˆ . a o a ˆ a 118
Prim [49] v` Dijkstra [20] d ˜ d u.a ra nh˜.ng thuˆt to´n kh´c du.a trˆn viˆc d ˇc biˆt ho´ hiˆu a ¯a ¯ u a a a. e e ¯a e ae . . . . . qua ho.n Ph´p to´n I. ˙ ’ e a 4.4.2 Thuˆt to´n Prim a a . Thuˆt to´n n`y xˆy du.ng cˆy T bˇ ng c´ch liˆn tiˆp thˆm c´c canh c´ trong lu.o.ng nho nhˆ t ` ´ ´ ˙a ’ a aaa a a a ee e a. o. . . . .o.c h` th`nh v` mˆt d ınh khˆng thuˆc cˆy n`y cho o ¯˙ .’ a o ¯˙ .’ liˆn thuˆc mˆt d ınh trong cˆy d ang d u . ınh a e o a¯ ¯ o oaa . . .o.c cˆy bao tr`m tˆi thiˆ’u. Trong mˆi bu.´.c lˇp, qu´ tr` thˆm canh n`y ˙ ˜ ´ ´ dˆn khi nhˆn d u . a ¯e a¯ u o e o oa a ınh e a . . . e ˙ ¯˙ ’ ’ s˜ bao d am khˆng tao th`nh chu tr` trong T. o a ınh . Ch´ng ta minh hoa thuˆt to´n bˇ ng c´ch su. dung “ma trˆn trong lu.o.ng” W = ` ˙. ’ u a a a a a . . . . . (wij )n×n , trong d o ¯´  ´ 0 nˆu i = j, e  ´ `.. wij =  +∞ nˆu khˆng tˆn tai canh (vi , vj ), e o o  e`.. ´o w(vi , vj ) nˆu tˆn tai canh (vi , vj ). Kho.i d` u t`. d ınh v1 v` nˆi n´ dˆn mˆt d ınh kˆ gˆn nhˆ t (t´.c l` d ınh m` c´ phˆn tu. ´ ´ `` ´ ao ` ˙ ¯ˆ u ¯˙ ’a ’ o ¯˙ .’ a u a ¯˙ ’ a˙ ’ a o o ¯e ea ˙ nhˆ t trong h`ng th´. nhˆ t trong ma trˆn W ), gia su. l` vk . Bˆy gi`. khao s´t v1 v` vk ´ ´ ’ ˙˙a ’’ ˙a ’ nho a a u a a a o a . nhu. mˆt d` thi con, v` nˆi d` thi con n`y v´.i mˆt d ınh kˆ v´.i n´ v` gˆn nhˆ t (t´.c l` d ınh ´ˆ ` o oa` ´ a o o ¯˙ ’ a u a ¯˙ ’ o ¯ˆ .o a o ¯o . e a . . . nho nhˆ t trong tˆ t ca c´c phˆn tu. cua h`ng th´. nhˆ t v` th´. ao ` ´ ´’ ` ´ a˙ ’ ˙ ’a a ˙a a˙˙a ’’ kh´c v1 v` vk m` c´ phˆn tu a a uaau ˙ su. d ınh m´.i l` vi . Kˆ tiˆp, xem cˆy v´.i c´c d ınh v1 , vk , vi nhu. mˆt d` thi ´e ´ ’ ˙ ¯˙ ’’ ˙ ’ k trong W ). Gia oa e a o a¯ o ¯ˆ . .o con, v` tiˆp tuc xu. l´ cho dˆn khi tˆ t ca n d ınh d u.o.c nˆi bo.i (n − 1) canh. ´ ´ ´’ ´’ ˙y ’ a ˙ ¯˙ ¯ . o ˙ ’ ae . ¯e . Tˆ’ng qu´t ta c´ thuˆt to´n d u.o.c tr` b`y nhu. sau: ˙ o a o a a¯. ınh a . 1. [Kho.i tao] Gia su. T l` d` thi chı c´ mˆt d ınh v1 v` khˆng c´ canh. ˙. ’ ˙˙ ’’ a ¯o . ˙ o o ¯˙ ’ .’ ˆ ao o. 2. [Kˆt th´c] Nˆu T c´ (n − 1) canh th` thuˆt to´n d`.ng; T l` cˆy bao tr`m tˆi thiˆ’u.˙ ´ ´ ´ e u e o ı a au aa u o e . . 3. [Thˆm canh] Trong sˆ tˆ t ca c´c canh khˆng thuˆc cˆy T m` liˆn thuˆc v´.i mˆt d ınh ´´ ’ oa ˙a . o o o ¯˙.’ e o oa ae . . . .o.ng nho ˙ ’ trong T v` khˆng tao th`nh chu tr` khi thˆm v`o T, chon canh c´ trong lu . ao a ınh e a o. . . . .´.c 2. nhˆ t v` thˆm n´ v` d ınh n´ liˆn thuˆc v`o cˆy T. Chuyˆ’n sang Bu o ˙ ´ o a ¯˙ ’ aae oe oaa e . V´ du 4.4.5 Ap dung Thuˆt to´n Prim cho d` thi trong H` 4.12(a) v´.i d ınh xuˆ t ph´t ´ ´ o ¯˙ ’ ı. a a ¯ˆ . o ınh a a . . .o.c lˆn lu.o.t thˆm v`o cˆy T theo th´. tu. l` ` l` v1 ta c´ c´c canh d u . a a oa . ¯ e aa u.a . (v1 , v5 ), (v1 , v4 ), (v4 , v2 ), (v2 , v3 ), (v2 , v6 ). Cˆy bao tr`m nho nhˆ t c´ trong lu.o.ng 12 (H` 4.12(b)). ´ ˙ ’ao. a u ınh . 119
v1 v1 ..•.. • .... .... .... .... . ... . ... ... .... . ... .... ... . ... . ... . .. ... ... ... ... . . ..... . . ... ... ... ... ... ... ... . ... . ... . .. . ... ... ... ... ... . 4................... 2 4 2 ... . ... ... ... . ... ... . ... . ... . ... ... ... . ... ... . . ... ... . ... ... . ... ... . . . . ... ... . . ... . . ... ... ... . ... ... . v4 • • v5 v4 • • v5 ... ... ... . .. . . 9 ... ... . .... ... . . . . ... .... . .. . . ... . ... ... . ... ..... ... ..... ... ... ..... . . . . ... ... ... . ... ... ... . ... ... ... . ... . . . ... ... ... . ... ... ... ... . ... ... ... . . . .. . . .. . ... ... ... ... ... ... ... 3 6 5 7 3 ... . ... ... . ... ... ... ... . ... ... ... ... ... . ... . ... . . ... ... ... ... ... . ... . ..... ... ... ... . ... ... . ... . ... ... ... ... . ... ... ... ... . ... ... ... . . ... ... . ... ... ....... ...... .. • • • • • • .. .......................................................................................... ........................................................................................... .............................................. ............................................. . .. . . . .. . .. .. .. .. .. .. .. .. .. .. .. .. ... .. .. v2 v6 v3 v2 v6 v3 ... ... ... ... ... ... ... 2 8 2 ... . ... ... ... ... ... ... ... ... ... ... ... ... .. .. . . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ..... ..... ..... ..... .... .... ... ... ....... ....... ....... ....... ............................. ............................. ............................ ............................ 1 1 (a) (b) H` 4.12: (a) D` thi G. (b) Cˆy bao tr`m nho nhˆ t cua G sinh bo.i Thuˆt to´n Prim. -ˆ . ´’ ˙ ’a˙ ˙ ’ ınh o a u a a . aoı.˙ ’ Thuˆt to´n Prim l` mˆt v´ du cua thuˆt to´n tham lam (greedy algorithm). Thuˆt a a a a a . . . . to´n tham lam l` thuˆt to´n chon lu.a tˆi u.u tai mˆ i bu.´.c lˇp m` khˆng quan tˆm dˆn ˜ ´ ´ a a a a o o oa ao a ¯e . .. . . su. chon lu.a o. bu.´.c tru.´.c. C´ thˆ’ n´i nguyˆn l´ n`y l` “thu.c hiˆn tˆt nhˆ t vˆ mˇt d .a ˙ ´ a ` a ¯i ´e. ˙ ’ o o o eo eyaa eo . .. . . .o.ng”. Trong thuˆt to´n Prim, v` ch´ng ta muˆn t` cˆy bao tr`m tˆi thiˆ’u nˆn tai mˆi ˙ ˜ ´ ım a ´ phu a a ıu o uo ee.o . .´.c lˇp ch´ng ta thˆm mˆt canh c´ trong lu.o.ng nho nhˆ t (nˆu viˆc thˆm khˆng tao th`nh ´ ´ ˙a ’ bu o a u e o. o. e e e o a . . . . . chu tr` ınh). Tˆi u.u ho´ tai mˆi bu.´.c lˇp khˆng nhˆ t thiˆt cho l`.i giai tˆi u.u cua b`i to´n gˆc. ˜ ´ ´ ´ ’´ ´ ˙o ˙ ’a o a. o oa o a e o ao . .o.c ch´.ng minh trong Dinh l´ 4.4.6. Mˆt v´ du -. ´ ˙ ’ T´ d ung d an cua thuˆt to´n Prim s˜ d u . ınh ¯´ ¯ˇ a a e¯ u y oı. . . ˙ a thuˆt to´n tham lam nhu.ng khˆng d u.a dˆn l`.i giai tˆi u.u nhu. sau: x´t “thuˆt to´n t` ´o ’´ ’ ˙o cu a a o ¯ ¯e e a a ım . . d u.`.ng d i ngˇn nhˆ t” trong d ´, mˆ i bu.´.c lˇp ch´ng ta chon canh c´ trong lu.o.ng nho nhˆ t ´ ˜ ´ ´ ˙ ’a ¯o ¯ a a ¯o o oa u o. . . . . .i d ınh d u.o.c thˆm v`o gˆn d ˆy a ` ¯a (m` khˆng tao th`nh chu tr` khi thˆm v`o) liˆn thuˆc v´ ¯˙ o o ’ ¯. ao a ınh e a e e a . . ´t. Nˆu ta ´p dung thuˆt to´n n`y v´.i d` thi c´ hu.´.ng trong H` 4.13 dˆ’ t` d u.`.ng d i ˙ ım ¯ o ´ nhˆ a e a a a a o ¯ˆ . o oo ınh ¯e ¯ . . ngˇn nhˆ t t`. v1 dˆn v4 , ch´ng ta s˜ chon cung (v1 , v3 ) v` sau d o cung (v3 , v4 ). Tuy nhiˆn, ´ ´ ´ a au ¯e u e. a ¯´ e d ay khˆng phai l` d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v4 . ´ ´ ´ ˙ a¯ o ’ ¯ˆ o ¯ a au ¯e v2 • ... ........ .... ..... . .... . ....... .... . ....... . 2 4 .... .... . .... .... .... . .... . .... .... .... . .... . .... .... . .. . . .... .... .... .... . . .. . .... .... .... . .... . . .... .. .... . .... . .... . .... .... . .. . . .... .... .... .... . . v1 • • v4 .. .... . .... .... . .... 8 . . . . ... .... ... .... . . . .. .... .... . .... . .... .... .... . .... . .. . .... .... . .... .... . .... . ... . .... .... . .... .... . .... . .... .... .... . .... . .... . .... .... .... . .... . .... .... . .... .... . .... 1 6 .... . .... . .... . ...... . .... .... . ....... . • ......... ..... . . v3 H` 4.13: ınh Dinh l´ sau ch´.ng minh t´ d ung d an cua thuˆt to´n Prim. -. ´˙ ’ y u ınh ¯´ ¯ˇ a a . 120
Dinh l´ 4.4.6 Thuˆt to´n Prim l` d ung; t´.c l`, kˆt th´c thuˆt to´n T l` cˆy bao tr`m tˆi -. ´u ´ y aa a ¯´ uae aa aa uo . . thiˆ’u. ˙ e Ch´.ng minh. Trong ch´.ng minh n`y ch´ng ta s˜ d ac tru.ng cˆy bo.i mang c´c canh cua n´. ˙ ’ ˙ ’ ˙o ’ u u a u e ¯ˇ a a. . Theo c´ch xˆy du.ng, kˆt th´c Thuˆt to´n Prim, T l` d` thi con liˆn thˆng khˆng chu ´ a a e u a a a ¯o . ˆ e o o . . ` thi G v` ch´.a tˆ t ca c´c d ınh cua G; do d ´ T l` cˆy bao tr`m cua G. ´ ˙ a ¯˙ ınh ˙ ¯ˆ ’ aua’ ’ ˙ ’ ˙ ’ tr` cua d o . ¯o aa u Dˆ’ chı ra T l` cˆy bao tr`m tˆi thiˆ’u, ch´ng ta ch´.ng minh bˇ ng quy nap rˇ ng o. bu.´.c -e ˙ ˙’ ˙ ` ` ´ .a˙ ’ aa uo e u u a o . k cua Thuˆt to´n Prim, T d u.o.c ch´.a trong mˆt cˆy bao tr`m tˆi thiˆ’u. V` do d ´, kˆt ˙ ´ ´ ˙ ’ th´u a a ¯. u oa u o e a ¯o e . . ´i thiˆ’u. K´ hiˆu Tk l` cˆy d u.o.c tao ra o. bu.´.c lˇp th´. ˙ ˙ ’ th´c thuˆt to´n T l` cˆy bao tr`m tˆ u a a aa u o e ye aa¯. . oa u . . . k. Nˆu k = 1 th` T1 gˆm mˆt d ınh v` do d ´ d u.o.c ch´.a trong moi cˆy bao tr`m tˆi thiˆ’u. ˙ ´ ` ´ o ¯˙ .’ e ı o a ¯o ¯ . u .a uo e ˙ ’ Khˇng d .nh d ung. a ¯i ¯´ Gia su. rˇ ng o. bu.´.c th´. (k − 1) cua Thuˆt to´n Prim, cˆy Tk−1 ch´.a trong cˆy bao ˙˙` ’’a ˙ ’ ˙ ’ o u a a a u a . ´i thiˆ’u T . K´ hiˆu Vk−1 l` tˆp c´c d ınh cua Tk−1 . Theo Thuˆt to´n Prim, canh ˙ ˙ ’ ˙ ’ tr`m tˆ u o e ye aa a¯ a a . . . . e = (vi , vj ) c´ trong lu.o.ng nho nhˆ t v´.i vi ∈ Vk−1 v` vj ∈ Vk−1 d u.o.c thˆm v`o Tk−1 dˆ’ tao ˙ ´ ˙ ’ao o. a / ¯. e a ¯e . . ra Tk . Nˆu e ∈ T th` Tk ch´.a trong cˆy bao tr`m tˆi thiˆ’u T . Nˆu e ∈ T th` T ∪ {e} ch´.a ˙ ´ ´ ´ e ı u a uo e e / ı u mˆt chu tr` µ. Chon canh (vx , vy ) = e trˆn chu tr` µ sao cho vx ∈ Vk−1 v` vy ∈ Vk−1 . o ınh e ınh a / . . . Ta c´ o w(x, y ) ≥ w(i, j ). Suy ra d` thi T ” := [T ∪ {e}] − {(vx , vy )} c´ trong lu.o.ng nho ho.n hoˇc bˇ ng trong lu.o.ng a` ˙ ’ ¯o . ˆ o. .a . . . ˙u. Do d o ta c´ d iˆu cˆn ch´.ng ’ ´ o ¯` ` ˙ ’ cua T . V` T ” l` cˆy bao tr`m nˆn T ” l` cˆy bao tr`m tˆi thiˆ ı aa u e aa uo e ¯´ ea u minh. Thuˆt to´n Prim cˆn kiˆ’m tra O(n3 ) canh trong tru.`.ng ho.p xˆ u nhˆ t (b`i tˆp) dˆ’ ˙ ˙ ` ´ ´ a a a e o a a a a ¯e . . . . ´i thiˆ’u trong d` thi n d ınh. Ch´ng ta c´ thˆ’ chı ra Thuˆt to´n ˙ ˙˙ ¯ˆ . ¯˙ ’ oe’ x´c d .nh cˆy bao tr`m tˆ a ¯i a u o e o u a a . 4.4.3 du.´.i d ay chı cˆn kiˆ’m tra O(n2 ) canh trong tru.`.ng ho.p xˆ u nhˆ t. V` Kn c´ n2 canh ˙ ˙` ´ ´ ’a o ¯ˆ e o a a ı o . . . nˆn thuˆt to´n sau hiˆu qua ho.n. ˙ ’ e a a e . . 4.4.3 Thuˆt to´n Dijkstra-Kevin-Whitney a a . Thuˆt to´n du.´.i d ay t` cˆy bao tr`m tˆi thiˆ’u trong d` thi liˆn thˆng c´ trong sˆ hiˆu ˙ ´ ´. a a o ¯ˆ ım a u o e ¯o . e ˆ o o. oe . .n phu.o.ng ph´p cua Prim. Phu.o.ng ph´p sau n`y d u.a ra bo.i Dijkstra [20], v` bo.i ˙ ’ ˙ ’ ˙ ’ a˙ ’ qua ho a a a¯ Kevin v` Whitney [41]. a Y tu.o.ng cua thuˆt to´n l` g´n mˆ i d ınh vj ∈ Ts mˆt nh˜n (αj , βj ), trong d o o. bu.´.c ´ ˜’ ˙ ’ ˙ ’ o ¯˙ ¯´ ˙ ’ a a aa / o a o . . .i d ınh v nhˆ t v` β l` d o d`i canh (α , v ). Tai mˆ i bu.´.c ˜ `o’ ´ n`o d o αj l` d ınh thuˆc Ts gˆn v´ ¯˙ a ¯˙’ a ¯´ o a a a j a ¯ˆ a . .o o . . j jj 121
trong suˆt qu´ tr` thu.c hiˆn thuˆt to´n, mˆt d ınh m´.i, chˇng han vj ∗ , v´.i gi´ tri βj nho ˙ ’ ´ o ¯˙ .’ ˙’ o a ınh . e a a o a o a. . . . .o.c thˆm c`ng v´.i canh (α ∗ , v ∗ ) v`o cˆy T . V` cˆy T d u.o.c thˆm d ınh v ∗ nˆn c´c ´ e ¯˙ ’ nhˆ t d u . a¯ e u o. a a s ı a s¯ . ea j j j nh˜n (αj , βj ) cua c´c d ınh vj ∈ Ts cˆn d u.o.c cˆp nhˆt lai (nˆu, chˇng han, w(vj , vj ∗ ) nho ˙ ’ ` ¯. a ´ ˙ a ¯˙ ’ ’ ˙’ a / a a. e a . . . .n nh˜n tru.´.c d o β ), v` tiˆn tr` d u.o.c xu. l´ tiˆp tuc. Thu tuc g´n nh˜n n`y tu.o.ng tu. ´ ´ ˙ye . ’ ˙. a ’ ho a o ¯´ j ae ınh ¯ . aa . v´.i thu tuc g´n nh˜n cua thuˆt to´n Dijkstra t` d u.`.ng d i ngˇn nhˆ t. ´ ´ ˙. a ’ a˙ ’ o a a ım ¯ o ¯ a a . Thuˆt to´n nhu. sau: a a . 1. [Kho.i tao] Dˇt Ts := {s}, trong d ´ s l` d ınh d u.o.c chon tu` y, v` As = ∅. (As l` tˆp ˙ . -a ’ ¯o a ¯ ˙ ’ ¯. y´ a aa . . . ˙ a cˆy bao tr`m nho nhˆ t d u.o.c tao ra trong qu´ tr` lˇp). ´ ’a ˙ ’ a¯. . c´c canh cu a. u a ınh a . 2. [G´n nh˜n] V´.i moi d ınh vj ∈ Ts t` d ınh αj ∈ Ts sao cho . ¯˙ ’ ım ¯˙ ’ a a o / w(αj , vj ) = min{w(vi , vj ) | vi ∈ Ts } = βj a ˙ ¯˙ ’’ v` g´n nh˜n cua d ınh vj l` (αj , βj ). aa a Nˆu khˆng tˆn tai d ınh αj , t´.c l` Γ(vj ) ∩ Ts = ∅ th` d at nh˜n cua vj l` (0, +∞). ´ ` . ¯˙ ’ a˙ ’ e o o ua ı ¯ˇ a . . ¯˙ ’ 3. [Thˆm canh] Chon d ınh vj ∗ sao cho e . βj ∗ = min{βj | vj ∈ Ts }. / Cˆp nhˆt Ts := Ts ∪ {vj ∗ }, As := As ∪ {(αj ∗ , vj ∗ )}. a a . . Nˆu #Ts = n thuˆt to´n d`.ng; c´c canh trong As cho cˆy bao tr`m nho nhˆ t. Ngu.o.c ´ ´ ˙a ’ e a au a. a u . . ˙n sang Bu.´.c 4. ’ lai, chuyˆe o . 4. [Cˆp nhˆt nh˜n] V´.i moi vj ∈ Ts v` vj ∈ Γ(vj ∗ ) cˆp nhˆt c´c nh˜n nhu. sau: a a a o / a a aa a . . . . . Nˆu βj > w(vj ∗ , vj ) th` d ˇt βj = w(vj ∗ , vj ), αj = vj ∗ . Chuyˆ’n sang Bu.´.c 3. ˙ ´ e ı ¯a e o . 4.5 B`i to´n Steiner a a Trong phˆn tru.´.c ch´ng ta d ˜ x´t b`i to´n t` cˆy bao tr`m nho nhˆ t. Mˆt b`i to´n c´ ` ´ ˙ ’ a o u ¯a e a a ım a u a oa ao . .i t` cˆy bao tr`m nho nhˆ t nhu.ng kh´ ho.n nhiˆu l` “b`i to´n Steiner trong ´ `aaa ˙’a liˆn quan v´ ım a e o u o e c´c d` thi” [21]. Trong b`i to´n Steiner, cˆy bao tr`m nho nhˆ t T d oi hoi d i qua mˆt tˆp ´ ˙ ’a ¯` ˙ ¯’ a ¯o . ˆ aa a u oa .. .´.c cua d` thi G. C´c d ınh kh´c (thuˆc V \ P ) c´ thˆ’ thuˆc hoˇc khˆng ˙ con P ⊂ V cho tru o ˙ ¯o . ’ˆ a ¯˙’ a o oe o a o . . . .i d iˆu kiˆn cu.c tiˆ’u trong lu.o.ng cua cˆy T. Do d o, b`i to´n Steiner trˆn d` ˙ ` ˙a ’ thuˆc cˆy v´ ¯ e oao e e ¯´ a a e ¯ˆ o . . . . . thi tu.o.ng d u.o.ng v´.i t` cˆy bao tr`m nho nhˆ t trong d` thi con G = (V , Γ ) cua G v´.i ´ ˙’a ˙’ ¯ o ım a u ¯ˆ . o o . P ⊆ V ⊆ V. Thˆt ra, b`i to´n Steiner d u.o.c ph´t biˆ’u o. dang nguyˆn thuy l` mˆt b`i to´n h` ˙’ e˙. ˙a o a ’ a a a ¯. a e a ınh . . ˙m trˆn mˇt phˇng d u.o.c nˆi v´.i nhau bˇ ng c´c d oan thˇng ’ ˙ ’ ` ˙ ’ ´ hoc [15], trong d ´ tˆp P c´c d iˆ ¯o a a ¯e e a a ¯. o o a a ¯. a . . . 122
sao cho tˆ’ng c´c d oan thˇng d u.o.c v˜ l` ´ nhˆ t. Nˆu gia thiˆt hai d oan thˇng chı c´ thˆ’ ˙ ˙ ˙ ’ ˙ ’ ´ ´ ´ ˙ ’ ˙o e ’ o a ¯. a ¯ . e a ıt a e e ¯. a . th`nh t` cˆy bao tr`m nho nhˆ t cua d` thi ´ ´’ˆ . a ¯˙ ’ ˙ ’ ˙ ’ ˙ ’ a ˙ ¯o . cˇt nhau tai c´c d ınh cua P th` b`i to´n tro a a ıa a ım a u .o.ng d u.o.ng c´ #P d ınh v´.i ma trˆn trong lu.o.ng x´c d inh bo.i ma trˆn khoang c´ch gi˜.a ¯˙ ’ ˙ ’ ˙ ’ tu ¯ o o a a ¯. a a u . . . ˙m thuˆc tˆp P. Tuy nhiˆn, khi c´c “d ınh nhˆn tao” kh´c (goi l` c´c d iˆ’m Steiner) ’ ˙ ˙’ c´c d iˆ a ¯e oa e a¯ a. a . a a ¯e .. d u.o.c tao thˆm trˆn mˇt phˇng th` trong lu.o.ng cua cˆy bao tr`m nho nhˆ t tu.o.ng u.ng tˆp ˙ ’ ´ ˙a ’ ˙ ’a ¯. . e e a a ı. u ´ a . . . .i P ⊃ P s˜ c´ thˆ’ giam d i. Chˇng han, x´t bˆn d iˆ’m trong H` 4.14(a) v´.i cˆy ˙˙¯ ˙ ˙ ’ ´ ¯˙’ eo e ’ d ınh m´ o a e o ¯e ınh oa . bao tr`m nho nhˆ t T ; tuy nhiˆn khi thˆm hai d iˆ’m m´.i s1 v` s2 ta d u.o.c cˆy bao tr`m nho ˙ ´ ˙a ’ ˙ ’ u e e ¯e o a ¯. a u .i T qua s´u d ınh c´ trong lu.o.ng nho ho.n cˆy T (xem H` 4.14(b)). Do d ´ trong ´o a ¯˙’ ˙ ’ nhˆ t m´ a o. a ınh ¯o . ´c, nhiˆu d iˆ’m Steiner d u.o.c thˆm v`o trong mˇt phˇng dˆ’ tao ra cˆy bao ˙ ˙. ˙ ’ ` ¯e b`i to´n Steiner gˆ aa o e ¯. e a a a ¯e a . tr`m nho nhˆ t qua nh˜.ng d ınh cho tru.´.c P. Kˆt qua d u.o.c d` thi goi l` cˆy Steiner nho ´ ´ ˙ ’ ¯˙’ ˙ ¯ . ¯o . . a a ’ ˙ ’ u a u o e ˆ ´ nhˆ t. a P3 P3 • (4, 4) • .... .. .... .. . ....... . ....... . ....... ....... . .. .. . ....... ....... . . .. . ....... ....... . . . .. ....... ....... .. . . .... P1 P1 ... . ....... ....... .. . . . ... ... .. . ....... ....... .. . . ... ... . .. ....... (0, 3) • ....... •...... .. . . . .. ... . . .. .. . . . . . .. . . .. . . . . 1200 1200 . . .. .. . . . .. . . .. . . . .. . . .. .. . . .. . . .. . . ...... ....... . . ........ .. ...... . .. . .. .... ... . . . .. . . ..................................... . . ........................................... • • .. . . . . . . . . . ....... .. . . . .. . . .. . . .. . . . s1 s2 .. . . .. .. . . .. . . .. . . .. . . .. . . . . . .. .. .. . . .. . . . . .. . .. . . .. .. . .. .. . ... . . . .. . ... .. . . .. .. . .. .. . . .. . (0, 1) • • . . . . . . .. . . . .. . . . . . . . . . . .. . . . .. . . . . . . . .. P2 P2 . . . .. . . . . . . .. . . . .. . . . . . . . .. . . . .. . . . . . . .. . . . .. . . . . . . . . .. . . .. . • (4, 0) • . . . . . . . . . . . . . P4 P4 C´c d iˆ’m ˙ a ¯e Steiner H` 4.14: (a) Cˆy bao tr`m nho nhˆ t c´ trong lu.o.ng bˇ ng 10.123. (b) Cˆy Steiner nho ` ´ ˙ ’ ˙ ’ ınh a u ao. a a . .o.ng 9.196. ´ nhˆ t c´ trong lu . ao. C´ rˆ t nhiˆu cˆng tr` nghiˆn c´.u xung quanh b`i to´n Steiner trˆn mˇt phˇng ˙ ’ ´ ` oa eo ınh eu a a e a a . .o.c ph´t hiˆn. Trong sˆ d ´, c´c t´ a ` ınh a ˙ a ´’ ´ ´ ˙ a¯ ’ Euclide, v` nhiˆu t´ chˆ t cua cˆy Steiner nho nhˆ t d u . e ae o ¯o a ınh . .ng minh c´c t´ chˆ t n`y c´ thˆ’ xem [28]): ˙ ´ ´ ´ chˆ t sau l` quan trong nhˆ t (ch´ a a a u a ınh a a o e . 1. Dˆi v´.i d iˆ’m Steiner si c´ bˆc d(si ) = 3. Bˇ ng h` hoc dˆ d`ng chı ra rˇ ng g´c liˆn -o o ¯e ˙ ` ınh . ˜ a ` ´ ˙ ’ oa a e a oe . .a c´c d iˆ’m Steiner bˆc ba bˇ ng 1200 , v` c´ d ung ba canh liˆn thuˆc v´.i d iˆ’m ˙ ˙ ` thuˆc gi˜ a ¯ e ou a a a o ¯´ e o o ¯e . . . . ˙m n`y l` “tˆm” (tˆm Steiner) cua “tam gi´c ao” m` ba d ınh cua ’ ˙’ ˙ ’ ˙ ’ ˙ ’ Steiner si . Do d ´ d iˆ ¯o ¯ e aaa a a a ¯ .o.c nˆi v´.i d ınh s trong cˆy bao Steiner nho nhˆ t. ´ ´ tam gi´c kh´c nhau d u . o o ¯˙ ’ ˙ ’a a a ¯ a i Mˆt sˆ d iˆ’m tao th`nh c´c d ınh cua tam gi´c n`y c´ thˆ’ l` c´c d iˆ’m Steiner kh´c. .´˙ ˙ ˙ a ¯˙ ’ ˙ ’ o o ¯e a a a o e a a ¯e a . ˙ ng han, trong H` 4.14, d iˆ’m Steiner s2 l` tˆm Steiner cua tam gi´c ao v´.i c´c ˙ ’ ˙’ a˙ oa ’ Chˇ a ınh ¯e aa . ¯˙’ d ınh l` P3 , P4 v` s1 . a a 2. V´.i d ınh Pi ∈ P n`o d ´ m` d(Pi ) ≤ 3. Nˆu d(Pi ) = 3 th` g´c gi˜.a hai canh bˆ t k` ´ ´ o ¯˙ ’ a ¯o a e ıo u ay . 123
trong ba canh liˆn thuˆc v´.i Pi bˇ ng 1200 , v` d(Pi ) = 2 th` g´c gi˜.a hai canh liˆn ` e oo a a ıo u e . . . .n ho.n hoˇc bˇ ng 1200 . a` thuˆc Pi l´ o o a . . 3. Sˆ k c´c d iˆ’m Steiner trong cˆy bao tr`m nho nhˆ t Steiner thoa r`ng buˆc 0 ≤ k ≤ ˙ ´ ´ ˙ ’a ˙a ’ o a ¯e a u o . n − 2, trong d ´ n = #P. ¯o e ´´ ˙’ a uo ` oa ´ ˙ ’ Mˇc d` c´ nhiˆu cˆ gˇng trong viˆc giai quyˆt b`i to´n Steiner trˆn mˇt phˇng Euclide, e eaa e a a . . . .ng ch´ng ta chı m´.i thu d u.o.c nh˜.ng kˆt qua rˆ t han chˆ (trong tru.`.ng ho.p #P ≤ 10). ´ ’´ ´ ˙o ’ ˙a . nhu u ¯. u e e o . V´.i nh˜.ng b`i to´n c´ k´ thu.´.c l´.n ta cˆn d`ng phu.o.ng ph´p heuristics. ` o u a a o ıch oo au a Mˆt dang kh´c cua b`i to´n Steiner su. dung khoang c´ch b`n c`. thay cho khoang c´ch a˙aa ’ ˙. ’ ˙ ’ ˙ ’ o. a ao a . Euclide. B`i to´n n`y d u.o.c x´t lˆn d` u tiˆn bo.i Hanan [32] v` c´ liˆn quan v´.i c´c d u.`.ng a a a ¯ . e ` ¯a ˙ ’ aˆ e aoe o a ¯o dˆn d u.o.c in trˆn c´c bang mach d iˆn tu.. Nhˇc lai rˇ ng, khoang c´ch b`n c`. cua hai d iˆ’m˙ ˜ a.` ´ ea˙ ’ . ¯e ˙ ’ ˙’ ao˙ ’ a ¯. a a ¯e . .i ˙ ’ 2 ˙ ’ (x1 , y1 ) v` (x2 , y2 ) trong mˇt phˇng R x´c d .nh bo a a a a ¯i . d1,2 := |x1 − x2 | + |y1 − y2 |. V´.i c´c d iˆu kiˆn n`y, c´ thˆ’ ch´.ng minh rˇ ng nˆu ke mˆt lu.´.i c´c d u.`.ng thˇng nˇ m ngang ˙ ` ˙ ’ ` o a ¯` ´’. e˙o e eaoeu a o a ¯o a a . .ng d i qua c´c d iˆ’m cua tˆp P th` l`.i giai cua b`i to´n Steiner c´ thˆ’ x´c d inh bˇ ng ˙ ˙ ` ˙a ’. ˙˙aa ’’ v` d u a ¯´ ¯ a ¯e ıo o e a ¯. a .´.i n`y. c´ch xem vi tr´ c´c d iˆ’m Steiner thuˆc v`o c´c giao d iˆ’m cua lu o a ˙ ˙ ˙ ’ a . ı a ¯e oaa ¯e . Do d o, nˆu d` thi G d u.o.c x´c d .nh bo.i tˆp d ınh V l` c´c giao d iˆ’m cua lu.´.i v` mˆt ˙ ´o ˙ a ¯˙ ’. ’ ˙ ’ ¯´ e ¯ˆ . ¯ . a ¯i aa ¯e oao . .o.ng u.ng d oan thˇng thuˆc lu.´.i nˆi hai giao d iˆ’m. Khi d ´ b`i ˙ ˙ ’ ´ ¯˙’ canh liˆn thuˆc hai d ınh tu e o ´ ¯. a o oo ¯e ¯o a . . . to´n Steiner trˆn mˇt phˇng v´.i khoang c´ch b`n c`. tro. th`nh b`i to´n Steiner trˆn d` thi ˙ ’ ˙ ’ ao˙a ’ a e a a o a aa e ¯o . ˆ . h˜.u han G. H` 4.15(b) minh hoa v´ du cua cˆy Steiner nho nhˆ t trong b`i to´n Steiner ´ ı.˙ a ’ ˙ ’a u ınh a a . . 6 d iˆ’m v´.i khoang c´ch b`n c`. v` H` 4.15(a) l` cˆy bao tr`m nho nhˆ t cua d` thi x´c ˙ ´’o ˙ ’ ˙ ’ a ˙ ¯ˆ . a ¯e o a a o a ınh aa u ˙.i 6 d iˆ’m (dˆ’ d o.n gian lu.´.i khˆng d u.o.c v˜ ra). ˙ ˙¯ ’ ˙ ’ d .nh bo ¯i ¯e ¯e o o ¯. e B`i to´n Steiner trˆn d` thi vˆ hu.´.ng tˆ’ng qu´t d u.o.c nghiˆn c´.u bo.i nhiˆu t´c gia ˙ `a ˙ ’ ˙ ’ a a e ¯ˆ . o o o o a¯. eu e .ng thuˆt to´n (khˆng hiˆu qua vˆ mˇt t´ to´n) giai quyˆt ch´ng. Tuy nhiˆn ˙ ` a ınh a ´ ’e . ˙ ’ v` d ˜ c´ nh˜ a ¯a o u a a o e e u e . . (nhu. trong tru.`.ng ho.p b`i to´n Steiner v´.i khoang c´ch Euclide), k´ thu.´.c l´.n nhˆ t cua ´’ ˙ ’ a˙ o aa o a ıch oo . mˆt b`i to´n Steiner trˆn d` thi c´ thˆ’ giai trˆn m´y t´ d iˆn tu. v´.i th`.i gian cho ph´p ˙’ e ¯o . o e ˙ e a ınh ¯ e ˙ o ’ oa a ˆ o e . . ˜n khˆng vu.o.t qu´ 10 d ınh (trong P ). N´i c´ch kh´c, b`i to´n Steiner trˆn d` thi c˜ng c´ ˙ ’ vˆ a o a ¯ oa a aa e ¯ˆ . u o o . thˆ’ xem l` b`i to´n chu.a c´ l`.i giai. ˙ ˙ ’ e aa a oo 124
P1 P1 • • 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • P3 • P3 . . 5 . ...................................................... . .................................................... . . . ................................... .................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • P2 . . . 4 .................................... . . ................. ................. . . . . . . . . . . . . . P2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 . . . . . . . . . . . . . . . . . . . . . . . . . . P6 P6 . . . . . . . . . . . . . . • • . . 1 . ...................................................... . . ...................................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P5 . . . . . . . . . . . . . . . . . . . . . . . • • P4 • • P4 . .................................... 0 . ........................................................................................ . . ................................... ......................................................................................... . .. P5 0 1 2 3 4 5 H` 4.15: (a) Cˆy bao tr`m nho nhˆ t c´ trong lu.o.ng bˇ ng 18. (b) Cˆy Steiner nho nhˆ t ` ´ ´ ˙ ’ao. ˙ ’a ınh a u a a . .o.ng bˇ ng 15 ( = c´c d iˆ’m Steiner). ˙ ` c´ trong lu . o. a a ¯e 125
126
Chu.o.ng 5 B`i to´n Euler v` b`i to´n Hamilton a a aa a L´ thuyˆt d` thi ph´t triˆ’n bˇt nguˆn t`. nh˜.ng b`i to´n cˆ’ d iˆ’n, trong sˆ d o b`i to´n Euler ˙´ ˙˙ ´ˆ `uu ´ y e ¯o . a ea o a a o ¯e o ¯´ a a ˜ ˜’ o` a o ¯˙ ¯ ´ v` b`i to´n Hamilton t` h`nh tr` d i qua mˆ i canh d ung mˆt lˆn v` qua mˆi d ınh d ung aa a ım a ınh ¯ o. ¯´ .a .o.ng u.ng d ong vai tr` quan trong. o` mˆt lˆn tu .a ´ ¯´ o . Hai b`i to´n n`y c´ liˆn quan dˆn nh˜.ng u.ng dung: c´c b`i to´n t` h`nh tr` tˆt ´ ´ a a a oe ¯e u´ a a a ım a ınh o . .`.i d u.a thu. Trung Hoa, ngu.`.i ch`o h`ng), tu. d ˆng ho´ thiˆt kˆ bˇ ng m´y t´ e e` ´ ´ ´a nhˆ t (ngu o ¯ a o aa . ¯o a a ınh, . lˆp lich, vˆn vˆn. a. aa . Mˇc d` hai b`i to´n n`y d u.o.c ph´t biˆ’u rˆ t giˆng nhau, nhu.ng m´.c d o kh´ trong ˙´o ´ au a a a ¯. a ea u ¯ˆ o . . ´ ´ ˙ ’ viˆc giai quyˆt ch´ng l` rˆ t kh´c nhau. e e u aa a . Ch´ng ta s˜ ch´.ng minh rˇ ng trong d` thi vˆ hu.´.ng, tˆn tai thuˆt to´n d a th´.c t` ` `. u eu a ¯ˆ . o o o o a a¯ u ım . .`.i d u.a thu. Trung Hoa c´ thˆ’ d u.a vˆ t` cˇp gh´p ho`n ˙ ` ım a h`nh tr` Euler v` b`i to´n ngu o ¯ a ınh aa a o e¯ e e a . .o.ng nho nhˆ t [30] (c˜ng xem Phˆn 7.5). C´c thuˆt to´n n`y s˜ d u.o.c tr` ´ ` ˙o. ’ ˙ ’a hao c´ trong lu . u a a a a a e¯ . ınh . ` b`y trong c´c Phˆn 5.1 v` 5.2. a a a a Mˇt kh´c, vˆ n d` tˆn tai chu tr` hay mach Hamilton l` nh˜.ng b`i to´n khˆng d a a ¯ˆ ` . ´ eo a a ınh au a a o¯ . . .c khˆng d u.o.c d` cˆp o. d ˆy. Ban d oc quan tˆm c´ thˆ’ xem, chˇng han [30]. Ch´ng ta ˙ ˙ ’ ˙ ¯a ’ th´ u o ¯ . ¯ˆ a e. . ¯. a oe a u . chı tr` b`y trong Phˆn 5.3 nh˜.ng kˆt qua ch´ liˆn quan dˆn su. tˆn tai cua c´c chu tr` ` ´ ¯e . ` . ˙ a ´ ˙ ınh a ’ ˙ ınh e ’ ’ a u e o ınh .ng minh c´ t´ kiˆn thiˆt thuˆt to´n hoˇc o ¯` ´ ´ hay mach Hamilton. Khi c´ d iˆu kiˆn, c´c ch´ e e a u o ınh e e a a a . . . . c´ thˆ’ d` xuˆ t nh˜.ng phu.o.ng ph´p heuristic. ˙e ´ o e ¯ˆ a u a 5.1 B`i to´n Euler a a Dinh ngh˜ 5.1.1 Gia su. G = (V, E ) l` d` thi vˆ hu.´.ng (d o.n hoˇc d a d` thi). Dˆy chuyˆn -. ` ˙˙ ’’ ıa a ¯o . o o ˆ ¯ a ¯ ¯ˆ .o a e . 127
Euler l` dˆy chuyˆn ch´.a tˆ t ca c´c canh cua d` thi, mˆi canh d ung mˆt lˆn. Chu tr` ˜ ` ´’ o` u a ˙a . ˙ ¯o . o . ’ˆ aa e ¯´ .a ınh .i d ınh cuˆi. Euler l` dˆy chuyˆn Euler m` d ınh d` u tr`ng v´ ¯˙ ` ´ a ¯˙ ¯ˆ ’ o’ aa e a u o V´ du 5.1.2 (B`i to´n Euler) C´ch d ˆy khoang ba trˇm nˇm, nhiˆu ngu.`.i dˆn th`nh phˆ ` ´ ˙’ ı. aa a ¯a a a e oa a o .´.c Nga (sau n`y l` th`nh phˆ Kaliningrat) d a t`.ng thˇc mˇc vˆ n d` nhu. ´ ´´e ´ ˙ ’ K¨nigsberg cua nu o o aaa o ¯˜ u a a a ¯ˆ ´ c´ sˆng Pregel chay qua, gi˜.a sˆng c´ c` lao Kneiphof, v` c´ 7 chiˆc cˆu e` ´a ˙ ’ sau: Th`nh phˆ o o a o uo ou ao . trˆn H` 5.1(a); c´ thˆ’ d i dao qua khˇp c´c cˆu nhu.ng mˆ i cˆu chı d i ˙ ´ ´ ˜a aa` o` ˙¯ ’ bˇc qua sˆng nhu e a o ınh o e¯ . a .c a, b, c, d cua th`nh phˆ nhu. mˆt d ınh, mˆi cˆu ˜ ˜a o` ´ ´ o` ˙ ’ o ¯˙ .’ mˆt lˆn thˆi khˆng? Nˆu ta coi mˆ i khu vu .a o o e o a o . .c nhu. mˆt canh nˆi hai d ınh, th` ban d` th`nh phˆ K¨nigsberg l` mˆt ´ ´o ˙ ’ ˙ ¯ˆ a ’ qua lai hai khu vu o. o ¯ ı o o ao . . . . d` thi (H` 5.1(b)). Thˇc mˇc cua ngu.`.i dˆn th`nh phˆ ch´ l`: c´ thˆ’ v˜ d u.o.c d` thi ˙ ´ ´’ ´ a˙ ¯o . ınh ˆ a oa a o ınh a o e e ¯ . ¯ˆ . o ` oeu` a`. bˇ ng mˆt n´t b´t liˆn hay khˆng? N´i c´ch kh´c: tˆn tai chu tr` Euler? a e o oa o ınh . Nh` to´n hoc L. Euler (1707-1783) l` ngu.`.i d` u tiˆn d ˜ ch´.ng minh b`i to´n khˆng aa a o ¯aˆ e ¯a u aa o . .i giai (nˇm 1736, xem [22], [23]), v` v` vˆy b`i to´n thu.`.ng d u.o.c goi l` b`i to´n Euler ˙ ’ c´ l` oo a aıa a a o ¯. .aa a . ` c´c cˆu o. K¨nigsberg. `˙o ’ vˆ a a e a . ... ..... ... ... . . . .. .. . ... a . . .... . . ..... . .. ... .. . ... .. .. ... .. ... . ... .. . ... ....... .... ....... ..... . . ........ ... . . ........ ........ ......... . . ... .. ...... . .. ....... . ... ....................... .. ............ . ............................................................... . . ... . ................................................. .. . . ... .. .. . . .. .. . ... . .. . . ... . .. .. .. . . ... .. .. .. . . .. .. ... .. . . .. .. . .. . ... .. .. . .. . ... .. . .. . .. ... ... .. .. .. .. . .. .. .. ... .. .. .. .. ... .. .. .. .. ... .. .. .. .. ......................... ... .................... .. ... .. .. .. ... ..... .. . ... ..... .. ............................ .. ... ............................... .... .. . ... .. .... ..... . . ... .... .. . ... ... ... ... ... ... .. . .. ... .. . .. .. . .. .. . .. ... .. . . ........................................... c c . . ...................... b b . ... . . ..................... ......................................... ..................... . . . . ... . . ....................... . . .. ... . ... .. . . . .. .. . . .. .. .. ... ... . .. . ... ... ... .. ... ... .. .... .. ................................ .. . ................................. . .... ... .. .... .... ... .. .... . .. .. ....... ......................... .. ................. .. .. .. .. . .. .. .. ... ... .. .. .. .. .. .. .. ... . .. .. ... .. .. .. .. .. . .. .. . ... .. ... . .. . .. .. .. . .. . .. ... . .. ... .. .. . . .. .. . .. .. . .. . .. .. . . .. .. .. . .. . .. . .............................................. .. ... .............................................. .. ... . .. . ......................... ........ . . . ... ................. ........... . .. ... . . ... ....... ... . . . . .. . . ........ ........ ........ ... ........ . ... . . ...... . ..... ..... .... . ... . ... . .. .. .. .. .. .. .. ... ... .. .. .. . .... .. d .. . .... .. . .... .. . .... .. .... ... . .. d (a) (b) H` 5.1: (a) Ban d` cua th`nh phˆ K¨nigsberg. (b) D` thi tu.o.ng d u.o.ng. -ˆ . ´ ˙ ¯ˆ ˙ ’ o’ ınh a oo o ¯ Dinh l´ 5.1.3 [Euler] Da d` thi vˆ hu.´.ng liˆn thˆng G = (V, E ) c´ dˆy chuyˆn Euler nˆu -. - ¯ˆ . o o ` ´ y o e o oa e e a˙` ´´ v` chı’ nˆu sˆ c´c d ı’nh bˆc le bˇ ng 0 hoˇc 2. a ˙ e o a ¯˙ . ’a a . Ch´.ng minh. Tru.´.c hˆt ch´ y rˇ ng d` thi khˆng liˆn thˆng khˆng thˆ’ ch´.a dˆy chuyˆn ˙ u´ ` ´ ` u oe a ¯o . o ˆ e o o eua e hoˇc chu tr` Euler. a ınh . Bˆy gi`. ta ch´.ng minh d iˆu kiˆn cˆn. Nˆu µ l` dˆy chuyˆn Euler, th` chı c´ hai d ınh ¯` e` ´ ` ı ˙o’ ¯˙’ a o u e .a e aa e d` u v` cuˆi c´ bˆc le. Nˆu ngo`i ra, hai d ınh n`y tr`ng nhau (chu tr` Euler) th` khˆng ´ ´ ¯a a o o a ˙ ’ ¯˙’ ˆ e a a u ınh ıo . o ¯˙’ a˙ ’ c´ d ınh bˆc le. . 128
Kˆ tiˆp ta ch´.ng minh d iˆu kiˆn d u bˇ ng quy nap theo sˆ canh m cua G. Hiˆ’n nhiˆn ˙ e ¯˙ ` ´´ ¯` ´ ’a ˙ ’ ee u e o. e e . . . d inh l´ d ung cho moi d` thi liˆn thˆng m canh. Nˆu G c´ ´ ´ ˙˙ ’’ d .nh l´ d ung nˆu m = 1. Gia su ¯. ¯i y ¯´ e y ¯´ ¯o . e ˆ o e o . . . c´c d ınh n`y l` a v` b (nˆu tˆ t ca c´c d ınh cua G c´ bˆc chˇn, chon ˜ ´´’ hai d ınh bˆc le, gia su a ¯˙ ¯˙’ a˙ .’ ˙˙ ’’ ’ e a ˙ a ¯˙ ’ ˙ ’ aa a oa a . . ˙nh a bˆ t k` v` lˆ y b = a). K´ hiˆu µ l` dˆy chuyˆn m` ta d i trˆn d` thi G xuˆ t ph´t t`. a ´ y aa ´ ` ´ ’ dı ¯ a ye aa e a ¯ e ¯o . ˆ a au . theo hu.´.ng tu` y, d i qua mˆ i canh d ung mˆt lˆn. Nˆu tai th`.i d iˆ’m n`o d ´ ta o. d ınh x = b ˙ ˜ o` ´ ˙ ¯˙ ’’ o y´ ¯ o. ¯´ .a e. o ¯e a ¯o . dung mˆt sˆ le canh liˆn thuˆc v´.i x nˆn c´ thˆ’ d i theo canh kh´c chu.a ˙¯ . ´’ ¯˜ ˙ ’ o o˙ . ngh˜ l` ta d a su . ıa a e oo eoe a . . d u.o.c su. dung. Nˆu ta khˆng thˆ’ d i d u.o.c n˜.a, ngh˜ l` d ang o. d ınh b. Nˆu tˆ t ca c´c canh ˙ ´ ´´’ ¯. ˙ . ’ ˙ ¯˙ ’’ e a ˙a . e o e¯ ¯ . u ıa a ¯ d a d u.o.c su. dung, µ l` mˆt dˆy chuyˆn Euler v` d .nh l´ d ung. Trong tru.`.ng ho.p ngu.o.c ` ˙. ’ ¯˜ ¯ . aoa e a ¯i y ¯´ o . . . ` thi con G d u.o.c x´c d .nh bo.i c´c canh chu.a d u.o.c su. dung chı c´ nh˜.ng d ınh bˆc ˙a. ’ ˙. ’ ˙o u ’ ¯˙ ’ lai, d o . . ¯ˆ ¯ . a ¯i ¯. a . chˇn. K´ hiˆu G1 , G2 , . . . , Gp l` c´c th`nh phˆn liˆn thˆng cua G ch´.a ´ nhˆ t mˆt canh. ˜ ` ´o. ˙ ’ a ye aa a ae o u ıt a . . Khi d ´ c´c d` thi Gi c´ sˆ canh ´ ho.n m v` do d ´ theo gia thiˆt quy nap, ch´ng ch´.a mˆt ´ ´ ˙ ’ ¯o a ¯ˆ . o oo. ıt a ¯o e u u o . . chu tr` Euler µi . V` G liˆn thˆng, dˆy chuyˆn µ c´ chung v´.i c´c d` thi G1 , G2 , . . . , Gp c´c ` ınh ı e o a e o o a ¯o . ˆ a d ınh theo th´. tu. i1 , i2 , . . . , ip . Khi d o h`nh tr` ınh: xuˆ t ph´t t`. a d i trˆn µ dˆn d ınh i1 , d i ´ ´’ ¯˙’ ¯e ¯˙ u. ¯´ a a au¯e ¯ . i vˆ i , d i trˆn µ dˆn d ınh i d i doc theo chu tr` µ t`. i vˆ i , `1¯ e ´ ¯˙ `2 ’ doc theo chu tr` µ1 t` 1 e ınh u ¯e 2¯ ınh 2 u 2 e . . v` vˆn vˆn, l` mˆt dˆy chuyˆn Euler xuˆ t ph´t t`. a v` kˆt th´c tai b. Dinh l´ d u.o.c ch´.ng -. ` ´ ´ aa a a o a e a au ae u. y¯ . u . minh. -ˆ . e ˙ -. D` thi thoa c´c d iˆu kiˆn cua Dinh l´ Euler goi l` d` thi Euler. ˙ a ¯` ’ ’ o e y . a ¯ˆ . o . ` 5.1.1 Thuˆt to´n t` dˆy chuyˆn Euler a a ım a e . C´ch ch´.ng minh Dinh l´ Euler 5.1.3 cho ta mˆt thuˆt to´n xˆy du.ng dˆy chuyˆn Euler -. ` a u y o a aa a e . . . trong mˆt d` thi Euler. o ¯ˆ . o . 1. Xˆy du.ng mˆt dˆy chuyˆn d o.n gian µ xuˆ t ph´t t`. s. `¯ ´ ˙ ’ a oa e a au . . 2. Nˆu tˆ t ca c´c canh cua G d a d u.o.c su. dung th` d`.ng v` ta c´ µ l` dˆy chuyˆn Euler. ´´’ ` e a ˙a . ˙ ’ ¯˜ ¯ . ˙ . ’ ıu a o aa e .o.c lai sang Bu.´.c 3. Ngu . . o 3. K´ hiˆu G1 l` d` thi con cua G gˆm c´c canh chu.a d u.o.c su. dung. Chon d ınh c cua G1 ` ˙ ’ ¯. ˙ . ’ . ¯˙’ ˙ ’ ye a ¯o . ˆ oa. . .ng chu tr` d o.n gian µ trong d` thi G xuˆ t ph´t ` ` ´ ˙ ’ nˇ m trˆn dˆy chuyˆn µ. Xˆy du a ea e a ınh ¯ ¯o . 1 a ˆ a . 1 . d ınh c. ˙ ’ t` ¯ u 4. Mo. rˆng dˆy chuyˆn µ bˇ ng c´ch gˇn thˆm chu tr` µ1 tai d ınh c (t´.c l` d˜y c´c ` ´ ` ˙o ’. . ¯˙ ’ a e a a a e ınh uaa a .o.c ch`n v`o d˜y c´c canh cua µ). ˙ ’ ˙ ’ canh cua µ1 d u . ¯ eaaa. . 5. Thay G bo.i G1 v` lˇp lai bu.´.c 2. ˙ ’ aa . o . -ˆ . V´ du 5.1.4 D` thi trong H` 5.2 c´ mˆt chu tr` Euler ı. o ınh oo ınh . (v1 , e1 , v2 , e2 , v3 , e3 , v2 , e4 , v3 , e15 , v4 , e14 , v5 , e13 , v4 , e12 , v6 , e11 , 129
e2 .................................. .... .......................... ......... ........ ...... ...... ...... ...... ..... ..... ..... ..... .... .... .... .... .... e3 .. .... . .... .... .... ... v2 v3 ... . ... ...................................................................................... ........................................................................................... ... .... ... .... . ... . .... .... ..... ... .... . ... . .. . ... .... . ..... . ... .... . ..... .... .... .... . ... ..... .... ..... . ... . .... .. . ... ... . ..... ....... ..... . e4 . .. . ... ...... .. ... ......... . ... . ...... ... ...... . ... . ... ... ... ........ ...... . ........ ....... .. .. ... ........ ... . . ............................ ............................ . ... ... . ... ... .. . .. . . . ... . .... ... ... .... . ... . ... . . ... . e1 .... ... .... . ... . ... ... . . . . ... .... .... . ... ... . ... . . . .... ... .... ... . ... ... . e16 e15 . . . . ... .... .... ... ... . ... . . . . ... .... ... .... ... . ... . . . ... . . e17 ... .... ... .... . ... . ... . ... . . .... ... .... . ... . ... ... . . . . ... .... .... . ... ... . ... . . . ... .... .... . ... ... ... . . . . . ... .... ... . ... .... e14 ... . . . . ... .... ... ... .... . ... . v7 . .. . . . . .... ... . .... ... ....................... ..... ....................... .... . . .... .... e5 . . .... ... ....... . ........... .... . ... ...... .. . ..... .. . . .. ... . . . ... . .... v1 v5 v4 ...... . ........................................................... ...... ....... .... .. . .......................................................... . ..... .. ... ..... . .. .... .. ... .. . ...... ..... ...... . ... . .. . ... . . ..... . ... . ..... ... . .......... . .. . ... ...... .. . .. . . ... .............................. .... .... ........ . . . ............. ......... .... .... .. .... . . ... .. . . .... e13 . .... ... ... . ... . . .. .. .... .. . . ... .... .. ... . .. . . .... . .. ... ... ... ... .... .. . . . . ... .... ... ... . . ... .. .... .. . . ... . .... ... . ... ... . .... . .. ... .. . . ... .... ... . e6 . ... .... e10 . .. . ... .. ... .... . . .. ... .... ... . . ... . ... ... . .... ... .. . . .... .. . ... . ... ... . .... ... . ... ... .... . . e8 e11 e12 ... . ... . .... ... ... . ... ... . .... . . ... ... .... . ... ... . ... ... .... . . ... . . .... ... .. ... . ... ... .... . . e7 . ... ... .... ... . . ... ... ... .... . . ... . . .... .. ... .. ... . . ... .... . .. . ... .... . . ... . .. ... .... .. . . . ... .... . ... .. ... ... . .. .... . . . ... .... .. ... .. . . . .. . .... . ... . ... ... . .... ... .. . .... . ... .. . ... ... . ... .... . . .... . ... ... . ... ... ... . . ..... .... . ... .. . .... . .... . ..... .... . . . .... ... . . . . .. .... . . .... . .. ... . .. .... .. ..... .. ................................................................................................ ............................................................................................ .... . .. e9 v8 v6 H` 5.2: Mˆt v´ du vˆ d` thi Euler. o ı . ` ¯ˆ . ınh eo . v5 , e16 , v3 , e17 , v7 , e10 , v6 , e9 , v8 , e8 , v7 , e5 , v1 , e7 , v8 , e6 , v1 ). Mˆt dˆy chuyˆn hay chu tr` Euler c´ thˆ’ d u.o.c x´c d inh bo.i mˆt danh s´ch c´ th´. ˙ ` ˙’ oa e ınh o e ¯ . a ¯. o a ou . . . c´c d ınh cua G ch´.a trong n´. Chˇng han, ta c´ thˆ’ su. dung mˆt cˆ u tr´c danh s´ch ˙˙ . ˙ ’ ´ ˙ ’ ˙ ’ ’ tu a ¯ u o a oe oa u a . . . ´ liˆn kˆt ee typedef struct PathNode *PathPtr; struct PathNode { byte Vertex; PathPtr Next; }; dˆ’ d ´nh dˆ u c´c d ınh liˆn tiˆp trˆn dˆy chuyˆn, trong d ´ V ertex l` sˆ hiˆu d ınh trˆn dˆy ˙ ´ ´ ` ´. a a ¯˙ ’ a o e ¯˙ ’ ¯e ¯a e e ea e ¯o ea .a sˆ hiˆu cua d ınh kˆ V ertex trˆn dˆy chuyˆn. ` ´´ u´. ` ` chuyˆn; v` con tro N ext chı n´t kˆ tiˆp ch´ o e ˙ ¯˙ ˙ ’ ˙u ee ’ ’’ e a e ea e ˜ thˆ y rˇ ng, danh s´ch n`y c´ sˆ n´t bˇ ng (m + 1). ` ´u ` ´a Dˆ a e a a oo a T`. d ˆy vˆ sau ta s˜ gia thiˆt G d u.o.c cho bo.i mang c´c danh s´ch kˆ V out[] (c´ u ¯a ` ´ ` e˙ ’ ˙’ ˙ ’ e e ¯. a a e o ´), trong d ´ v´.i mˆ i d ınh vi ∈ V, V out[i] l` danh s´ch c´c d ınh liˆn thuˆc d ınh vi ˜ ¯˙ o’ a ¯˙’ o ¯˙’ trong sˆ o ¯o o a a e . . v` tru.`.ng d o d`i Length o. n´t th´. j (tu.o.ng u.ng d ınh vj ) l` sˆ canh liˆn thuˆc v´.i d ınh ´ ˙u ’ ¯˙ ’ o o ¯˙ ’ a o ¯ˆ a u ´ ao. e . . .c hiˆn thuˆt to´n, mˆ i khi d i qua canh (v , v ) n`o d ´, ta giam d o ˜ ˙ ¯ˆ ’ vi . Trong qu´ tr` thu a ınh . e a a o ¯ a ¯o . . . . ij 130