Lí thuyết đồ thị part 8

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

Thêm vào BST

Báo xấu

86
lượt xem 13
download

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

Có nhiều cách khác nhau để lưu trữ các đồ thị trong máy tính. Sử dụng cấu trúc dữ liệu nào thì tùy theo cấu trúc của đồ thị và thuật toán dùng để thao tác trên đồ thị đó. Trên lý thuyết, người ta có thể phân biệt giữa các cấu trúc danh sách và các cấu trúc ma trận. Tuy nhiên, trong các ứng dụng cụ thể, cấu trúc tốt nhất thường là kết hợp của cả hai. Người ta hay dùng các cấu trúc danh sách cho các đồ thị thưa (sparse graph), do chúng đòi hỏ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 8

tuyˆn cua n´ theo gia thiˆt quy nap lˆp th`nh mˆt co. so. gˆm c´c chu tr` d ˆc lˆp. Khi ´˙o ´ ˙` ’ ˙ ’ ’o e e .a a o a ınh ¯o a . . .. .u han m´.i m` chu tuyˆn l` mˆt chu tr` khˆng phu thuˆc ´ ˙. . ’ tra lai canh e, ta c´ mˆt diˆn h˜ oo eu oa eao ınh o o . . . . . . .´.c (v` n´ ch´.a mˆt canh khˆng thuˆc v`o mˆt chu tr` n`o trong sˆ ´ v`o c´c chu tr` tru o aa ınh ıo u o. o oa o ınh a o . . . ´y). Do bˆ’ sung mˆt canh khˆng thˆ’ l`m tˇng chu sˆ lˆn qu´ mˆt d o.n vi, nˆn ˙ ˙a a ´e c´c chu tr` ˆ a ınh a o o. o e o a o¯ .e . . sˆ diˆn h˜.u han cua d` thi G qua l` x´c d inh mˆt co. so. gˆm c´c chu tr` d ˆc lˆp. ´. ˙` ˙ ¯o . ’ˆ ˙ a a ¯. ’ ’o oeu o a ınh ¯o a . . .. Hˆ qua 6.3.2 [Euler, 1752] Gia su. G l` d` thi tˆ pˆ phˇ ng liˆn thˆng n d ı’nh, m canh v` ˙ ’ ˙ ’ ˙˙ ’’ ¯˙ e a ¯ˆ . o o a o e o a . . f diˆn. Khi d ´ e ¯o . f = m − n + 2. Ch´.ng minh. Thˆt vˆy, sˆ c´c diˆn h˜.u han bˇ ng chu sˆ ν (G), nˆn ` ´ ´ u a a oa eu a o e .. . . f = ν (G) + 1 = (m − n + 1) + 1 = m − n + 2. C˜ng c´ thˆ’ ch´.ng minh c´ch kh´c nhu. sau. ˙ u oeu a a Nhˆn x´t rˇ ng chı cˆn ch´.ng minh cho mˆt d o.n d` thi, v` viˆc thˆm mˆt khuyˆn hoˇc ae` ˙` ’a a u o¯ ¯ˆ . ı e o e o e a . . . . . .n gian l` tˇng sˆ diˆn v` sˆ canh cua d` thi lˆn mˆt d o.n vi. ´. ´ ˙¯ ’ ˙ aa ’ ˙ ¯o . e ’ˆ thˆm mˆt canh song song chı d o e o. o e ao. o¯ . . . Ch´ng ta c˜ng c´ thˆ’ xo´ tˆ t ca c´c d ınh treo v` c´c canh liˆn thuˆc n´. Nˆu thˆm (hoˇc ˙ ´’ ´ o e a a ˙ a ¯˙ ’ u u aa . e ooe e a . . b´.t) mˆt canh v` mˆt d ınh th` hiˆu sˆ (m − n) khˆng d ˆ’i.˙ .´ a o ¯˙ .’ o o. ıeo o ¯o . V` mˆ i d o.n d` thi phˇng c´ thˆ’ biˆ’u diˆn trˆn mˇt phˇng sao cho mˆ i canh l` mˆt ˙˙ ˜ ˙ ’ ˜ ˙ ’ ˜ ı o¯ ¯ˆ . a o oee e e a a o. ao . . ˙ ng (Dinh l´ 6.2.1), nˆn mˆt d` thi phˇng c´ thˆ’ d u.o.c v˜ trˆn mˇt phˇng sao cho -. ˙¯ . e e ’ ˙ ’ ˙ ’ d oan thˇ ¯. a y e o ¯o . a .ˆ oe a a . ˜ ´. ´ c´c diˆn l` c´c d a gi´c. K´ hiˆu f l` sˆ diˆn v` kp l` sˆ c´c diˆn c´ p canh. V` mˆi canh a e aa¯ a ye ao e a aoa eo ıo. . . . . e ˙ ¯´’ thuˆc biˆn cua d ung hai d a gi´c, nˆn o ¯ a e . 3k3 + 4k4 + 5k5 + · · · + rkr = 2m, trong d o kr l` sˆ c´c d a gi´c v´.i sˆ canh cu.c d ai. ´ ´ ¯´ aoa¯ a oo. . ¯. Mˇt kh´c a a . k3 + k4 + · · · + kr = f. Tˆ’ng tˆ t ca c´c g´c tai mˆi d ınh trong d a gi´c tu.o.ng u.ng d` thi l` 2nπ. Nhˇc lai rˇ ng tˆ’ng ˙ ˙ ˜’ ´ ` ´’ a ˙ a o . o ¯˙ o ¯ a ´ ¯o . a ˆ a.a o ´t ca c´c g´c trong mˆt d a gi´c p canh l` (p − 2)π v` tˆ’ng tˆ t ca c´c g´c ngo`i l` (p + 2)π. ˙ ´ ˙a o ˙a o ’ ’ tˆ a o¯ a a ao a aa . . Do d o ¯´ 2nπ = (3 − 2)πk3 + (4 − 2)πk4 + · · · + (r − 2)πkr + 4π = (2m − 2f )π + 4π. T`. c´c d ˇng th´.c trˆn, ta suy ra ˙ ’ u a ¯a u e 2(m − f )π + 4π = 2nπ. Vˆy f = m − n + 2. a . 155
` e ` o ¯˙ ’ V´ du 6.3.3 [Euler] Ta x´t trong khˆng gian ba chiˆu mˆt d a diˆn lˆi c´ n d ınh, m canh ı. e o e o¯ .o . . v` f diˆn. Hiˆ’n nhiˆn ta c´ thˆ’ v˜ n´ trˆn mˆt mˇt cˆu sao cho hai canh bˆ t k` khˆng cˇt ˙ ˙ ´ a` ´ a e e e o eeoe o a ayo a . . . . .ng d iˆ’m kh´c c´c d` u m´t. Sau d ´ tiˆn h`nh ph´p chiˆu nˆ’i v´.i tˆm o. gi˜.a ˙ ˙ ´ ´ e ooa˙u ’ nhau tai nh˜u ¯e a a ¯a ˆ u ¯o e a e . ˙ biˆ’u diˆn d a diˆn d ´ trˆn mˇt phˇng. V` d` thi l` phˇng nˆn ’e ˙ ˜¯ ˙ ’ ˙ ’ mˆt trong c´c diˆn ta c´ thˆ o a e oe e e ¯o e a a ı ¯o . a a ˆ e . . . . ta c´ hˆ th´.c co. ban sau d ay cua c´c d a diˆn lˆi: e` ˙ ’ ¯ˆ ˙ a ¯ ’ oe u o . . n − m + f = 2. Hˆ qua 6.3.4 Trong mˆt d o.n d` thi phˇ ng, liˆn thˆng c´ f diˆn, n d ı’nh, m canh (m ≥ 2), ˙ ’ ˙ ’ ¯˙ e o ¯ ¯ˆ . a o e o o e . . . . .c sau luˆn nghiˆm d ung ´˙ ’ c´c bˆ t d ˇ ng th´ a a ¯a u o e ¯´ . 2m ≥ 3f, 3n − 6 ≥ m. Ch´.ng minh. Mˆi diˆn c´ biˆn ´ nhˆ t l` ba canh, mˆ i canh l` chung cua ch´ x´c hai ˜ e o e ıt a a ˜ ´ ˙’ u o o. a ınh a . . diˆn, do d o e ¯´ . 2m ≥ 3f. Thay thˆ f = m − n + 2 trong cˆng th´.c Euler, ta c´ bˆ t d ang th´.c th´. hai. ´˙ ’ ´ e o u o a ¯ˇ u u Ch´ng ta lu.u y rˇ ng bˆ t d ang th´.c th´. hai chı l` mˆt d iˆu kiˆn cˆn m` khˆng d u vˆ ´` ´˙ ’ ˙ a o ¯` e` a o ¯˙ ` ’ ’e u a a ¯ˇ u u e .a . .n d` thi phˇng cˆn phai thoa m˜n c´c ˙ ’ ˙ ’ t´ phˇng cua mˆt d` thi. N´i c´ch kh´c, moi d o ¯o . a ` ˙ ’ ˙ ’ ˙ ’ ınh a o ¯ˆ . .o oa a .¯ ˆ a aa .ng d iˆu ngu.o.c lai l` khˆng d ung. Chˇng han d` thi Kuratowski K thoa ˙ ’ d iˆu kiˆn n`y, nhu ¯ ` ¯` ˙ ’ e ea e . . a o ¯´ a . ¯ˆ .o . 3,3 3n − 6 = 3.6 − 6 = 12 ≥ m = 9. Nhu.ng V´ du 6.3.5 D` thi K3,3 khˆng phˇng. Dˆ’ ch´.ng minh ch´ng ta cˆn chı ra rˇ ng trong d` -ˆ . -e u ˙ ˙ ’ ` ` ˙ ’ ı. o o a u a a ¯o ˆ ` n tai diˆn m` biˆn cua n´ c´ sˆ canh nho ho.n 5. Thˆt vˆy, nˆu d` thi l` ´. ´ ¯ˆ . a ˙ ooo ’ ˙ ’ thi n`y khˆng tˆ . .a o o e ae aa e o . .. ˙ ’ phˇng th` 2m ≥ 4f. a ı Theo cˆng th´.c Euler o u 2m ≥ 4(m − n + 2). Vˆy a . 2.9 ≥ 4(9 − 6 + 2). ˜ ˙ ’ Hay 18 ≥ 20! Mˆu thuˆn. Do d o d` thi K3,3 khˆng phˇng. a a ¯´ ¯ˆ . o o a V´ du 6.3.6 D` thi d` y d u c´ nˇm d ınh K5 l` khˆng phˇng. Thˆt vˆy, nˆu ngu.o.c lai th` - ˆ . ¯a ¯ ˙ o a ¯˙ ˙ ’ ´ ’ ’ ı. o ˆ ao a aa e ı .. .. K5 s˜ c´ eo f = m − n + 2 = 10 − 5 + 2 = 7 156
diˆn. Chu tuyˆn cua mˆi diˆn d` u c´ ´ nhˆ t ba canh. Nˆu lˆp d o.n d` thi liˆn thuˆc ˜ ´ ´ ´. ˙ ’ e e o e ¯ˆ o ıt e a ea¯ ¯o . e ˆ o . . . . diˆn-canh, th` sˆ canh mˆt mˇt ≤ 2m v` mˇt kh´c lai ≥ 3f. T`. d ´ ´ e. ıo. o a aa a. u ¯o . . . . 20 = 2m ≥ 3f = 21. ˙ ’ Vˆ l´, vˆy K5 l` khˆng phˇng. oy a ao a . Hˆ qua 6.3.7 Mˆ i ba n d` d. a l´ c´ ´ nhˆ t mˆt diˆn m` sˆ canh cu a chu tuyˆn nho ho.n ˜’o ´oe ´ ´ ˙ ’ o ˙ ¯ˆ ¯i y o ıt a ˙ ’ ˙ ’ e ao. e . . . ` ng 5. hoˇc bˇ aa . Ch´.ng minh. Thˆt vˆy, trong ban d` d .a l´, mˆ i d ınh l` d` u m´t cua ´ nhˆ t 3 canh; nˆu ˜’ ´ ´ ˙ ¯ˆ ¯i y o ¯˙ ’ u ˙ ıt a ’ u aa o a ¯a ˆ e .. . .n d` thi liˆn thuˆc d ınh-canh th` sˆ canh mˆt mˇt ≤ 2m, mˇt kh´c lai ≥ 3n, vˆy ´ o ¯˙ ’ lˆp d o ¯o . e a¯ ˆ ıo. o a a a. a . . . . . . . ´u gia thiˆt rˇ ng mˆi diˆn c´ chu tuyˆn gˆm ´ nhˆ t 6 canh v` nˆu lˆp d o.n ` ˜eo ´a ´ ` ıt a ´ ´a¯ ˙’ n ≤ 2m/3. Nˆ e e o eo ae . . . d` thi liˆn thuˆc diˆn-canh, th` sˆ canh cua n´, mˆt mˇt ≤ 2m, mˇt kh´c lai ≥ 6f. Vˆy ´ ˙ ’oo ¯o . e ˆ o e. ıo. a a a. a . . . . . . ˙ gia thiˆt l` d` thi liˆn thˆng (nˆu khˆng th` ch´.ng minh hˆ ’˙ ´ a ¯o . e ´ f ≤ 2m/6. Ta luˆn luˆn c´ thˆ ’ o ooe e ˆ o e o ıu e . qua cho t`.ng th`nh phˆn), v` do d o c´ thˆ’ viˆt˙´ ` ˙ ’ u a a a ¯´ o e e 2 = n − m + f ≤ 2m/3 − m + m/3 = 0. - ` ¯o o Diˆu d ´ khˆng thˆ’ xay ra. ˙’ e˙ e Hˆ qua 6.3.8 Gia su. G l` d o.n d` thi phˇ ng liˆn thˆng. Khi d ´ tˆn tai d ı’nh v ∈ V sao ˙ ’ ¯o ` . ¯ ˙ ˙’ ˙˙ ’’ e a¯ ¯ˆ . a o e o o . cho d(v ) ≤ 5. Ch´.ng minh. Thˆt vˆy, trong d` thi G, mˆi diˆn d u.o.c bao ´ nhˆ t bo.i ba canh kh´c nhau; ˜. ´’ ıt a ˙ u aa ¯ˆ . o o e¯. a .. . .c l` d` thi gˆm tˆp X c´c d iˆ’m d`ng dˆ’ biˆ’u thi ˙ u ¯e ˙ ˙e nˆu lˆp d` thi H liˆn thuˆc diˆn-canh (t´ a ¯o . ` ´. e a ¯o . ˆ e o e. u ˆ oa a ¯e . . . . .p Y c´c d iˆ’m d`ng dˆ’ biˆ’u thi c´c canh v` c´c canh nˆi d iˆ’m x ∈ X v´.i ˙ ˙˙ ˙ ´ c´c diˆn, tˆp ho a e a a ¯e u ¯e e .a . aa . o ¯e o . . . y ∈ Y nˆu diˆn x liˆn thuˆc canh y ) th` sˆ canh cua d` thi H, mˆt mˇt ≤ 2m, mˇt kh´c lai ´ ´ ˙ ¯ˆ . ’o e e e o. ıo. o a a a. . . . . . ´u mˆ i d ınh l` d` u m´t ´ nhˆ t cua 6 canh, th` c˜ng bˇ ng c´ch nhu. ˜ ¯˙ ` ´˙ o’ u ıt a ’ ≥ 3f, vˆy f ≤ 2m/3. Nˆ a e a ¯a ˆ ıu a a . . vˆy ta thu d u.o.c n ≤ 2m/6, ngh˜ l` (theo cˆng th´.c Euler) a ¯. ıa a o u . 2 = n − m + f ≤ m/3 − m + 2m/3 = 0. Vˆ l´! oy ˙ ’ 6.4 Ph´t hiˆn t´ phˇ ng a e ınh a . ˙ ’ ˙’ d inh d` thi G l` phˇng hay khˆng l` mˆt b`i to´n quan trong, chˇng han trong Viˆc x´c ea ¯. ¯ˆ . o aa o aoa a a . . . . . d ´ nhiˆu chˆ t ho´ hoc m` cˆng th´.c cˆ u tao cua n´ c´ thˆ’ biˆ’u diˆn nhu. mˆt ˙e ˙ ˜ ` ´ ´ ˙ ’ ˙ oo e ’ ho´ hoc: a. o ¯o e a a. ao ua. e o . 157
d` thi phˇng; v` tra l`.i cˆu hoi n`y bˇ ng c´ch cˆ gˇng thu. v˜ n´ lˆn mˆt mˇt phˇng r˜ ˙ ’ ˙a` ´´ ˙ ’ a ˙o a ’ ’ ˙ e oe ’ ¯o . a ˆ a a oa o a a o . . .i tˆt. Vˆ thuˆt to´n th`.i gian O(n) kiˆ’m tra mˆt d` thi ˙ ˙o ´ ` ˙aoa ’ ’ r`ng khˆng phai l` mˆt cˆu tra l` o a o e a a o e o ¯o . ˆ . . . c´ phˇng hay khˆng, v` nˆu phˇng th` biˆ’u diˆn n´ nhu. thˆ n`o c´ thˆ’ xem [34], [18]. ˙ ˙ ˙ ’ ˙ ’ ˜o ´ ´ oa o ae a ıe e ea o e C˜ng c´ mˆt thuˆt to´n [33] th`.i gian O(n log n) dˆ’ kiˆ’m tra t´ d ˇng cˆ u cua hai ˙˙ ˙ ’ ´˙ ’ u oo a a o ¯e e ınh ¯a a . . .`.ng nay sinh trong ho´ hoc khi ch´ng ta muˆn nghiˆn ˙ ’ d` thi phˇng. B`i to´n n`y c˜ng thu o ´ ˙ ’ ¯o . a ˆ aaau a. u o e .u c´c phˆn tu.. a˙ ’ c´ a u C´c tiˆu chuˆ’n d o.n gian v` hiˆu qua sau cho ph´p ph´t hiˆn t´ phˇng cua d` thi. ˙ ˙ ’ ˙ae ’ ˙ ’ ˙ ¯o . ’ˆ ae a¯ e a e ınh a . . Ph´p r´ t gon co. so. ˙’ eu . ˙ ’ ˙ ’ 1. Do d` thi l` phˇng nˆu v` chı nˆu c´c th`nh phˆn liˆn thˆng cua n´ l` phˇng, ch´ng ´ ’´ ` e a ˙e a ˙ oa a ’ ¯o . a a ˆ a ae o u ˙ cˆn x´t mˆt th`nh phˆn liˆn thˆng cua n´. C˜ng vˆy, mˆt d` thi c´ d iˆ’m kh´.p ˙ ’` e ` ˙ou ’ ta chı a o a ae o a o ¯ˆ . o ¯ e .o o . . l` phˇng nˆu v` chı nˆu c´c khˆi cua n´ l` phˇng. V` vˆy d ˆi v´.i mˆt d` thi G cho ˙ ’ ˙ ’ ´ ’´ ´’ ´ e a ˙e a o ˙ oa a aa ı a ¯o o o ¯ˆ . o . . tru.´.c, x´c d .nh o a ¯i G = {G1 , G2 , . . . , Gk }, trong d o Gi , i = 1, 2, . . . , k, l` c´c d` thi con khˆng t´ch d u.o.c cua d` thi G. Rˆi th` ` ˙ ¯o . ’ˆ ¯´ a a ¯o . ˆ o a ¯. o ı ch´ng ta chı cˆn kiˆ’m tra t´ phˇng cua mˆ i Gi . ˙ ˙ ’ ˜ ˙` ’a ˙ ’ u e ınh a o ˙ ’ ´ 2. Do viˆc thˆm hay x´a c´c khuyˆn khˆng l`m mˆ t t´ phˇng, ta xo´ c´c khuyˆn. e e oa e o a a ınh a aa e . 3. Tˆ t ca c´c canh song song c˜ng khˆng anh hu.o.ng trong viˆc x´t t´ phˇng, v` vˆy ˙ ’ ´’ a ˙a . ˙ ’ ˙’ u o e e ınh a ıa . . . mˆt canh c`n lai. ´’ aa ˙a . xo´ tˆ t ca c´c canh song song tr` o . u. o. 4. Loai bo tˆ t ca c´c d ınh bˆc hai v` coi hai canh nˆi v´.i d ınh d ´ l` mˆt khˆng anh ’´ ’ ´ . ˙ a ˙ a ¯˙ ’ o o ¯˙ ’ ˙ ’ a a ¯o a o o . . . .o.ng dˆn t´ phˇng cua d` thi. N´i c´ch kh´c thu.c hiˆn “r´t gon chuˆi.” ˙ ’ ˜ ´ hu ˙ ’ ˙ ¯o . o a ’ˆ ¯e ınh a a e u. o . . Lˇp lai c´c Bu.´.c 3 v` 4 cho dˆn khi ta d u.o.c mˆt d` thi d o.n gian nhˆ t cho ph´p x´c ´ ´ ˙ ’ a.a o a ¯e ¯. o ¯o . ¯ .ˆ a ea . ˜ d`ng t´ phˇng cua n´. ˙ ’ ˙o ’ d .nh dˆ a ¯i e ınh a Dˆi v´.i mˆt d` thi liˆn thˆng khˆng c´ d iˆ’m kh´.p Gi , sau khi ´p dung c´c Bu.´.c 3 v` - o o o ¯ˆ . e ˙ ´ .o o o o ¯e o a a o a . .o.c mˆt d` thi H c´ c´c d ac tru.ng: 4 ta s˜ d u . e¯ o ¯o . i o a ¯ˇ .ˆ . -. -ˆ . Dinh l´ 6.4.1 D` thi Hi c´ mˆt trong ba dang y o oo . . 1. Mˆt canh d o.n; hoˇc l` o. ¯ aa . . 2. Mˆt d` thi d` y d u c´ bˆn d ı’nh; hoˇc l` ´ o ¯ˆ . ¯ˆ ¯ ˙ o o ¯˙ ’ .o a aa . 3. Mˆt d o.n d` thi khˆng t´ch d u.o.c c´ sˆ d ı’nh n ≥ 5 v` sˆ canh m ≥ 7. ´ ´ a ¯ . o o ¯˙ o¯ ¯ˆ . o o ao. . 158
Ch´.ng minh. Dinh l´ c´ thˆ’ d u.o.c ch´.ng minh bˇ ng c´ch khao s´t tˆ t ca c´c d` thi liˆn -. ˙ ` ´’ ˙ a a ˙ a ¯o . e ’ u y o e¯ . u a a ˆ .o.c v´.i sˆ canh nho ho.n hoˇc bˇ ng s´u. a` ´ ˙ ’ thˆng khˆng t´ch d u . o o . o o a¯ a a . Ap dung d .nh l´, ch´ng ta thˆ y rˇ ng tˆ t ca c´c d` thi Hi ro.i v`o loai 1 hoˇc 2 l` ´ a` ´a ´’ a ˙ a ¯o . ¯i y u ˆ a a a . . . ˙ ng, do d ´ khˆng cˆn kiˆ’m tra thˆm. ˙ ’ ` phˇ a ¯o o a e e T`. nh˜.ng d iˆu nˆu trˆn, ch´ng ta cˆn nghiˆn c´.u c´c d o.n d` thi liˆn thˆng khˆng ¯` ` u u ee e u a e u a¯ ¯ˆ . e o o o .o.c v´.i ´ nhˆ t nˇm d ınh, v` mˆ i d ınh c´ bˆc l´.n ho.n hay bˇ ng ba. Kˆ dˆn, ch´ng ˜ ¯˙ ` ´ ´´ t´ch d u . o ıt a a ¯˙ ’ ao’ a¯ oao a e ¯e u . ta cˆn kiˆ’m tra bˆ t d ang th´.c m ≤ 3n − 6. Nˆu bˆ t d ˇng th´.c khˆng thoa m˜n, th` Hi ˙ ´˙ ’ ´˙ ’ ` ´ a ¯a ˙ ’ a e a ¯ˇ u e u o a ı khˆng phˇng. Ngu.o.c lai, ch´ng ta kiˆ’m tra thˆm bˇ ng c´ch ´p dung d .nh l´ Kuratowski ˙ ˙ ’ ` o a u e e a aa ¯i y .. . .´.i d ay. Tru.´.c hˆt ta cˆn d inh ngh˜ sau. ´ ` ¯. du o ¯ˆ oe a ıa Dinh ngh˜ 6.4.2 (a) Trong mˆt d` thi, hai canh d u.o.c goi l` trong mˆt chuˆi, nˆu ch´ng -. ˜´ ıa o ¯o . .ˆ ¯. .a o oe u . . o ¯˙ .’ c´ d ung mˆt d ınh chung bˆc hai. o ¯´ a . (b) Hai d` thi d u.o.c goi l` d` ng phˆi nˆu d` thi n`y c´ thˆ’ nhˆn d u.o.c t`. d` thi kia bˇ ng ˙ ` ´ˆ ¯ˆ . ¯ . o . a ¯o ˆ o e ¯o . a o e a ¯ . u ¯ˆ . o a . .c l` ch`n thˆm c´c d ınh bˆc hai) hay ho.p nhˆ t c´c ˜ ´ a ¯˙ ’ c´ch tao thˆm c´c canh trong chuˆ i (t´ a e a e a. ou e a aa . . . ˜i. canh trong chuˆo . V´ du 6.4.3 C´c d` thi G1 v` G2 trong H` 6.6 l` d` ng phˆi, do c´ thˆ’ d u.a vˆ c`ng d` ˙ ` u ¯ˆ ı. a ¯o . ˆ a ınh a ¯ˆ o o o e¯ e o thi G . . • • • • • • • ...................................... . ................................... . .. ...................................... . ................................... . .. ...................................... . ................................... . .. .... . .... . .... . . . . .. ... .. . .. ... .. . .. ... .. . . . . .. ... .. . .. ... .. ... .. . .. . . . . .. .. . .. .. . .. .. . .. .. . .. .. . .. .. . . . . .. .. .. .. .. .. .. .. . .. .. . .. .. . .. . .. .. .. . .. .. . . . . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. • . . . .. .. .. .. .. .. . . . .. .. .. .. .. .. . . . .. .. .. .. .. .. . . . .. .. .. . . . .. .. .. .. .. .. .. .. .. . . . .. .. .. .. .. .. . . . .. .. .. . . . .. .. .. .. .. .. .. .. .. . . . .. .. .. .. .. .. . . . .. .. .. . . . .. .. .. .. .. ... .. .. ... .. .. ... . . . .. .. ... .. .. ... .. .. ... . . . . . . .. .. .. . . . .. .. .. . . . .. .. .. .. .. .. . . . .... .... .... • • • • • • .. .. .. . . . . . . . . . . . . . . . . . . .. .. .. .. .. .. . . . .. .. .. .. .. .. . . . . . . .. .. .. . . . .. .. .. .. .. .. .. .. .. . . . . . . . . . .. .. .. .. .. .. .. .. .. . . . .. .. .. . . . . . . .. .. .. .. .. .. . . . .. .. .. .. .. .. .. .. .. . . . .. .. .. .. .. .. .. .. .. • .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... ... ... .. .. .. ... ... ... .. .. .. .. .. .. .. .. .. ... ... ... ... ... ... .. ... .. ... .. ... .. .. .. .. .. .. .... .... .... .... .... .... .. .. .. .. .. .. ... ... ... .... .... .... .. .. .. .. .. .. • .............. • .............. • .............. ............ ............ ............ . . . G1 G2 G H` 6.6: ınh Hiˆ’n nhiˆn rˇ ng d` thi l` phˇng nˆu v` chı nˆu moi d` thi d` ng phˆi v´.i n´ l` phˇng. ˙ ` ˙ ’ ˙’ ´ ’´ e a ˙e e e a ¯ˆ . a ao . ¯ˆ . ¯o o ˆ o o oa a .n n˜.a, quan hˆ R trˆn tˆp c´c d` thi x´c d inh bo.i G RG nˆu v` chı nˆu G v` G d` ng ´ a ˙e ’´ ˙ ’1 Ho u e e a a ¯o . a ¯. ˆ 2e 1a 2 ¯oˆ . . .o.ng d u.o.ng. phˆi l` quan hˆ tu oa e ¯ . Dinh l´ 6.4.4 [Kuratowski, 1930] D` thi G l` phˇ ng nˆu v` chı’ nˆu G khˆng ch´.a d` thi -. -ˆ . ˙ ’ ´ ´ e a ˙e y o aa o u ¯ˆ . o .i hoˇc K hoˇc K . con d` ng phˆi v´ ¯ˆ o oo a a . . 5 3,3 159
Ch´.ng minh. Diˆu kiˆn cˆn. R˜ r`ng, v` G khˆng thˆ’ biˆ’u diˆn trˆn mˇt phˇng sao cho c´c -` ˙˙ ˜ ˙ ’ e` u e .a oa ı o ee e e a a a . . tai c´c d ınh chung cua ch´ng nˆu n´ ch´.a d` thi ´ ´ canh cua ch´ng khˆng cˇt nhau ngoai tr` . a ¯˙ ˙ ’ ’ ˙ ’ u o a u u e o u ¯ˆ . o . . con d` ng phˆi v´.i K5 hoˇc K3,3 . ¯o ˆ oo a . -` e ¯˙ ’ Diˆu kiˆn d u. Xem [4]. e . -. ` V´ du 6.4.5 Bˇ ng c´ch ´p dung Dinh l´ Kuratowski ta c´ d` thi trong H` 6.7 khˆng ı. a aa y o ¯ˆ . o ınh o . ˙ ng. Thˆt vˆy, tru.´.c hˆt xo´ c´c canh (a, b), (e, f ) v` (g, h); sau d ´ “r´t gon” c´c chuˆi ’ ˜ ´ phˇa aa oe aa . a ¯o u . a o .. .o.c c´c canh m´.i (a, d) v` (f, c). D` thi thu d u.o.c l` K . -ˆ . (a, g ), (g, d) v` (f, h), (h, c) dˆ’ d u . a . ˙ a ¯e ¯ o a o ¯ . a 3,3 .a mˆt d` thi con d` ng phˆi v´.i K v` do d ´ khˆng phˇng. ˙ ’ Suy ra G ch´ u o ¯o . .ˆ ¯oˆ oo 3,3 a ¯o o a a •... . ... .......... ..... . ... . .. . . .... .... . . .... . .... .. .. ....... .... .. .. ....... . .... .... .... .. .... .. . . . .... . .... .... . . .... . . .... .... . . .... .... . . . . . . .... .... .... . .... . . . . . . . .... .... .... . . .... . . . . .... .... . . .... .... . . . . .... .... . . . . .... . . .... . . .... .... . . .. . . f• •b . ......................................................................................... ........................................................................................... . .... ... . .... .... .. . ... . . . .... ... .... . . . .. . . ... . ...... . . .. .. . . . .. . . .. . . . ... . ... . . . ... .. . ... . . . . ... . g . . . . ... ... .. . . ... .. . . ... . . . . ... ... . ... . . ... . . • . . . ... ... . ... . . . ... . . . .. ... .. . ... . . ... ... ... . . . . .. ... . ... ... .. ..... . . ..... . .. ... ... .. . ... .. . ... . ... .. . ... . ... . . . ... . .... ... . .. .. .. .. ... . .. . . . ... .. ..... . .. .. . . ... . . .. ... .. .. . ..... . .. ... .. . . ..... . . .. .. ... .. ... . .. . ... . . . ... ... ..... . ... . ... ... . .... . . . .. . . . . . . . .... ... . .. . . . ... ... . . . . ........ . . . .. . .. . ... . . . .. . .. ........ . .. . .. .. ..... . .. . .. ... . . . .. .. ... . . .. ... . . ... .. . . .. .. ... . . . ... ... ... . . . . .. . ... . ... ... . .. . ... ... . . . ... .. .. ... .. . . ... . ... .. .. ... .. . .. .. ... .. ... .. . . .. ... . .. ... . . . ..... ... . .. . .... . . . . ..... .. •h .. ..... .. . . . ... . . . .. . . . . ... .. .... . .. .... • .... . .... . .. .. .... . .. .. . ..... . . .. ..... .. ..... . ..... ..... . .. . . .. . e .. .. ...... .. . ..... . .. ..... .. . .... .. . .... . .. . .... .. . ..... .. . ..... .. . .. . ..... .. ..... . . ........ . .. ..... .. . .. . .. ..... ..... .. .. .. .. ..... ..... .. . .. .. ..... ..... .. .. .. .. ..... ..... ..... ... .. . ..... ... .. . . .. . .. . . . ............................................... • • .. . ............................................ .. .. . ... c d H` 6.7: ınh Viˆc kiˆ’m tra t´ phˇng du.a v`o Dinh l´ Kuratowski l` kh´ d oi v´.i c´c d` thi l´.n a -. ˙ ˙ ’ ´ e e ınh a y a o ¯ˆ o a ¯o . o ˆ . . ˙ ng han, d o.n d` thi khˆng t´ch d u.o.c c´ 25 d ınh v` bˆc cua mˆi d ınh ≥ 3). C´ mˆt sˆ ’ ˜ ¯˙ .´ ˙ ’ ˙’ ’ (chˇ a .¯ ¯ˆ . o o a ¯. o ¯ aa o ooo . .ng cho c´c d` thi phˇng. Mˆt trong nh˜.ng d ac tru.ng d o s˜ d u.o.c x´t ˙ ’ ´ t´ chˆ t kh´c d ac tru ınh a a ¯ˇ a ¯ˆ . a o o u ¯ˇ ¯´ e ¯ . e . . . ` ´´ trong phˆn kˆ tiˆp. a ee -. ˙ ’ ´ Dinh l´ 6.4.6 Moi d` thi phˇ ng d` u 5−sˇc. y . ¯ˆ . a ¯ˆ o e a Ch´.ng minh. Hiˆ’n nhiˆn d inh l´ d ung cho c´c d` thi phˇng c´ sˆ d ınh ≤ 5. Gia su. khˇng ˙ ˙ ’ ˙ ’ ´’ o o ¯˙ ˙˙ ’’ u e e ¯. y ¯´ a ¯o . a ˆ a .ng minh d inh l´ c˜ng d ung cho ˙ ’ d .nh d ung cho moi d` thi phˇng c´ (n − 1) d ınh. Ta s˜ ch´ ¯˙’ ¯i ¯´ . ¯o . a ˆ o eu ¯. y u ¯´ .ng d` thi phˇng c´ n d ınh. ˙ ’ o ¯˙ ’ nh˜u ¯o . a ˆ 160
Thˆt vˆy, theo Hˆ qua 6.3.8, trong G tˆn tai d ınh v c´ bˆc ≤ 5. D` thi con nhˆn d u.o.c -ˆ . ` . ¯˙ e˙ ’ ’ aa o oa o a¯. .. . . . . G bˇ ng c´ch xo´ d ınh v v` c´c canh liˆn thuˆc n´ l` 5−sˇc; ta tˆ c´c d ınh cua n´ bˇ ng ` ´ ` a ¯˙’ o a ¯˙ ’ ˙ oa ’ t` u a a aa . e o oa a . . khi n´ kˆ v´.i nˇm d ınh mang nˇm m`u nˇm m`u α, β, γ, δ, . Ta c´ thˆ’ tˆ m`u d ınh v, tr` ˙ o ` o a ¯˙ o e o a ¯˙ ’ ’ a a u e a a kh´c nhau. a Trong tru.`.ng ho.p d ´, gia su. a, b, c, d, e l` nˇm d ınh kˆ v´.i v (theo th´. tu. v`ng quanh `o . ¯o ˙ ˙’’ a a ¯˙ ’ o e u.o . α, β, γ, δ, l` c´c m`u tu.o.ng u.ng. K´ hiˆu G l` d` thi con sinh bo.i tˆp ho.p a˙˙ ’’ ˙a ’. v ) v` gia su aa a ´ ye α,β a ¯oˆ. . . c´c d ınh c´ m`u α hay β, v.v. C´ hai tru.`.ng ho.p xay ra: a ¯˙ ’ ˙ ’ oa o o . 1. Nˆu a v` c khˆng thuˆc nh˜.ng th`nh phˆn cua d` thi Gα,γ th` trong th`nh phˆn ch´.a ´ ` ` a ˙ ¯ˆ . ’o e a o o u a ı a a u . .o.c lai. C´ch tˆ m`u m´.i cho G l` chˆ p ´ a ¯˙’ a ta tˆ m`u γ cho c´c d ınh c´ m`u α v` ngu . . oa oa a a oa o aa .o.c, v` d ınh v bˆy gi`. d u.o.c bao quanh bo.i c´c d ınh c´ m`u γ, β, γ, δ, nˆn c´ a ¯˙’ ˙ a ¯˙ ’ ’ nhˆn d u . a¯ a o¯ . oa eo . thˆ’ tˆ n´ bˇ ng m`u α. ˙ ` eooa a 2. Nˆu a v` c thuˆc c`ng mˆt th`nh phˆn cua d` thi Gα,γ th` c´c d ınh b v` d khˆng thˆ’ ˙ ´ ` a ˙ ¯ˆ . ’o ı a ¯˙ ’ e a ou o a a o e . . .i nhau trong d` thi G (v` nˆu ngu.o.c lai, G ch´.a d` thi K ). Khi ho´n vi c´c ´ ´ nˆi v´ oo ¯ˆ . β,δ ı e o u ¯o . 5 ˆ a .a .. ` n cua d` thi Gβ,δ (ch´.a d ınh b) ta c´ thˆ’ tˆ m`u β cho ˙o a ˙ ¯ˆ . ’o ˙ ’ m`u β v` δ trong th`nh phˆ a a a a u¯ oe d ınh v d u.o.c. ¯˙’ ¯. Dinh l´ d u.o.c ch´.ng minh. -. y¯ . u Tuy nhiˆn, ta c`n c´ thˆ’ l`m tˆt ho.n: ˙ ´ e o o ea o -. ´ ´’ ˙ ’ ` Dinh l´ 6.4.7 [Gia thuyˆt bˆn m`u] Sˇc sˆ cu a moi d` thi phˇ ng bˇ ng bˆn. ´´ ´ ˙ ’ ao˙ y eo a . ¯ˆ . a o a o Ch´.ng minh. Gia thuyˆt bˆn m`u xuˆ t hiˆn lˆn d` u tiˆn trong cuˆc trao d o’i gi˜.a Morgan ˙ ´´ ´ e ` ¯a ˙ ’ u eo a a .aˆ e o ¯ˆ u . .`.i hoc tr` cua ˆng v`o nˇm 1850. Sau d ´, Morgan d ˜ d` cˆp b`i to´n n`y v´.i o˙o ’ v` ngu o . a aa ¯o ¯a ¯ˆ a e. a a ao Hamilton trong mˆt b´.c thu. viˆt ng`y 23 th´ng 10 nˇm 1852. Kˆt qua l` rˆ t nhiˆu “ch´.ng ´ ´ ´ ` ˙aa ’ ou e a a a e e u . . c´c “phan v´ du” v` c´c gia thuyˆt kh´c c´ liˆn quan xuˆ t hiˆn (dˆ’ c´ thˆm ˙ ´ ´ e ¯e o e ˙ ı . aa ’ ˙ ’ minh” c˜ng nhu a u e a oe a . .ng thˆng tin chi tiˆt, xem [48]). Tuy nhiˆn, phai dˆn nˇm 1976, hai nh` to´n hoc ngu.`.i ´ ’´ ˙ ¯e a nh˜u o e e aa. o M˜ l` Appel v` Haken (xem [1]), su. dung h`ng ng`n gi`. trˆn m´y t´ d iˆn tu., d ˜ ch´.ng ˙. ’ a ınh ¯ e ˙ ¯a u ’ ya a a a oe . ´˙ ´´ ’ ˙ ’ minh t´ d ung d ˇn cua gia thuyˆt bˆn m`u. ınh ¯´ ¯a eo a Kiˆ’m tra t´ phˇ ng ˙ ˙ ’ 6.4.1 e ınh a Viˆc x´c d inh mˆt d` thi c´ phˇng hay khˆng l` mˆt b`i to´n c´ y ngh˜ Nhu. d a chı ra, ˙ ’ ¯˜ ˙ ’ e a ¯. o ¯ˆ . o a .o o a o a a o´ ıa. . . .ng cua Kuratowski v` Whitney cho ph´p kiˆ’m tra t´ phˇng cua d` thi. Tuy ˙ ˙ ’ ˙ ’ ˙ ¯o . ’ˆ c´c d ac tru a ¯ˇ a e e ınh a . nhiˆn c´c d ac tru.ng n`y khˆng ph` ho.p khi thu.c hiˆn trˆn m´y t´ do kh´ thˆ’ hiˆn bˇ ng ˙.a oee` e a ¯ˇ a o u. e e a ınh . . . .o.ng tr` ınh; ngo`i ra nˆu d` thi l` phˇng, th` c´c kˆt qua n`y khˆng chı ra phu.o.ng ph´p ˙ ’ ´ˆ ´ ˙a ’ ˙ ’ chu a e ¯o . a a ıa e o a 161
v˜ n´ nhu. thˆ n`o. Ngu.`.i ta biˆt rˇ ng [52], nˆu su. dung tiˆu chuˆ’n cua Kuratowski dˆ’ ˙ ˙ e` ´ ´a ´˙. ’ ˙ ’ eo ea o e e a ¯e .i gian thu.c hiˆn ´ nhˆ t l` O(n6 ). kiˆ’m tra t´ phˇng cua d` thi n d ınh (n > 5) th` th` ˙ ˙ ’ ´ ˙ ¯o . ¯˙ ’ˆ ’ e ınh a ıo e ıt a a . . C´ mˆt sˆ thuˆt to´n kiˆ’m tra t´ phˇng cua d` thi (xem [52] dˆ’ c´ tˆ’ng quan vˆ ˙ ˙ ˙ ˙ ’ .´ ` ˙ ¯o . ’ ooo a a e ınh a ˆ ¯e o o e . ´t qua n`y). Hˆu hˆt c´c phu.o.ng ph´p n`y ´p dung c´ch “xˆy du.ng ban d` ”: D` u ˙ ¯o - ˆ ` ´a ˙a ’ ’ c´c kˆ ae ae a aa a a ˆ a . . tiˆn, chon mˆt d` thi con phˇng g cua G v` biˆ’u diˆn n´ trˆn mˇt phˇng. (Trong hˆu hˆt ˙ ˙ ’ ˜oe ˙ ’ ` ´ ˙’ e o ¯o . ˆ a ae e a a ae . . . ınh). Sau d ´ thˆm c´c canh v`o d` thi g sao cho n´ khˆng c´c thuˆt to´n, g l` mˆt chu tr` a a a ao ¯o e a. a ¯o . ˆ oo . . cˇt c´c canh kh´c (ngoai tr`. tai c´c d ınh chung). Nˆu ch´ng ta th`nh cˆng khi biˆ’u diˆn˙ ´ ˜ ´ u . a ¯˙ ’ aa. a e u a o e e . .o.c lai kˆt luˆn G khˆng phˇng. ˙ ’ ˙ ’ lai th` d` thi G l` phˇng; ngu . . e ´a ı ¯o . ˆ aa o a . . Kh´ khˇn ch´ cua mˆt thuˆt to´n nhu. vˆy o. chˆ trong nh˜.ng giai d oan tru.´.c d o, .’˜ ınh ˙ ’ a˙ o oa o a a u ¯. o ¯´ . . . nh˜.ng kha nˇng c´ thˆ’ khˆng dˆ’ y dˆn c´c giai d oan sau n`y. ˙ ˙ ´ ˙a ’ viˆc thˆm c´c canh v`o g t` u e e a. a u o e o ¯e ´ ¯e a ¯. a . . bu.´.c n`o d o c´ thˆ’ dˆn dˆn khˆng thˆ’ d ˇt canh o. bu.´.c sau, mˇc d` ˙ a ¯e ˙ ¯a . ˜ ´ ˙ ’ ˙ ’ Mˆt c´ch d at canh o o a ¯ˇ . o a ¯´ o e o e. o au . . . d` thi d a cho l` phˇng. Chˇng han, trong H` 6.8(a), gia su. ta bˇt d` u v´.i d` thi con g l` ˙ ’ ˙ ’ ´a ˙˙ ’’ ¯o . ¯˜ ˆ aa a ınh a ¯ˆ o ¯ˆ . o a . chu tr` {v1 , v2 , v3 , v4 , v5 , v1 }. Sau d o ta thˆm c´c canh (v1 , v4 ), (v4 , v6 ), (v3 , v6 ) v` (v1 , v6 ) ınh ¯´ e a. a ` thi thu d u.o.c vˆ n phˇng. Hiˆ’n nhiˆn l` canh (v2 , v5 ) khˆng thˆ’ d at d u.o.c! T`. d ´ ˙ ˙ ¯ˇ ¯ . ˜ ˙ ’ sao cho d o . ¯ˆ ¯. a a e e a. o e. u ¯o ta cho rˇ ng d` thi khˆng phˇng. Tuy nhiˆn, d` thi n`y c´ thˆ’ biˆ’u diˆn phˇng nhu. trong ˙˙ ` ˙ ’ ˜ ˙ ’ a ¯ˆ . o o a e ¯ˆ . a o e e o e a H` 6.8(b). ınh v4 v4 • • ................................. .. . .. ................................. .. .. .. .. . .................................... ....................................... .......... .......... ......... ......... .. .. . . .. ........ ...... ...... .. . .. .. ...... ...... ... .... . ... . ..... ... ... . ..... ... ..... ..... ..... ..... ... .... ... .... ... ... ..... ..... . ..... ..... ... ... ... ..... ... ..... . ... ... . .. . . . .. . . ... ... . .... ... ... ... .... ... ... ... ... ... . ... ... . .... . . .... ... ... . ... . ... ... .. .. ... ... .. .. ... . .... .... . . . .. .. ... ... ... ... ... . ... ... .. .. ... .... .... . . ... . . ... ... .... ... ... .... ... . ... ... . . . . . ... .... . . . ... ... .... . . ... ... ... . . . ... ... . . . .... ... .... ... ... . . . ... . . ... ... . ... ... .... . . .... ... . ... ... . . ... . . . .... . . .... . . ... ... . ... ... ... . . ... ... . ... . . .... .... . . . . . ... ... ... . . v5 v3 v5 v3 . ... ... ... ... .... ... . . .... . . . . . . . . ... .... ... ... ... ... .... . . . ... ... ... . . . .... . . . ... .... . ... . ... .. ... ... .. ... . ... ... .. .. . ... ... • v6 ... . ... ... • • • • .. ... .. ...................................... ... ... ..................................... . .. .... .... .. .. .... . .. .. . . ......... . ......... .. .. ..... ..... . . . ............. .. . ......................... .. .. . .. . . .. • . ... ... . .. ... .. ... ....... .. .. .. .. .. .. .. ... ..... . .. .. .. .. . ... .. ... ... . .. ... .. ... .. .. ... .. ... .. .. .. .. . .. .. . . . ... ... . ... ... v6 .. .. .. . .. .. ... ... .. .. .. .. .. .. .. . . . ... ... . .. .. ... ... .. .. .. .. . ... ... .. .. .. .. .. .. .. . . . . ... ... .. .. . ... ... ... ... .. .. .. .. . .. .. ... ... ... ... .. .. .. .. .. .. . ... . .. .. ... .. .. . .. .. ... . ... .. .. .. .. . .... ... . . .. .. .. .. . ... ... . ... ........ .. .. .. .. .. .. . .. .. ... .. . .. . .. . . ... .. .. .. ...... .. ... .. .. .. .. .. .. .. .. .. . . . ... ... .. .. .. .. ... .. ... .. .. ... .. ... .. .. .. .. . . . ... . .. .. .. .. ... ... ... .. .. .. ... .. .. . .. . .. .. .. .. . .. . . ... ... ... ... .. .. .. .. ... .. .. .. .. .. ... .. .. .. ... ... .. . .. . . . .. . ... ... .. . .. .. . ... ... .. . ... .. . ... . . .... . .... . ......................................... ... . ... ......................................... .. • • • • ....................................... .. .. ..... ..................................... . .. .. .. .. . .. .. .. .... .. .. v1 v2 v1 v2 .. .. .. .. .. ... ... .. .. ... ... .. .. ... . ... ... ... ... ... .... .... .... .... ... ... ..... ..... ..... ..... ....... ....... ........................ ........................ (a) (b) H` 6.8: Hai c´ch biˆ’u diˆn cua c`ng mˆt d` thi. ˙ ˜˙u ’ ınh a e e o ¯o . .ˆ Dˆy ch´ l` mˆt tro. ngai cua phu.o.ng ph´p xˆy du.ng ban d` ; v` ta cˆn mˆt sˆ thu -a ` .´’ ˙ ’ .˙ ’ ˙ ¯o a ’ oo˙ ınh a o aa ˆ a . . ´ ˙ ’ tuc kh´c giai quyˆt. a e . Nhu. d ˜ biˆt, mˆt d` thi, n´i chung, c´ thˆ’ thu gon th`nh d` thi nho ho.n dˆ’ d o.n gian ˙ ˙ ´ ˙ ’ ˙ ’ ¯a e o ¯o . o .ˆ oe a ¯o . ˆ ¯e ¯ . .´.c thu gon khˆng anh hu.o.ng dˆn t´ phˇng (hoˇc khˆng ho´ tiˆn tr` kiˆ’m tra. C´c bu o ˙ ˙ ’ ´ ´ ˙ ’ ˙ ’ ae ınh e a o ¯e ınh a a o . . ˙ ’ phˇng) cua d` thi. ˙ ¯ˆ . ’o a 162
1. Kiˆ’m tra t´ liˆn thˆng cua d` thi. Nˆu d` thi khˆng liˆn thˆng, x´t t`.ng th`nh ˙ ´o ˙ ¯ˆ . ’ e ınh e o o e ¯ˆ . o e o eu a ` phˆn liˆn thˆng. ae o 2. Xo´ c´c khuyˆn, v` thay tˆ t ca c´c canh song song bo.i d ung mˆt canh. ´’ a ˙a . ˙ ¯´ ’ aa e a o. . 3. Xo´ c´c d ınh bˆc hai v` ho.p nhˆ t hai canh liˆn thuˆc d ınh n`y. Lˇp lai c´c Bu.´.c 2 ´ a a ¯˙ ’ o ¯˙ ’ a a. a e a a.a o . . . . v` 3 cho dˆn khi khˆng thˆ’ r´t gon thˆm. ˙ ´ a ¯e o eu . e ´ 4. Ap dung Thuˆt to´n Tremaux-Tarjan dˆ’ phˆn hoach d` thi th`nh c´c th`nh phˆn ˙a ` a a ¯e ¯o . a ˆ a a a . . . .o.c . khˆng t´ch d u . o a¯ 5. V´.i mˆi th`nh phˆn khˆng t´ch d u.o.c, thu.c hiˆn ph´p thu gon su. dung c´c Bu.´.c 3 ˜ ` ˙. ’ o o a a o a ¯. e e a o . . . v` 2 cho dˆn khi khˆng thˆ’ thu gon thˆm. ˙ ´ a ¯e o e e . 6. V´.i mˆ i th`nh phˆn khˆng t´ch d u.o.c c´ n d ınh, m canh, kiˆ’m tra c´c bˆ t d ang th´.c ˙ ˜ ´˙ ’ ` a ¯ . o ¯˙ ’ oo a a o e a a ¯ˇ u . n ≥ 5, m ≥ 9, m ≤ 3n − 6. Nˆu c´c r`ng buˆc n`y khˆng thoa m˜n, thuˆt to´n kˆt th´c; ngu.o.c lai kiˆ’m tra th`nh ˙ ´ ´u ˙a ’ eaa oa o a ae ..e a . . .o.c kh´c. Moi d` thi c´ n < 5 hoˇc m < 9 l` phˇng, v` moi d o.n ˙ ’ ` phˆn khˆng t´ch d u . a o a¯ a ¯ˆ . o o a aa a .¯ . . ˙ ’ d` thi c´ m > 3n − 6 khˆng phˇng. ¯ˆ . o o o a Mˆi d` thi khˆng t´ch d u.o.c c´ thˆ’ t´ch th`nh c´c th`nh phˆn 3−liˆn thˆng. Su. dung ˙ ˜o ` ˙. ’ o ¯ˆ . o a ¯. o ea a a a a e o -ˆ . a a ˙ ’ kˆt qua cua Tutte [54]: D` thi l` phˇng nˆu v` chı nˆu tˆ t ca c´c th`nh phˆn 3−liˆn thˆng ´ ´ ’´ ´ ’ ` ˙˙ ’’ e a ˙e a ˙a e o a a e o ˙ a n´ l` phˇng. Tuy nhiˆn, phu.o.ng ph´p n`y khˆng hiˆu qua bˇ ng thuˆt to´n cua Hopcroft ˙ ’ ˙` ’ oa a ’a ˙ ’ cu e aa o e a a . . v` Tarjan sau d ˆy. a ¯a Thuˆt to´n Hopcroft-Tarjan a a . Thuˆt to´n kiˆ’m tra t´ phˇng cua d` thi rˆ t ph´.c tap. Do d o ch´ng ta s˜ chı tr` b`y ˙ ˙ ’ ´ ˙ ¯ˆ . a ’o e ˙ ınh a ’ a a e ınh a u. ¯´ u . .ng d ˇc tru.ng cˆt yˆu. Dˆ’ hiˆ’u thuˆt to´n ch´ o e -e e ˙˙ ´´ ˙. ’ nh˜ u ¯a a a ınh, x´t thu tuc phˆn r˜ sau ´p dung cho e aa a . . . .n d` thi khˆng t´ch d u.o.c G c´ n d ınh v` m canh. o ¯˙ ’ c´c d o ¯ˆ . o a¯ o a ¯. a . ` Phˆn r˜ chu tr` aa ınh-dˆy chuyˆn: a e a a ¯˙ ’ ˙ ’ 1. T` chu tr` µ trong G. G´n g = µ. G´n nh˜n c´c d ınh v` c´c canh cua g l` v1 , v2 , . . . , ım ınh a a aa . a .o.ng u.ng. Dˇt i = 1. -a v` e1 , e2 , . . . , tu a ´ . 2. Nˆu c´ mˆt canh n`o cua G chu.a c´ nh˜n th` t` mˆt dˆy chuyˆn µi bˇt d` u v` kˆt ´ˆ ´ ` ´ a˙ ’ eoo. oa ı ım o a e a ¯a a e . . .o.c g´n nh˜n nhu.ng dˆy chuyˆn n`y chı gˆm nh˜.ng canh chu.a ` ` u . a ¯˙ ’ ˙o ’ th´c tai c´c d ınh d u . a ¯ a a e a u . d u.o.c g´n nh˜n. Lu.u tr˜. µi . Nˆu tˆ t ca c´c canh d a d u.o.c g´n nh˜n, chuyˆ’n sang ˙ ´´’ e a ˙a . ¯. a a u ¯˜ ¯ . a a e .´.c 4. Bu o 163
3. Dˇt g = g ∪ µi ; v` i = i + 1. G´n nh˜n c´c canh v` c´c d ınh chu.a d u.o.c g´n nh˜n trong -a a a ¯˙ ’ a a aa. ¯. a a . g v` chuyˆ’n sang Bu.´.c 2. ˙ a e o 4. Xuˆ t g v` c´c dˆy chuyˆn µ1 , µ2 , . . . , µe . D`.ng. ´ ` a aa a e u C´ thˆ’ ch´.ng minh rˇ ng [52] thu tuc trˆn s˜ phˆn r˜ d o.n d` thi khˆng t´ch d u.o.c G ˙ ` ˙. ’ oeu a e e a a¯ ¯o . o ˆ a ¯. th`nh mˆt chu tr` v` e = m − n dˆy chuyˆn. V` chu tr` c´ thˆ’ xem l` kˆt nˆi cua hai ˙ ` ´´’ ae o ˙ a o ınh a a e ı ınh o e . dˆy chuyˆn khˆng c´ chung canh, nˆn G d u.o.c phˆn r˜ th`nh m − n + 2 dˆy chuyˆn. Cˆn ` ` ` a e o o e ¯. aaa a e a . ` ng, mˇc d` phˆn r˜ trˆn l` khˆng duy nhˆ t, nhu.ng sˆ c´c dˆy chuyˆn d u.o.c phˆn ´ ´a a ` ¯. ch´ y rˇ u´ a auaaeao a o e a . r˜ t`. G l` hˇ ng sˆ. Chˇng han, H` 6.8, x´t hai phˆn r˜ sau th`nh mˆt chu tr` v` bˆn a` ˙ ’ ´ ´ au a o a ınh e aa a o ınh a o . . ` n: (10 − 6 = 4) dˆy chuyˆ a e {v1 , v2 , v3 , v4 , v5 , v1 }, {(v1 , v4 )}, {(v2 , v5 )}, {(v4 , v6 ), (v1 , v6 )}, {(v3 , v6 )}, v` a {v1 , v2 , v3 , v4 , v5 , v1 }, {(v4 , v6 ), (v3 , v6 )}, {(v1 , v6 )}, {(v1 , v4 )}, {(v2 , v5 )}. ınh-dˆy chuyˆn, ch´ng ta c´ thˆ’ biˆ’u diˆn chu tr` µ ˙˙ ˜ ` Trong qu´ tr` phˆn r˜ chu tr` a ınh a a a e u oee e ınh ˙ ng, v` tiˆp tuc thˆm c´c dˆy chuyˆn m´.i µ1 , µ2 , . . . , khi ch´ng d u.o.c sinh ra. ’ ´. ` trˆn mˇt phˇ e a a ae e aa e o u ¯. . Mˆt dˆy chuyˆn µi m´.i hoˇc s˜ phˆn chia mˆt diˆn d ang tˆn tai th`nh hai diˆn m´.i hoˇc ` `. oa e o aea o e¯ o a e o a . . . . . . ˙ ng khi thˆm n´ v`o g. Do ch´ng ta thˆm tu` y, nˆn c´ thˆ’ ˙ ’ ´ s˜ khiˆn cho g ∪ µi khˆng phˇ e e o a e oa u e y´ e o e . trong H` 6.8. Dˆ’ giai quyˆt kh´ khˇn n`y, ta c´ thˆ’ hoˇc -e ˙ ˙’ ˙. ´ ˙ ’ xay ra t` trang nhu ınh . ınh e oaa oea 1. Tiˆp tuc thˆm c´c dˆy chuyˆn cho dˆn khi khˆng thˆ’ thu.c hiˆn d u.o.c n˜.a. Sau d o tro. ˙ ´ ` ´ ¯´ ˙’ e. e aa e ¯e o e. e¯. u . .a c´ch biˆ’u diˆn kh´c (t´.c l` d`ng phu.o.ng ph´p lˆn ngu.o.c) thay ˙ ˜ ´m chon lu a ` lai t` kiˆ . ım e e e a uau aa .. . cho qu´ tr` tru.´.c d ´; hoˇc l` a ınh o ¯o aa . 2. Tiˆp tuc t` c´c dˆy chuyˆn kh´c nhau nhu.ng khˆng d at ch´ng v`o µ, cho dˆn khi ´ ` ´ e . ım a a e a o ¯ˇ u a ¯e . .o.c diˆn m` mˆt dˆy chuyˆn cˆn d u.o.c d at v`o, hoˇc l` biˆt chˇc rˇ ng khˆng c´ ´a ` ` ` ¯ . ¯ˇ a ´ t` d u . ım ¯ e aoa ea aae a o o . . . . tro. ngai v´.i diˆn m` d at dˆy chuyˆn v`o. ` ˙’ oe a ¯ˇ a ea . . . C´ mˆt sˆ thuˆt to´n tiˆp cˆn theo hu.´.ng th´. nhˆ t, nhu.ng Hopcroft v` Tarjan tiˆp .´ ´. ´ ´ ooo a a ea o u a a e . . hai v` d ˜ ch´.ng minh rˇ ng thuˆt to´n cua ho l` hiˆu qua ho.n. Y ch´ ´ ınh ` a˙ ’ ˙ ’ cˆn theo c´ch th´ a a u a ¯a u a a .a e . . . . nhˆp nhˇ ng khi thˆm c´c dˆy chuyˆn; cu thˆ’ l`: ˙a ` ´ ` ˙ ’ aaa˙ ’ cua thuˆt to´n n`y l` giai quyˆt su a a e. a e aa e .e . . Gia su. rˇ ng o. bu.´.c n`o d ´, ch´ng ta c´ mˆt dˆy chuyˆn µi (trˆn d ınh cua mˆt danh ˙˙` ` ’’a ˙ ’ e ¯˙’ ˙ ’ o a ¯o u ooa e o . . .a c´c dˆy chuyˆn cˆn xu. l´) m` ch´ng ta cˆn giai quyˆt su. nhˆp nhˇ ng cua n´. ` `` ` ´ ˙y ’ ˙’ ˙ ’o s´ch ch´ a a a u ea au a e. a a . . a v` b l` c´c d ınh xuˆ t ph´t v` kˆt th´c cua dˆy chuyˆn n`y. C´c tru.`.ng ho.p kh´c ´ ´ ` ˙˙ ’’ a a a ¯˙ ’ u˙a ’ Gia su a a ae ea a o a . nhau c´ thˆ’ xay ra v` phu.o.ng ph´p xu. l´ tu.o.ng u.ng s˜ d u.o.c tr` b`y du.´.i d ˆy. C´c t` ˙’ oe˙ ˙y ’ a a ´ e¯ . ınh a o ¯a a ınh huˆng n`y d u.o.c giai th´ du.a v`o H` 6.9. ´ ˙’ o a¯. ıch . a ınh 1. Nˆu khˆng tˆn tai dˆy chuyˆn kh´c Pi v` ch´.a hai d ınh a v` b. ´ `.a ` ¯˙’ e o o e a au a 164
(a) Nˆu stack kh´c trˆng th` lu.u tr˜. Pi v` giai quyˆt su. nhˆp nhˇ ng cua dˆy chuyˆn ` ´ ´ ´ ` a˙ ’ ˙a ’ e ao ı u e. a a e . ´´ kˆ tiˆp trong stack. ee (b) Ngu.o.c lai (stack bˇ ng trˆng) th` thˆm Pi v`o g ; giai quyˆt su. nhˆp nhˇ ng cua ` ` ´ ´ ˙ ’ ˙ ’ a o ıe a e. a a .. . ` ´´ dˆy chuyˆn kˆ tiˆp trong stack. a e ee 2. Ngu.o.c lai gia su. Pj l` dˆy chuyˆn (kh´c Pi ) ch´.a hai d ınh a v` b (xem H` 6.9(a)). ` ˙˙ ’’ ¯˙’ aa e a u a ınh .. . lai P trong danh s´ch. Xˆy du.ng dˆy chuyˆn P xuˆ t ph´t t`. d ınh x n`o d ´ trˆn ` ´ ˙ ’ Gi˜ . i u a a a eka a u¯ a ¯o e . Pi v` nˇ m gi˜.a a v` b (gia su. Pk kˆt th´c tai y ). ` ´ ˙˙ ’’ aa u a e u. ´ ` (a) Nˆu y thuˆc Pk (xem H` 6.9(b)) th` d at dˆy chuyˆn Pk trˆn Pi v`o stack v` e o ınh ı ¯ˇ a e e a a . . ` ng cua dˆy chuyˆn Pk . ´ ` ˙ ’ ˙a ’ giai quyˆt t´ nhˆp nhˇ e ınh a a e . (b) Ngu.o.c lai v` nˆu y khˆng thuˆc Pj (H` 6.9(c)) th` dˆy chuyˆn Pi d ˜ d u.o.c giai. ´ ` ˙ ’ . . ae o o ınh ıa e ¯a ¯ . . ˙ i stack. Giai su. nhˆp nhˇ ng cua dˆy chuyˆn kˆ tiˆp trong stack. ` ` ´e ´ ’ ˙. ’ ˙a ’ Loai Pi kho a a ee . . (c) Ngu.o.c lai nˆu y nˇ m gi˜.a a v` b (H` 6.9(d)) th` lu.u tr˜. Pk . Tiˆp tuc giai t´ ` ´ ´ ˙ ınh ’ ..e a u a ınh ı u e. nhˆp nhˇ ng cua dˆy chuyˆn Pi bˇ ng c´ch tao dˆy chuyˆn kh´c gi˜.a a v` b. ` ` ` ` ˙a ’ a a e a a a e a u a . . .o.c lai (H` 6.9(e)), lu.u tr˜. P . Tiˆp tuc giai t´ nhˆp nhˇ ng cua dˆy chuyˆn ` ´ ` ˙ ınh a ’ ˙a ’ (d) Ngu . . ınh uk e. a e . .a y v` b. ` ` Pi bˇ ng c´ch tao dˆy chuyˆn kh´c gi˜ a a a e a u a . Trong H` 6.9(a), dˆy chuyˆn µi c´ thˆ’ xoay tai hai d ınh a v` b, v` do d o s˜ phˆn ˙ ` ¯˙ ’ ınh a e oe a a ¯´ e a . .´.i” dˆy chuyˆn µ . Su. nhˆp nhˇ ng n`y cˆn d u.o.c xu. l´. Dˆ’ giai ˙ y -e ˙ ˙’ ` ` ` ¯. ’ d oi diˆn “trˆn” hoˇc “du o ¯ˆ e e a a e a a aa . . . . j .ng mˆt dˆy chuyˆn µ xuˆ t ph´t t`. d ınh x n`o d o trˆn dˆy chuyˆn µ . ´ ` ´ ` a u ¯˙’ quyˆt, ta xˆy du e a oa e a a ¯´ e a e . . k i .a c´c canh chu.a d u.o.c g´n nh˜n v` kˆt th´c ngay khi n´ gˇp mˆt d ınh ` ´ o ¯˙ .’ (Dˆy chuyˆn µk ch´ a . a e u ¯. a a ae u oa . d u.o.c g´n nh˜n, chˇng han y ). ˙ ’ ¯. a a a . Nˆu ca hai d ınh x v` y cua dˆy chuyˆn µk thuˆc dˆy chuyˆn µi nhu. trong H` 6.9(b), ´’ ` ` e˙ ¯˙’ ˙a ’ a e oa e ınh . ˙ d u.o.c xoay tai hai d ınh x v` y v` do d ´ s˜ phˆn d oi diˆn ph´ “trˆn” hoˇc ph´ ’¯ . ˙ ’ th` µk c´ thˆ ı oe ¯ a a ¯o e a ¯ˆ e ıa e a ıa . . . “du.´.i” dˆy chuyˆn µi . V` vˆy ch´ng ta khˆng nh˜.ng cˆn xu. l´ cho µi m` tru.´.c hˆt c`n ` ` ´ ˙y ’ o a e ıa u o u a a oeo . phai giai quyˆt su. nhˆp nhˇ ng cho ca dˆy chuyˆn m´.i µk . Do d ´ cˆn cˆ t µk sau khi cˆ t µi ` ´ ` ¯o ` a a´ ´ ˙ ’ ˙ ’ ˙a ’ e. a a e o a . trong mˆt ngˇn xˆp, v` ta bˇt d` u xu. l´ tu.o.ng tu. µi d oi v´.i µk . ´a ´ ´ ˙y ’ o ae a a ¯ˆ ¯ˆ o . . Kha nˇng kh´c l` d ınh y khˆng nˇ m trˆn hai dˆy chuyˆn µi v` µj nhu.ng lai thuˆc ` ` ˙a ’ a a ¯˙’ o a e a e a o . . ` n kh´c nhu. trong H` 6.9(c). Trong tru.`.ng ho.p n`y dˆy chuyˆn µi khˆng ` mˆt dˆy chuyˆ oa e a ınh o aa e o . . thˆ’ xoay sang ph´ bˆn kia, v` do d ´ khˆng c´ su. nhˆp nhˇ ng vˆ diˆn m` dˆy chuyˆn n`y ˙ ` `e ` e ıa e a ¯o o o. a a e. aa ea . phˆn chia. a Nhu. trong H` 6.9(d), nˆu d ınh cuˆi cua dˆy chuyˆn µk nˇ m trˆn dˆy chuyˆn µj gi˜.a ` ´’ ´’ ` ` e ¯˙ o˙a ınh e a ea e u .i µ ) vˆ n c´ thˆ’ xoay tai a v` b. Do d ´ vˆ n c´ su. ˙ ˜ ˜ ` ¯˙ ’ hai d ınh a v` b th` dˆy chuyˆn µi (c`ng v´ k a o e a ıa e u o a ¯o a o . . nhˆp nhˇ ng d ˆi v´.i dˆy chuyˆn µi . Tuy nhiˆn khi d o dˆy chuyˆn µk phˆn d oi diˆn x´c d .nh ` ¯o o a ´ ` ` a a e e ¯´ a e a ¯ˆ e a ¯i . . bo.i chu tuyˆn (a, x, b, y, a) khˆng c´ su. nhˆp nhˇ ng. V` vˆy, ch´ng ta cˆn mˆt dˆy chuyˆn ` ´ ` ` ˙ ’ e o o. a a ıa u a oa e . . . . mˆt d ınh trˆn µ dˆ’ giai quyˆt su. nhˆp nhˇ ng v´.i µ . ˙˙ ` ´ ´ kh´c xuˆ t ph´t t` o ¯˙ au. ’ e i ¯e ’ a a e. a a oi . 165
µi •......................•......................•......................•......................• .. . .. .. ... .. .. .. .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . •...........................................................................•.......................................................................................................•...........................................................................• (a) . ... .. . .. . .. . . . .. . µj a b µk •.......................•......................• . . .. .. .. . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . •......................•......................•......................•......................• . ... ... . .. . . . ... .. .. . .. . . . . . . . x µi y ......... . . . . . . . . . . . •...........................................................................•...................................................•......................................• (b) . .............................................................................................. .. . .. . .. .. . . µj a b µk •.......................• •......................•......................• . . .. . . ... .. .. . . . . . . . . . . . . . . . µi . . . . . . . . . . . . . . . . . . . . . . . . y •.......................• . . . . . . • • • • • . .. . . . . . . . ...................................................... . ..................................................... . . . . . . . . . . . . . x . . . . . . . . . . . . . . . . . . . . . . . . . .......................... ............................................................................................. . • • • • (c) . . . . ......................................................................................................................... . . . µj a b x µi •......................•......................•......................•......................• .. . ... . . ... .. .. .. .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • • • . . . .............. . . . ............. . . . . . . . . . . . . . . . µk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..................................................... ....................................... • • • • • (d) . .............................................................................................. . . . . ........................................ . ........................................ . µj y a b µk •......................•......................•......................• .. . .. .. ... .. .. . . . . . . . . . . µi . . . . . . . . . . . . . . . . . . • • • • • • . . ...................................................... . . . . .................................................... . . . . . . . . . . . . x . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • • • • (e) . . . ......................................................................................................................... . ......................................... ............................................................................................. .............. . µj y a b ` ˙a ’ ˙ ’ ˙a ’ H` 6.9: Phˆn t´ c´c kha nˇng xay ra cua dˆy chuyˆn µi . ınh a ıch a e Cuˆi c`ng, trong tru.`.ng ho.p dˆy chuyˆn µk c´ d ınh y nˇ m trˆn dˆy chuyˆn µj nhu.ng ` ´ ` ` o ¯˙ ’ ou o a e a ea e . ` m ngo`i d oan x´c d .nh bo.i a v` b nhu. trong H` 6.9(e). Dˆy chuyˆn µi vˆn c´ thˆ’ xoay. ˙ ˜oe ` ˙ ’ nˇ a a ¯ . a ¯i a ınh a e a .ng kh´c v´.i tru.`.ng ho.p cua H` 6.9(b), khˆng c´ su. nhˆp nhˇ ng cua dˆy chuyˆn µ ` ` ˙ ’ ˙a ’ Nhu ao o ınh o o. a a e . . k .o.ng u.ng v´.i µ . Do d o, cˆn t` mˆt dˆy chuyˆn m´.i dˆ’ giai quyˆt su. nhˆp nhˇ ng cua ˙˙ ` ¯´ ` ım o a ` ´ o ¯e ’ ˙ ’ tu ´ oi a e e. a a . . dˆy chuyˆn µi v` dˆy chuyˆn m´.i n`y c´ thˆ’ xuˆ t ph´t t`. mˆt d ınh bˆ t k` trˆn dˆy chuyˆn ˙´ ` ` ´ ` a u o ¯˙ .’ a e aa e oaoea aye a e . rˆng dˆy chuyˆn µ dˆn d ınh y trˆn µ . ` ´’ ˙. ’ e i ¯e ¯ ˙ y, a, x, b; ngo`i ra ta c˜ng mo o a u a ej T´m lai, thuˆt to´n kiˆ’m tra t´ phˇng cua d` thi gˆm c´c thu tuc: ˙ ˙ ’ ˙ ¯ˆ . ` ’o ˙. ’ o a a e ınh a o a . . 1. T` c´c th`nh phˆn khˆng t´ch d u.o.c; ` ım a a a o a ¯. 2. Phˆn hoach c´c th`nh phˆn khˆng t´ch d u.o.cth`nh c´c dˆy chuyˆn; ` ` a a a a o a ¯. a aa e . 166
3. X´c d inh vi tr´ dˆ’ thˆm c´c dˆy chuyˆn n`y; v` ˙ ` a ¯. . ı ¯e e aa ea a 4. Xˆy du.ng mˆt biˆ’u diˆn phˇng. ˙ ˜ ˙ ’ a o e e a . . Su. dung thuˆt to´n t` kiˆm theo chiˆu sˆu dˆ’ giai quyˆt c´c Bu.´.c 1 v` 2. C´c dˆy chuyˆn ˙’ ´ ` a ¯e ˙ ´ ` ˙. ’ a a ım e e ea o a aa e . .o.c tao bo.i hai bu.´.c trˆn c´ nh˜.ng t´ chˆ t th´ ho.p cho c´c tiˆn tr` vˆ sau. Th`.i ´ ´ ınh ` ˙ ’ du . . ¯ o eou ınh a ıch . ae e o gian d `i hoi trong mˆ i bu.´.c (ngoai tr`. Bu.´.c 4) tı lˆ v´.i n. Th`.i gian xˆy du.ng mˆt biˆ’u ˙ ˜ ¯o ˙ ’ ˙e o ’. o o u o o a o e . . . .i gian thu.c hiˆn cua thuˆt to´n l` O(n log n) (do cˆng ˜ ˙ ’ e˙ ’ diˆn phˇng l` O(n log n). V` vˆy th` e a a ıa o a aa o . . . . .c Euler, sˆ canh m tı lˆ v´.i sˆ d ınh n trong mˆt d` thi phˇng).˙ ’ ´. ´’ ˙ e o o ¯˙ ’. th´u o o ¯ˆ . a .o Thuˆt to´n n`y c`n c´ thˆ’ cai thiˆn tˆt ho.n v´.i th`.i gian thu.c hiˆn l` O(n) (xem ˙’ ´ a a o o e˙ a eo o o ea . . . . [34]). -o ˜ ´ 6.5 Dˆi ngˆu h` hoc a ınh . X´t d` thi phˇng liˆn thˆng G khˆng c´ d ınh cˆ lˆp. Khi d o ta c´ thˆ’ thiˆt lˆp mˆt d` thi ˙ ea ˙ ’ ´. o ¯˙’ e ¯ˆ . a o e o o oa ¯´ oe o ¯o . .ˆ . . sau: bˆn trong mˆ i diˆn s cua R(G) d at mˆt d ınh s∗ cua G∗ ; v´.i mˆ i canh e ˙ ’ ˜. ˜ ∗ ˙ ’ o ¯˙ ’ ˙ ’ phˇng G nhu a e oe ¯ˇ oo. . . cua G thiˆt lˆp tu.o.ng u.ng mˆt canh e∗ cua G∗ bˇ ng c´ch nˆi c´c d ınh s∗ v` t∗ tu.o.ng u.ng ` ´. ´ ˙ ’ ˙ ’ o a ¯˙ ’ ea ´ o. a a a ´ . -ˆ . ˜ c´c diˆn s v` t trˆn hai ph´ cua canh e trong R(G). D` thi G∗ goi l` d oi ngˆ u (tˆ pˆ) cua ´ ıa ˙ . ’ oo ˙ ’ a e a e o a ¯ˆ a . . ˜ ´ ˙ ’ G (hay c`n goi l` d oi ngˆ u h` hoc cua G). o . a ¯ˆ a ınh . V´ du 6.5.1 D` thi G (d u.`.ng liˆn n´t) v` d oi ngˆu cua n´ (d u.`.ng d u.t n´t) cho trong -ˆ . ˜ ` ´ ˙ ’ o ¯o ı. o ¯o e e a ¯ˆ a ¯´ e H` 6.10. ınh • ... .... . ... .. .. . . . . . ... .. . .. . . .. . .. . .. . . .. .. . .. . .. .. . . .. . . .. . .. .. . .. . . .. .. .. .. .. .. ... .. . .. .. . .. . .. .. . . . .. .. . .. . . . .... . .. .. . .. . .. . . .. . .. . . .. . . .. . . . .. . . . . .. . . . .. . . . .. •••. . . . . ...... .. . . .. ....... ....... ....... ... . ....... ...... . ... .. . .. ... ...... ... ...... .... . ..... ... ..... .... .. ..... . .. ... .... . .. .. . . .. ... . .. ... . .. . ... . .. ... .. ... .. . ... .. .. ... . .. . ... . ... ... ... . .. .. ... .. ... ... ... .. .. .. ... .. ... . .. . ... . ... ... . .. ... .... .. • .. .... . ... . ... . ... ... ... ... ... .. .. ... . ... . .... . . . ... . . ... .. .. . .. . ... ... ... ... . .. ..... ... .. ... . .. ... . . ... . .. . .. . . .. . .. ..... ... .. . ... . . .. • .. .. .. .. .. ... .. .. ..... .. . ..... . . ... . . .. . . ... .. ...... . ....... ... .. .. .. . .. . . .. . . . . .... .......... ... .. ... . .. ... . ..... .......... .... .. . . .. .... . . . .... . . . ........ .. . . ........ • • ... .. . . . .. . ......................................................................... . . ........................................................................ . . . . . . . . . .. . . . .. .. .. . ... .. .. .. . .. . .... ... .. .. . .. . . .... ... ... .. . .... ... . ... . . .. . ..... ... . .. .... ... ... .... ....... . ....... ....... .... . • . ...... .... ... ...... . . H` 6.10: ınh Mˆt chu tr` so. cˆ p cua R(G) chia mˇt phˇng th`nh hai v`ng liˆn thˆng kh´c trˆng ˙ ’ ´˙ ´ ’ o ınh a a a a u e o a o . . .i nhau. Bo d i tˆ t ca c´c canh d oi ngˆ u tu.o.ng u.ng c´c canh trˆn chu tr` n`y s˜ phˆn ˜ ´’ ´ ˙¯ a ˙ a . ’ v` r` ao ¯ˆ a ´ a. e ınh a e a 167
hoach R(G∗ ) th`nh hai th`nh phˆn liˆn thˆng. N´i c´ch kh´c, mˆ i chu tr` so. cˆ p cua G, ˜ ` ´˙ ’ a a ae o oa a o ınh a . .o.ng u.ng mˆt d ˆi chu tr` so. cˆ p cua G∗ , v` ngu.o.c lai. T´ chˆ t n`y rˆ t ˜ ´ ´ ´’ ´ ´ a˙ qua d oi ngˆ u, tu ¯ˆ a ´ o ¯o ınh a ınh a a a . .. .u ´ v` ta c´ thˆ’ t` mˆt d oi chu tr` cua G bˇ ng c´ch t` mˆt chu tr` cua G∗ . ˙ ` ´ ınh ˙’ ınh ˙ ’ h˜ ıch ı u o e ım o ¯ˆ a a ım o . . R˜ r`ng c´ mˆt su. tu.o.ng u.ng mˆt-mˆt gi˜.a c´c canh cua d` thi G v` d` thi d oi ngˆ u ˜ ´ ˙ ¯ˆ . ’o oa oo. ´ o oua. a ¯o . ¯ˆ ˆ a . . . .i mˆt canh cua G. Ho.n n˜.a ch´ng ta c´ mˆt v`i nhˆn x´t sau: ∗ ∗ ˙ ’ ˙ ’ G −mˆt canh cua G giao v´ o . o. o u u ooa ae . . . . 1. Canh l` khuyˆn trong G tu.o.ng u.ng canh treo trong G∗ . a e ´ . . 2. Canh l` canh treo trong G tu.o.ng u.ng khuyˆn trong G∗ . a. ´ e . 3. Nˆu G c´ d iˆ’m kh´.p th` G∗ c˜ng c´ d iˆ’m kh´.p. ˙ ˙ ´ e o ¯e o ı u o ¯e o 4. C´c canh trong chuˆi cua G tu.o.ng u.ng c´c canh song song trong G∗ . ˜’ o˙ a. ´ a. 5. C´c canh song song trong G tu.o.ng u.ng c´c canh trong chuˆi cua G∗ . ˜’ o˙ a. ´ a. 6. Sˆ c´c canh tao th`nh biˆn trong diˆn F cua G, bˇ ng bˆc cua d ınh tu.o.ng u.ng trong ` ´ ˙ ’ a ˙ ¯˙ ’ ’ oa . a e e a ´ . . . .o.c lai. ∗ G v` ngu . . a -ˆ . ˙ ’ 7. D` thi G∗ l` phˇng. o aa 8. D` thi d oi ngˆ u cua G∗ l` G; t´.c l` (G∗ )∗ = G. - ˆ . ¯ˆ ˜˙ ´ ’ o a a ua 9. Nˆu k´ hiˆu n, m v` f l` sˆ c´c d ınh, canh v` diˆn tu.o.ng u.ng cua d` thi phˇng liˆn ˙ ’ ´ ´ a o a ¯˙ ’ ˙ ¯o . a ’ˆ eye a ae ´ e . . . ˜ thˆng G, v` k´ hiˆu n , m v` f l` sˆ c´c d ınh, canh v` diˆn cua d` thi d ˆi ngˆ u G∗ ´ ´ ∗ ∗ ∗ a o a ¯˙ ’ a e ˙ ¯ˆ . ¯o ’o o ay e a a . . . tu.o.ng u.ng, th` ´ ı n∗ = f, m∗ = m, f ∗ = n. V´ du 6.5.2 X´t mˆt mang vˆn tai phˇng (vˆ hu.´.ng) G m` mˆ i canh e c´ kha nˇng thˆng ˙ ’ ˜ a˙ .’ o ˙a ’ ı. eo a oo ao. o . . ˙nh v`o s v` d ınh ra t d u.o.c xˆp trˆn c`ng mˆt d u.`.ng nˇ m ngang. Ta lˆp d` ` ´ ’ ˙ ’ qua c(e) ≥ 0, d ı ¯ a a¯ ¯. e eu o¯o a a ¯o ˆ . . thi d ˆi ngˆ u G∗ bˇ ng c´ch cho hai d ınh kh´c nhau s∗ v` t∗ tu.o.ng u.ng v´.i diˆn vˆ han cua ˜ ` ´ ¯˙ ’ ˙ ’ ¯o a a a a a ´ o e o. . . G : d ınh s∗ u.ng v´.i nu.a mˇt phˇng du.´.i, d ınh t∗ u.ng v´.i nu.a mˇt phˇng trˆn. G´n trong ˙ ’ ˙’ ¯˙ ’ o˙ ’ o ¯˙ ’ o˙ ’ ´ a a ´ a a e a . . . .o.ng w(e∗ ) = c(e) cho canh e∗ (´.ng v´.i e). Bˆy gi`. ta x´t c´c b`i to´n sau: lu . u o a o eaaa . B`i to´n 1. Trong G t` thiˆt diˆn A c´ kha nˇng thˆng qua nho nhˆ t; t´.c l` l`m cu.c ´e ´ ˙a ’ ˙ ’ a u aa a a ım e o o . . ˙u ’ tiˆ e c(A) = c(v ). v ∈A B`i to´n 2. Trong G∗ t` d u.`.ng d i ngˇn nhˆ t µ∗ d i t`. s∗ dˆn t∗ ; t´.c l` l`m cu.c tiˆ’u ˙ ´ ´ ´ a a ım ¯ o ¯ a a ¯u ¯e u aa e . w(µ∗ ) = w(v ∗ ). v ∗ ∈µ∗ 168
B`i to´n 1 tu.o.ng d u.o.ng v´.i b`i to´n t` luˆng l´.n nhˆ t; B`i to´n 2 tu.o.ng d u.o.ng v´.i o a a ım ` ´ aa ¯ o o a aa ¯ o .`.ng d i ngˇn nhˆ t v` r˜ r`ng d ˆi v´.i d` thi phˇng th` ca hai b`i to´n d o l` ´ ˙’ ´ ´ ı˙’ b`i to´n t` d u o a a ım ¯ ¯ a a a o a ¯o o ¯ˆ . a o a a ¯´ a mˆt. o . B`i to´n bˆn m`u c`n c´ thˆ’ ph´t biˆ’u du.´.i dang d oi ngˆ u l`: c´ thˆ’ tˆ c´c diˆn cua ˙ ˙ ˙ ˜ ´ ´ e˙ ’ aao aooea e o. ¯ˆ a a o eoa . ˙ ’ ` mˆt d` thi phˇng G bˇ ng bˆn m`u sao cho khˆng c´ hai diˆn kˆ nhau c´ c`ng mˆt m`u. ´ e` o ¯ˆ . a .o a o a o o e ou o a . . ˜ T´ duy nhˆ t cu a d` thi d oi ngˆu ´ ˙ ¯ˆ . ¯ˆ ´ ’ ınh a o a ˜˙ ˜ Vˆ n d` d at ra l` d ˆi ngˆ u cua mˆt d` thi l` duy nhˆ t? N´i c´ch kh´c, c´c d` thi d oi ngˆ u ´ e. ´ ´ ´ ’ a ¯ˆ ¯ˇ a ¯o a o ¯ˆ . a .o a oa a a ¯ˆ . ¯ˆ o a . phu.o.ng ph´p xˆy du.ng cua d` thi d oi ngˆ u, du.`.ng ˙ ’ ˜ cua mˆt d` thi d ˜ cho l` d ˇng cˆ u? T` ´ ´ ˙ ’ ˙ ¯o . ¯ˆ ’ˆ o ¯o . ¯a .ˆ a ¯a a u aa a o . . ho.p l´ cho rˇ ng mˆt d` thi phˇng G c´ duy nhˆ t d` thi d ˆi ngˆ u nˆu v` chı nˆu n´ c´ ` ˙ ’ ˜ e a ˙e oo ´ ¯o . ¯o ´ ´ ’´ nhu . y a o ¯ˆ . a .o o aˆ a mˆt biˆ’u diˆn phˇng (trˆn mˇt phˇng hoˇc mˇt cˆu) duy nhˆ t. ˙ ˜ ˙ ’ ˙ ’ a` ´ o e e a e a a a a a . . . . V´ du 6.5.3 Hai d` thi trong H` 6.11 l` d ang cˆ u v´.i hai biˆ’u diˆn phˇng kh´c nhau. ˙ ˙ ’ ˜ ˙ ’ ´ ı. ¯ˆ . o ınh a ¯ˇ ao e e a a .o.c lai, c´c d` thi d oi ngˆ u cua hai d` thi n`y khˆng d ang cˆ u nhu. trong H` 6.12. ˜˙ ˙ ’ ´ ´ ’ Ngu . . a ¯ˆ . ¯ˆ o a ¯ˆ . a o o ¯ˇ a ınh e5 ...........................•............................ e6 ... .. . .... . .... .... .... .... e7 .... .... .... .... .... .... .... .... .... .... .... .... .... .. .... ..................................................................... ....................................................................... •.............................................................................................................................................................................................• • • ..... .. ... .. .. .... .. ..... . . . . .. . . .. . . . . . e....6............................ ......... ... . . . ... . e7 . . . . . ... . .... . . ... . .... . . . . .... ... . .... ... . . . . . . . .... . . . .... . . . . ... ... . .... .. ... ... e5 .................................................... .................. ......... . . .... . .... . . . . ... . . ... . . . . . . . . . ... . . ... . . • .............. . . . . . . ... . . ... . . . . . . . . . . . ... . . ... . . . . . . . . . . . . ... . ... . . . . . . . . . . . . ... . ... . . ... . . . ... . . . . .. . . . . .. . . . ... . . . ... ... . ... . . . . . . . . . ... ... . . . . ... ... . . . . . . . . . . ... ... . . . ... ... e4 e3 e1 e4 e3 e1 . . . . . . . . . . . . ... ... . . ... ... . . . . . . . . . . . . ... ... . . ... ... . . . . . . . . . . . . ... ... . . . ... ... . . . . . . . . . . . . ... ... . . ... ... . . . . . . . . . . . . ... ... . . . ... ... . . . . . . . . . . . ... ... . . . ... ... . . . . . . . . . . . . ... ... ... ... . . . . . . . . . . . . . ... ... . ... ... . . . . . . . . . . . . . . . ... ... . . ... ... . . . . . . . . . . . ... ... . . . ... ... . . . . . . . . . . . ... ... . . . . ... ... . . . . . . . . . . ... ... . . . . . ..... ... . . . . . . . . .. . .... . ... . ..... . . .. . . . .. . . . . .... .. ...... . . . ..... .. . . • • • • ........................................................................ ........................................................................ . . .. .. ........................................................................ ........................................................................ e2 e2 H` 6.11: Hai biˆ’u diˆn kh´c nhau cua c`ng mˆt d` thi. ˙ ˜ ˙u ’ ınh e e a o ¯ˆ . .o a -. Tuy nhiˆn c´c d` thi trong H` 6.12 l` 2−d ang cˆ u. Dinh l´ sau tˆ’ng qu´t v´ du n`y. ˙ ˙ ’ ´ e a ¯o .ˆ ınh a ¯ˇ y o aı.a -. ˜ ˙ ’ ˙ ’ Dinh l´ 6.5.4 Tˆ t ca c´c d` thi d ˆi ngˆ u cu a mˆt d` thi phˇ ng G l` 2−d ˇ ng cˆ u; v` moi ´’ ´ ´ a ˙ a ¯ˆ . ¯o a˙ ’ y o o ¯ˆ . a .o a ¯a a a. .i mˆt d ˆi ngˆ u cu a G c˜ng l` mˆt d ˆi ngˆ u cu a G. ˙ ’ ˜˙ ˜˙ d` thi 2−d ˇ ng cˆ u v´ ´ .´ .´ ’ ’ ¯ˆ . o ¯a ao o ¯o a u a o ¯o a V` mˆt d` thi phˇng 3−liˆn thˆng c´ biˆ’u diˆn duy nhˆ t trˆn mˇt cˆu, nˆn d oi ngˆ u ˙ ˙ ’ ˜ ˜ ´e a` ´ ı o ¯o . a .ˆ e o oe e a .a e ¯ˆ a ˜ ˙ ’ cua n´ l` duy nhˆ t. N´i c´ch kh´c, tˆ t ca c´c d ˆi ngˆ u cua d` thi 3−liˆn thˆng l` d ˇng ´ ´’ ´ ˙ ’ oa a a ˙ a ¯o ˙ ¯o . ’ a oa a ˆ e o a ¯a ´ cˆ u. a 169
• • ............ ....... ..... ......... ...... ...... ... .. . . ..... ..... . .. .... .... .. . . .. . .... .... . .. . ... ... .. .. . .. .. . ... ... ... ... .. . .. .. . ... ... ... ... .. . .. . . . . . . . . . .. .. .. .. . . . .. .. . . . . . .. .. . . . .. .. .. . . . . . . . . . e∗ e∗ e∗ .. .. . . .. . .. .. . . . . . . . . .. . . . .. .. .. . . . . . . . 5 . 6 7 . . e∗ . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 5 . . . . .. . . . . . . . . .. . . . . .. . . . .. .. . . . . .. . . . .. .. . . . .. .. . . . . ... . . . . .. . e∗ e∗ . . .. ... . • • . . . . . . . . . . . ....... .. ....... ...... ...... . . . . . 7 6 . . ... ... ... ... . . .. ... .... ... .... . . . . . . . .. ... ... . . ... ... .. ... ... . . ... ... . . . ... ... .. . . ... .. ... ... . . ... ... . .. e∗ e∗ e∗ . . .. . . . . ... ... .. ... ... ... ... ... ... . . . . . ... ... ... ... ... ... . . .. ... ... 4 3 . 3 . . . . ... ... . . ... ... ... ... . . .. ... ... . . . ... ... . . ... ... . . .. ... ... . . ... ... .. . . ... ... ... ... . . . . ... ... ... .. ..... . . ... ... . . . ... ... e∗ . . . . .. .. . ... . . ... ... . .. ..... ... ... ... . . . ... ... ... ... ... . .. ..... ... . . 4 . .. .. . e∗ e∗ . . ..... ... ... . ... ... . . . .. .... . .... . . ... ... ... ... ... . . . . . ... . ...... . .... . .... 2 2 ... ... ... ... ..... . .. .... ... ......................................................................... .... ... • • • • .. ...................................................................... . .. ... ........................................................................ .. ........................................................................ ... . . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . .. . .. .. .. .. .. .. .. .. .. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. .. .. .. . .. .. .. .. .. .. .. .. ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. . .... .... .... ... .... .... .... .... . . .... .... .... .... ..... ..... ..... ..... ...... ...... ...................... ...................... ....... ....... .................. .................. e∗ e∗ 1 1 (a) (b) -o -o ˜ ˙ ¯o . ˜ ˙ ¯ˆ . H` 6.12: (a) Dˆi ngˆu cua d` thi trong H` 6.11(a). (b) Dˆi ngˆ u cua d` thi trong H` ´ ´ ’ˆ ’o ınh a ınh a ınh 6.11(b). Dˆi ngˆu tˆ’ ho.p -o ˙ ˜ ´ 6.6 ao. Trong c´c phˆn tru.´.c ch´ng ta d a d inh ngh˜ v` thao luˆn vˆ d oi ngˆu cua c´c d` thi phˇng ˜’ ˙ ’ ` a ` ¯ˆ . e ´ a ˙ a ¯ˆ . a ıa a ˙ ’ a a o u ¯˜ ¯. o .o.ng d u.o.ng cua kh´i ` u ınh . ` ´ ˙ ’ theo ngh˜ thuˆn t´y h` hoc. Phˆn n`y cung cˆ p mˆt d .nh ngh˜ tu ıa a aa a o ¯i ıa ¯ a . ˜u khˆng phu thuˆc v`o c´c kh´i niˆm h` hoc. Tru.´.c hˆt ta c´ ´ ´ niˆm d ˆi ngˆ e ¯o a o oaa ae ınh . oe o . . . . -. -` Dinh l´ 6.6.1 Diˆu kiˆn cˆn v` d u dˆ’ hai d` thi phˇ ng G1 v` G2 l` d ˆi ngˆ u cu a nhau ’˙ ˙ ’ ˜ e` ´ a a ¯ ˙ ¯e ˙ ’ y e ¯ˆ . a o a a ¯o a . .o.ng u.ng mˆt-mˆt gi˜.a c´c canh trong G v` c´c canh trong G sao cho mˆt a`. l`: Tˆn tai tu o ´ ooua. 1aa o . . . . 2 ´u v` chı’ nˆu tˆp tu.o.ng u.ng trong G2 tao ´a tˆp c´c canh trong G1 tao th`nh mˆt chu tr`nh nˆ a ˙ e . aa. a o ı e ´ . . . . ´e th`nh mˆt thiˆt diˆn. a o e . . Ch´.ng minh. Diˆu kiˆn cˆn. X´t mˆt biˆ’u diˆn phˇng cua d` thi G. Ch´ng ta c˜ng v˜ mˆt -` ˙ ˜ ˙ ’ e` ˙ ¯ˆ . ’o u e .a e oe e a u u eo . . ´i ngˆu (h` hoc) G∗ cua G. X´t mˆt chu tr` µ t`y y trong G. Hiˆ’n nhiˆn, chu tr` µ ˙ ˜ ˙ ’ do ¯ˆ a ınh . e o ınh u´ e e ınh . s˜ tao th`nh mˆt d u.`.ng cong d ong d o.n n`o d o trong mˇt phˇng biˆ’u diˆn cua G v` phˆn ˙ ˙ ’ ˜˙ ’ e. a o ¯o ¯´ ¯ a ¯´ a a e e aa . . - inh l´ Du.`.ng cong Jordan). Do d o c´c d ınh cua G∗ d u.o.c -o ˙ ’ ¯´ a ¯˙ ’ ˙’ chia mˇt phˇng th`nh hai v`ng (D. a a a u y ¯. . ´ng r`.i nhau-mˆt bˆn trong µ v` mˆt bˆn ngo`i µ. phˆn hoach th`nh hai tˆp con kh´c trˆ a a a a o o oe aoe a . . . . N´i c´ch kh´c, tˆp c´c canh µ∗ trong G∗ tu.o.ng u.ng tˆp µ trong G l` mˆt thiˆt diˆn trong ´e oa aaa. ´ a ao e . . . . G∗ . (Khˆng tˆp con thu.c su. n`o cua µ∗ l` thiˆt diˆn cua G∗ ; tai sao?). Tu.o.ng tu., hiˆ’n ˙ ´ ˙’ ˙ ’ o a .a a e e e . . . . . .i mˆ i thiˆt diˆn S ∗ trong G∗ tˆn tai duy nhˆ t mˆt chu tr` gˆm tˆp c´c canh e` o˜ ´e `. ´o ınh ` nhiˆn rˇ ng v´ o a e o a oaa. . . . .o.ng u.ng S trong G sao cho S l` mˆt chu tr` tu ´ ao ınh. . 170
Diˆu kiˆn d u. Gia su. G l` d` thi phˇng v` G l` d` thi m` c´ tu.o.ng u.ng mˆt-mˆt gi˜.a c´c -` ˙ ’ e ¯˙ ’ ˙˙ ’’ e a ¯ˆ . a o a a ¯ˆ . a o o ´ o oua . . . thiˆt diˆn trong G v` c´c chu tr` trong G v` ngu.o.c lai. Gia su. G∗ l` d` thi d ˆi ngˆ u cua˜ ´e ´ ˙˙ ’’ a˙’ e aa ınh a a ¯o . ¯o ˆ . .. .o.ng u.ng mˆt-mˆt gi˜.a c´c chu tr` trong G v` c´c thiˆt diˆn trong ´e G. Khi d o c´ mˆt tu ¯´ o o ´ o oua ınh aa e . . . . .a c´c thiˆt diˆn trong G v` c´c chu tr` trong G∗ . Do d o tˆn tai tu.o.ng u.ng mˆt ´e `. G, v` gi˜ a au e aa ınh ¯´ o ´ o . . mˆt gi˜.a c´c chu tr` cua G v` G∗ m` d iˆu n`y chı ra rˇ ng G v` G∗ l` 2−d ang cˆ u (Dinh a -. ` ˙ ’ a ¯` ´ ınh ˙ ’ ˙ ’ oua a ea a a a ¯ˇ . -. ˜˙ l´ 1.5.3). Theo Dinh l´ 6.5.4, d` thi G l` mˆt d ˆi ngˆu cua G. ´ ’ y y ¯ˆ . o a o ¯o a . -o ˜ Dˆi ngˆu cua d` thi con ´ ˙ ¯ˆ . ’ a o Gia su. G l` d` thi phˇng v` G∗ l` d oi ngˆ u cua n´. Gia su. a l` mˆt canh cua G v` canh ˙ ’ ˜ ´ ˙˙ ’’ ˙o ’ ˙˙ ’’ ˙ ’ a ¯ˆ . a o a a ¯ˆ a ao. a. . .o.ng u.ng n´ trong G∗ l` a∗ . Bˆy gi`. ta xo´ canh a khoi d` thi G v` t` d ˆi ngˆ u cua d` ˜ ˙ ¯ˆ ´ ˙ ¯o . ’ˆ ’o tu ´ o a a o a. a ım ¯o a .p nhˆ t hai diˆn n`y ´ ´ e˙ ’ thi G \ {a}. Nˆu a l` canh biˆn cua hai diˆn, th` viˆc xo´ canh a s˜ ho e a. e ıe a. e. a ea . . . . ˙ nhˆn d u.o.c t`. G∗ bˇ ng c´ch xo´ canh ’ a ¯. u ˜ ` l`m mˆt. Do d ´ d` thi d oi ngˆ u (G \ {a}) c´ thˆ ´ ∗ a o ¯o ¯o . ¯ˆ ˆ a oe a a a. . . tu.o.ng u.ng a∗ v` sau d ´ d` ng nhˆ t hai d ınh m` a∗ liˆn thuˆc trong G∗ \ {a∗ }. Mˇt kh´c nˆu ´ ´ ¯˙’ ´ a ¯o ¯oˆ a a e o a ae . . .`.ng ho.p n`y G∗ \ {a∗ } ch´ ` ∗ canh a khˆng nˇ m trˆn biˆn, th` a l` mˆt khuyˆn. Trong tru o o a e e ı ao e a ınh . . . ˜ ˜ ˙ ¯ˆ . ´u d` thi G c´ mˆt d ˆi ngˆ u G∗ th` d ˆi ngˆ u cua d` thi con cua G c´ ´ ´ ∗ ’o ˙ ’ l` (G \ {a}) . Do d o nˆ ¯o . a ¯´ e ˆ o o ¯o a ı ¯o a o . thˆ’ nhˆn d u.o.c bˇ ng c´ch ´p dung mˆt sˆ lˆn thu tuc n`y. ˙. e a¯. ` o o` ´a ˙. a ’ a aa . . -o ˜ Dˆi ngˆu cua d` thi d` ng phˆi ´ ˙ ¯ˆ . ¯ˆ ’ a o o o Gia su. G l` d` thi phˇng v` G∗ l` d oi ngˆ u cua n´. Gia su. a l` mˆt canh cua G v` canh ˙ ’ ˜ ´ ˙˙ ’’ ˙o ’ ˙˙ ’’ ˙’ a ¯ˆ . a o a a ¯ˆ a ao. a. . .o.ng u.ng n´ trong G∗ l` a∗ . Bˆy gi`. ta thˆm mˆt d ınh m´.i c´ bˆc bˇ ng hai nˇ m trˆn canh ooa ` ` o ¯˙’ tu ´ o a a o e a a e. . . a v`o G (t´.c l` a tro. th`nh hai canh trong chuˆi). Khi d o d oi ngˆ u cua d` thi m´.i nhˆn ˜ ˜ ´ ˙a ’ ˙ ¯ˆ . o ’o a ua o ¯´ ¯ˆ a a . . .o.c ch´ l` thˆm canh song song v´.i a∗ v`o d` thi G∗ . Tu.o.ng tu. xu. l´ ngu.o.c lai bˇ ng ` ˙y ’ du . ¯ ınh a e o a ¯ˆ . o a . . .. c´ch r´t gon chuˆi s˜ tu.o.ng u.ng v´.i xo´ mˆt canh song song trong G∗ . Do d ´ nˆu G c´ mˆt ˜ ´ a u. oe ´ o ao. ¯o e oo . . ´i ngˆu G∗ , th` moi d oi ngˆ u cua d` thi d` ng phˆi v´.i G∗ c´ thˆ’ nhˆn d u.o.c t`. G∗ bˇ ng ˙ a ¯. u ˜ ˜ ` ´ ˙ ¯o . ¯ˆ ’ˆ do ¯ˆ a ı . ¯ˆ a o oo oe a . phu.o.ng ph´p trˆn. a e Dˆn nay ch´ng ta m´.i chı nghiˆn c´.u d oi ngˆu cua c´c d` thi phˇng. D´ l` v` moi -e -o a ı . ˜ ˙ ’ ´ ´ ˙ ’ ˙ a ¯o . a ’ u o e u ¯ˆ a ˆ d .nh ngh˜ cua kh´i niˆm d oi ngˆu phu thuˆc v`o c´ch biˆ’u diˆn phˇng cua d` thi trˆn mˇt ˙ ˜ ˜ ˙ ’ ´ ıa ˙ ’ ˙ ¯ˆ . e ’o ¯i a e ¯ˆ a oaa e e a a . . . . e -. phˇng. Tuy nhiˆn, Dinh l´ 6.6.1 cho ph´p ch´ng ta c´ thˆ’ d .nh ngh˜ lai kh´i niˆm n`y m` ˙ ˙ ’ a y e u o e ¯i ıa . ae a a . ˙u diˆn trˆn mˇt phˇng; cu thˆ’ l` tu.o.ng u.ng gi˜.a c´c chu tr` ’ ˙a ˜ ˙ ’ khˆng phu thuˆc v`o c´ch biˆ o oaa e e e a a .e ´ ua ınh . . . v` c´c thiˆt diˆn. Kh´i niˆm n`y c´ thˆ’ mo. rˆng cho c´c d` thi khˆng phˇng? N´i c´ch ˙ ’. ˙ ’ ´e a o e ˙o aa e ae a ¯ˆ . o o a oa . . kh´c, v´.i d` thi khˆng phˇng G, c´ tˆn tai mˆt d` thi G tu.o.ng u.ng mˆt-mˆt gi˜.a c´c canh ˙ ’ o ` . o ¯o . a o ¯ˆ . o o a o .ˆ ´ o oua. . . ˙ a ch´ng sao cho moi chu tr` trong G tu.o.ng u.ng duy nhˆ t v´.i mˆt thiˆt diˆn trong G , ´o o ´e ’ cu u ınh ´ a e . . . v` ngu.o.c lai? Cˆu tra l`.i l` khˆng do kˆt qua sau ´ ˙o a o ’ ˙ ’ a a e .. -. - ˆ . o ¯o ˜´ ˙ ’ Dinh l´ 6.6.2 [Whitney] D` thi c´ d ˆi ngˆ u nˆu v` chı’ nˆu n´ phˇ ng. ´ ´ a e a ˙e o a y o 171
Ch´.ng minh. Ch´ng ta chı cˆn ch´.ng minh d iˆu kiˆn cˆn. T´.c l` ta s˜ ch´.ng minh d` thi ˙` ¯` e` ’a u u u e .a ua eu ¯o . ˆ . G l` d` thi khˆng phˇng. Khi d ´ theo Dinh l´ -. ˙ ’ ˜ ˙ ’ ´ ˙˙ ’’ khˆng phˇng s˜ khˆng c´ d oi ngˆ u. Gia su o a eo o ¯ˆ a a ¯ˆ . o o a ¯o y .a K hoˇc K hoˇc mˆt d` thi con d` ng phˆi v´.i mˆt trong hai d` thi Kuratowski, G ch´ u a a o ¯ˆ . .o ¯ˆ o oo o ¯ˆ . o . . . 5 3,3 ` ˜ ´t rˇ ng, G c´ mˆt d oi ngˆ u chı nˆu moi d` thi con g cua G v` moi d` thi d` ng ´ ’´ ˙e ˙ ’ n`y. Ta biˆ a a e o o ¯ˆ a . ¯o . ˆ a . ¯o . ¯o ˆ ˆ . phˆi v´.i g c´ mˆt d oi ngˆ u. Do d o nˆu ch´ng ta ch´.ng minh d u.o.c ca hai d` thi Kuratowski ˜ ´a ´ ¯. ˙ ’ oo o o ¯ˆ ¯´ e u u ¯ˆ . o . K5 v` K3,3 d` u khˆng c´ d oi ngˆ u th` d .nh l´ d u.o.c ch´.ng minh. Ta s˜ ch´.ng minh phan ˜ ´ ˙ ’ a ¯ˆ e o o ¯ˆ a ı ¯i y¯ . u eu .ng nhu. sau: ch´ u (a) Gia su. K3,3 c´ mˆt d ˆi ngˆu D. Nhˆn x´t rˇ ng c´c thiˆt diˆn trong K3,3 tu.o.ng u.ng c´c ˜ ae` .´ ´e ˙˙ ’’ o o ¯o a a a e ´ a . . .o.c lai (Dinh l´ 6.6.1). Do K khˆng c´ thiˆt diˆn gˆm hai canh -. ´e` chu tr` trong D v` ngu . . ınh a y o o e .o . 3,3 nˆn D khˆng c´ chu tr` d o d`i hai. T´.c D khˆng c´ c´c canh song song. Do moi chu e o o ınh ¯ˆ a u o oa . . . tr` trong K3,3 c´ d ˆ d`i bˆn hoˇc s´u nˆn D khˆng c´ thiˆt diˆn v´.i sˆ canh ´ ho.n bˆn. ´ ´ e oo. ´ ´ ınh o ¯o a o aae o o e ıt o . . . V` vˆy, bˆc cua c´c d ınh trong D ´ nhˆ t bˇ ng bˆn. Nhu.ng D khˆng c´ canh song song v` ıt a ` ´a ´ a ˙ a ¯˙ ’ ’ ıa o o o. a . . .n ho.n a ˙ a ¯˙ ıt a ` ˜’ ´a ´ ´ ’ ’ o ıt a a ¯˙ ’ o ¯˙ bˆc cua c´c d ınh ´ nhˆ t bˇ ng bˆn nˆn D c´ ´ nhˆ t nˇm d ınh, mˆ i d ınh c´ bˆc l´ oe oao . . ` ng bˆn. T´.c l` D c´ ´ nhˆ t (5 × 4)/2 = 10 canh. Diˆu n`y mˆu thuˆn v` K3,3 c´ -` ˜ ´ ´ hoˇc bˇ aa o ua o ıt a ea a aı o . . ˜ ˙ ou ˜ ´ ´ ’ ˙ o ın . ’ ch´ canh v` d ˆi ngˆu cua n´ c˜ng phai c´ ch´ canh. Do d o K3,3 khˆng c´ d oi ngˆu. ın . a ¯o a ¯´ o o ¯ˆ a (b) Gia su. K5 c´ mˆt d oi ngˆ u l` H. Ch´ y rˇ ng K5 c´ ˜ ` ´ ˙˙ ’’ o o ¯ˆ aa u´ a o . 1. 10 canh; . 2. khˆng c´ canh song song; o o. 3. khˆng c´ thiˆt diˆn v´.i hai canh; v` ´eo o o e a . . ´e ´ ˙oo ’ 4. c´c thiˆt diˆn chı c´ bˆn hoˇc s´u canh. a e aa. . . Suy ra d` thi H c´ ¯ˆ . o o 1. 10 canh; . 2. khˆng c´ d ınh bˆc nho ho.n ba; o ¯˙’ ˙ ’ o a . 3. khˆng c´ cˇp canh song song; o oa . . ´ 4. c´c chu tr` c´ d o d`i bˆn hoˇc s´u. a ınh o ¯ˆ a o aa . . Khi d o H ch´.a mˆt luc gi´c (mˆt chu tr` c´ d ˆ d`i s´u), v` khˆng c´ ho.n ba canh ¯´ u o. a o ınh o ¯o a a ao o . . . . m` khi thˆm v`o luc gi´c s˜ khˆng tao th`nh chu tr` d o d`i ba hoˇc mˆt cˇp canh song a e a. aeo a ınh ¯ˆ a a oa. . . . .. song. Nhu.ng d iˆu n`y khˆng thˆ’ xay ra trong H v` H c´ 10 canh, nˆn H c´ ´ nhˆ t bay ˙’ ¯` ´’ e˙ o ıt a ˙ ea o a o e . -` ˜ ¯˙ ´` ˜ ¯e´ ´ ˙nh. Bˆc cua mˆ i d ınh n`y ´ nhˆ t bˇ ng ba. Diˆu n`y dˆ n dˆn H c´ ´ nhˆ t 11 canh-mˆu ’ ˙ ’ ’ dı ¯ a o a ıt a a eaa o ıt a a . . ˜ thuˆn. a 172
Chu.o.ng 7 ˙ ’ Mang vˆn tai a . . Mo. d` u ˙ ¯ˆ ’a 7.1 Mˆt trong nh˜.ng b`i to´n l´ th´ v` quan trong cua l´ thuyˆt d` thi l` x´c d inh gi´ tri l´.n ´o ˙y ’ o u a a y ua e ¯ˆ . a a ¯. a .o . . ´t cua luˆng d u.o.c truyˆn t`. mˆt d ınh nguˆn s cua d` thi dˆn mˆt d ınh d´ t. Trong ` ` u o ¯˙ ` ´ ˙ ’ ’ ˙ ¯o . ¯e ’ ˙ ’ nhˆ a o ¯. e o ˆ o¯ ¯ıch . . khung canh d o, mˆ i cung (vi , vj ) cua d` thi G d u.o.c gˇn v´.i mˆt kha nˇng thˆng qua qij l` ˜ ´ ˙ ’ ˙ ¯o . ’ˆ ˙a ’ ¯´ o ¯. a o o o a . .o.ng luˆng l´.n nhˆ t c´ thˆ’ tai qua cung n`y. B`i to´n n`y v` nh˜.ng cai biˆn cua n´ ˙˙ ´ ` ´ ao e’ ˙ ’ ˙o ’ sˆ lu . o o o a a aaau e ´t nhiˆu u.ng dung trong thu.c tˆ, chˇng han, x´c d .nh mˆt d o giao thˆng l´.n nhˆ t gi˜.a ˙ ’ `´ ´a ´u c´ rˆ oa e .e a ¯i a ¯ˆ o o a . . .. hai v`ng trong ban d` giao thˆng d u.o.c biˆ’u diˆn bo.i mˆt d` thi. Trong v´ du n`y, l`.i giai ˙ ˜ ˙ ¯ˆ ’ ˙ ’ ˙’ u o o ¯. e e o ¯ˆ . o ı.ao . ` ng l´.n nhˆ t c˜ng chı ra nh˜.ng no.i “bao ho`” trˆn mang giao thˆng v` tao ´u ˙aa ’ ˙ ’ ˙ ’ cua b`i to´n luˆ o o a u a e o a. . mˆt “tˇc ngh˜n” khi luˆng tˆp trung v`o gi˜.a hai vi tr´ n`o d o. ´ ` o a e o a a u ı a ¯´ . . . Phu.o.ng ph´p giai b`i to´n luˆng l´.n nhˆ t t`. s dˆn t d u.a ra lˆn d` u tiˆn bo.i Ford ` ´ ´ ` ¯ˆ ˙a ’ ˙ ’ a a o o a u ¯e ¯ a a e ˙ a ho l` co. so. cho nh˜.ng thuˆt to´n kh´c giai ’ ˙ ’ ˙ ’ v` Fulkerson [27] v` k˜ thuˆt “g´n nh˜n” cu a ay a a a .a u a a a . . .ng vˆ n d` liˆn quan. C´ mˆt sˆ cai biˆn cua b`i to´n luˆng l´.n nhˆ t: ´ ´e . ´’ e ˙ a a ` ´ ooo˙ ’ quyˆt nh˜ e u a ¯ˆ e o o a 1. Gia su. rˇ ng mˆ i cung cua d` thi khˆng chı d u.o.c gˇn v´.i kha nˇng qij cho biˆt cˆn trˆn ˙˙` ˜ ´ ´. ’’a ˙ ¯o . o ’ˆ ˙¯ . a o ’ ˙a ’ o ea e .´.i cua luˆng trˆn cung ` ` cua luˆng trˆn cung (vi , vj ) m` c`n “kha nˇng” rij cho cˆn du o ˙ ˙ ’ ˙a ’ ’ o e ao a o e . .`.ng ho.p nhu. vˆy, khˆng phai l´c n`o mˆt tˆp chˆ p nhˆn d u.o.c c´c gi´ ´ ˙u a ’ n`y. Trong tru o a a o oa a a¯. a a . . .. . ` ` ˙ ’ ˙au ’ tri cua luˆng c˜ng thoa m˜n c`ng l´c hai r`ng buˆc n`y. Tuy nhiˆn-n´i chung-nhiˆu o u u a oa eo e . . luˆng thoa d iˆu kiˆn n`y, v` nˆu ngo`i c´c kha nˇng c`n c´ c´c chi ph´ cij tu.o.ng u.ng ` ˙ ¯` ´ ’e ˙a ’ o ea ae aa o oa ı ´ . mˆt d o.n vi luˆng doc theo c´c cung, th` b`i to´n tro. th`nh t` luˆng chˆ p nhˆn d u.o.c ` ım ` ´ ˙a ’ o¯ o a ıa a o a a¯. . . . . v´.i chi ph´ nho nhˆ t t`. s dˆn t. ´ ´ ˙ ’ a u ¯e o ı 2. X´t tru.`.ng ho.p d `i hoi luˆng l´.n nhˆ t gi˜.a moi cˇp d ınh. Mˇc d` b`i to´n n`y c´ . ¯o ˙ ` ´u ’ . a ¯˙ ’ e o o o a a ua aao . . thˆ’ giai bˇ ng n(n − 1)/2 lˆn lˇp c´c b`i to´n luˆng l´.n nhˆ t t`. s dˆn t nhu.ng c´ch ˙’a e˙` `aaa ` ´ ´ a. a o o a u ¯e a .o.ng tu. v´.i t` tˆ t ca c´c d u.`.ng d i ngˇn nhˆ t, o. d ˆy c˜ng cˆn ´ ´’ ´’ ` . o ım a ˙ a ¯ o a ˙ ¯a u l`m n`y qu´ thˆ! Tu a a ao ¯ a a 173
mˆt thuˆt to´n chuyˆn dung dˆ’ giai n´-v` trong tru.`.ng ho.p d` thi vˆ hu.´.ng, phu.o.ng ˙’ ¯e ˙ o a o a a e o . ¯ˆ . o o o . . . ph´p giai quyˆt n´ khˆng liˆn quan dˆn l`.i giai cua b`i to´n luˆng l´.n nhˆ t gi˜.a hai ´ ´ ` ´u ˙ ’ ˙˙aa ’’ a eoo e ¯e o o o a ¯˙’ d ınh s v` t. a ´ ` a o ¯˙ ¯ıch, .´ ` aoo .´ o ¯˙ .’ .’ ˙a ’ 3. Nˆu thay cho mˆt d ınh nguˆn v` mˆt d ınh d´ ta khao s´t mˆt sˆ nguˆn v` mˆt sˆ e o oo o .i c´c h`ng ho´ kh´c nhau gi˜.a hai tˆ’ ho.p nguˆn-d´ kh´c nhau, th` b`i to´n ˙. ` ¯ıch a d´ v´ a a ¯ıch, o aa u o o ıa a cu.c d ai tˆ’ng sˆ tˆ t ca c´c luˆng t`. c´c nguˆn dˆn c´c d´ l` b`i to´n luˆng d a-h`ng ˙ oa ˙a ` ´´ ’ ` ¯e a ¯ıch a a a o´ ` ¯. o o ua o¯a . ho´. Trong b`i to´n n`y, kha nˇng qij cua cung (vi , vj ) l` cˆn trˆn cua tˆ’ng c´c luˆng ˙ a` ˙a ’ ˙ ’ e˙o ’ a aaa aa o . .i c´c loai h`ng ho´ trˆn cung d ´. v´ a o .a ae ¯o 4. Gia thiˆt (ˆ’n) trong tˆ t ca c´c tru.`.ng ho.p trˆn l` sˆ lu.o.ng luˆng dˆn bˇ ng sˆ lu.o.ng ´˙ o ¯e ` ´’ ´ ` ´a ´ ˙’ a ˙a ea o e ao . o. . .`.ng ho.p luˆng ra khoi mˆt cung bˇ ng ` ` ´ ´ ` ˙˙ ’’ ˙ ’ luˆng ra. Nˆu ta bo gia thiˆt n`y v` x´t tru o o e e a ae o o a . . .i mˆt sˆ nguyˆn khˆng ˆm n`o d o, th` b`i to´n luˆng l´.n nhˆ t (t`. ` ´ .´ ` ´ luˆng dˆn nhˆn v´ o o o ¯e ao e oa a ¯´ ıa a o o au ´n t) d u.o.c xem nhu. b`i to´n trong c´c d` thi v´.i c´c lo.i nhuˆn. Trong dang n`y, s dˆ ¯e ¯. aa a ¯ˆ . o a . o a a . . c´c luˆng c´ thˆ’ “d u.o.c sinh ra” hoˇc “bi hˆ p thu” bo.i d` thi, v` do vˆy luˆng v`o s ˙ a` ´ ` ˙ ¯o . a ’ˆ o o e¯. a a a o a . . . . v` luˆng ra khoi t c´ thˆ’ thay d ˆ’i ho`n to`n d oc lˆp. ˙ ˙ a` ˙ ’ o oe ¯o a a ¯ˆ a.. C´c b`i to´n vˆ luˆng d u.o.c nghiˆn c´.u nhiˆu v` c´ nh˜.ng u.ng dung thu.c tiˆn. Muc ˜ aaa`` ` e o ¯. eu e ao u ´ e . . . .o.ng n`y tr` b`y ngˇn gon c´c b`i to´n thu.`.ng gˇp, chı ra mˆi liˆn hˆ gi˜.a ´.aaa ´e eu ¯ıch ˙’ ˙ ’ d´ cua chu a ınh a a o a o . . ch´ng v` xˆy du.ng mˆt sˆ thuˆt to´n giai quyˆt. .´ ´ ˙ ’ u aa oo a a e . . Chu.o.ng n`y s˜ thao luˆn b`i to´n luˆng l´.n nhˆ t t`. s dˆn t v` c´c tˆ’ng qu´t ho´ cua ˙ ` ´ ´ ae˙ ’ a˙ ’ aaa o o a u ¯e aa o a . ` ´ ˙ i b`i to´n luˆng d a-h`ng ho´ rˆ t kh´c biˆt ’aa n´ (1), (2), (3) v` (4) trˆn. Do c´c thuˆt to´n gia o a e a a a o¯a aa a e . . vˆ ban chˆ t, v` khˆng phai d` u hiˆu qua nhu. phu.o.ng ph´p g´n nh˜n, nˆn s˜ khˆng d u.o.c `˙ ´ao e’ ˙ ¯ˆ ’e ˙ ’ a e aa a e e o ¯. . d` cˆp o. d ay. Ban d oc quan tˆm c´ thˆ’ xem [30] v` c´c t`i liˆu dˆ n k`m theo. ˙ ˜ ¯ˆ a ˙ ¯ˆ e.’ . ¯. a oe aa a e a e . B`i to´n luˆng l´.n nhˆ t ` ´ 7.2 a a o o a Luˆng l´.n nhˆ t trˆn mang vˆn tai G l` mˆt luˆng v´.i gi´ tri l´.n nhˆ t. N´i chung c´ mˆt ` ´e ao` ´ a˙ ’ o o a o o a .o a o oo . . . . .i c`ng gi´ tri l´.n nhˆ t. Phˆn n`y tr` b`y thuˆt to´n t` luˆng l´.n nhˆ t. Y a´ a` ´ ` a ım ` ´ v`i luˆng v´ u o o a .o a aa ınh a a o o . tu.o.ng cua thuˆt to´n l`: kho.i d` u v´.i luˆng n`o d o v` tˇng gi´ tri cua luˆng cho dˆn khi ˙ ¯a o ` ` ´ ˙ ’ ˙ ’ ’ˆ a.˙ ’ a aa o a ¯´ a a o ¯e . .o.c n˜.a. Kˆt qua ta c´ luˆng l´.n nhˆ t. khˆng thˆ’ tˇng d u . u ˙ ´ o` ´ ˙ ’ o ea ¯ e o o a V´ du 7.2.1 D` thi c´ hu.´.ng trong H` 7.1 biˆ’u diˆn so. d` mang dˆn dˆu. Dˆu d u.o.c -ˆ . o o ˙ ˜ ˜a a` ` ¯. ı. o ınh e e ¯ˆ . o a . t`u s v` d u.o.c bo.m thˆng qua mang dˆn nh` m´y loc dˆu t. C´c d ınh b, c, d v` e l` ˜ ´ aa.` a ¯˙ ’ dˆn t` a au a¯ . o ¯e a aa . c´c tram bo.m trung gian. C´c cung biˆ’u thi c´c ˆng dˆ n dˆu v` hu.´.ng di chuyˆ’n cua hˆ ˙ ˙˙e ˜aao ´ a` ’ a a e ao e . . . ˜ ´ ´ ’´ ˙a ’ o¯ ˙o thˆng. C´c nh˜n trˆn c´c cung l` kha nˇng thˆng qua tˆi d a cua ˆng dˆn. B`i to´n d at ra o a a ea a o a a a ¯ˇ . l` t` c´ch chuyˆ’n nhiˆu nhˆ t lu.o.ng dˆu t`. t`u dˆn nh` m´y v` t´ gi´ tri n`y. H` 7.1 ˙ ` ´ ` u a ¯e ´ a ım a e e a a a a a ınh a . a ınh . l` mˆt v´ du cua mˆt “mang vˆn tai”. Tru.´.c hˆt ta c´: ´ aoı.˙ ’ a˙ ’ o oe o . . . . 174