Đồ thị và các thuật toán - Chương 6

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

74
lượt xem 9
download

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

Tài liệu tham khảo giáo trình Đồ thị và các thuật toán - Chương 6 Đồ thị phẳng

Chủ đề:

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

Lưu

Nội dung Text: Đồ thị và các thuật toán - Chương 6

Chu.o.ng 6 -ˆ . ˙ ’ D` thi phˇ ng o a Ch´ng ta d a nghiˆn c´.u c´c t´ chˆ t cua c´c d` thi con, chˇng han, c´c dˆy chuyˆn, chu ˙ ’ ´’ ` e u a ınh a ˙ a ¯ˆ . u ¯˜ o a aa e . .o.ng n`y, ch´ng ta s˜ nghiˆn tr` v` c´c cˆy bao tr`m trong mˆt d` thi d ˜ cho. Trong chu ınh a a a u o ¯o . ¯a .ˆ a u e e .u to`n bˆ d` thi G v´.i cˆu hoi sau: khi n`o G l` phˇng? ˙ ’ ˙ ’ c´ u a o ¯o . .ˆ oa a aa Chu.o.ng n`y bˇt d` u v´.i hai v´ du vˆ d` thi Kuratowski d ´ng vai tr` trung tˆm trong ´ˆ ı . ` ¯ˆ . a a ¯a o eo ¯o o a ˙m tra t´ phˇng cua d` thi. Kˆ tiˆp l` c´c t´ chˆ t cua d` thi phˇng, chˇng han ’ ˙ ’ ˙ ’ ˙ ’ ´´ ´’ˆ ˙ ¯ˆ . e e a a ınh a ˙ ¯o . a ’o viˆc kiˆ e e ınh a a . . d .nh l´ Euler v` gia thuyˆt bˆn m`u nˆ’i tiˆng “moi d` thi phˇng l` 4−sˇc” (ph´t biˆ’u nˇm ˙´ ˙ ˙ ’ ´ ´´ a˙ ’ ¯i y eo aoe ¯o . a ˆ a a aea . 1850 v` d u.o.c ch´.ng minh nˇm 1976). Ch´ng ta c˜ng t` hiˆ’u tiˆu chuˆ’n cˆn v` d u dˆ’ d` ˙e ˙ a a ¯ ˙ ¯e ¯o ’ ˙ˆ a` a¯ . u a u u ım e -. ˙ ng-Dinh l´ Kuratowski. Cuˆi c`ng l` d ˆi ngˆ u h` hoc cua d` thi phˇng. ’ ˜ ınh . ˙ ¯o . a ˙ ’ ´u ´ ’ˆ thi l` phˇ .a a y o a ¯o a -. 6.1 Dinh ngh˜ v` c´c v´ du ıa a a ı . Nhˇc lai rˇ ng d` thi G d u.o.c goi l` phˇng nˆu tˆn tai mˆt ph´p biˆ’u diˆn G lˆn mˆt mˇt ˙ a.` ´ ˙ ’ ˜ e`. ´o a ¯o . ˆ ¯. .a a o e e e e o a . . . . tai d ınh cua ch´ng. C´c ˙ ’ ´ phˇng sao cho hai canh bˆ t k` cua d` thi khˆng cˇt nhau ngoai tr` . ¯˙ ´ a y ˙ ¯ˆ . o ’o ’ ˙ ’ a a u u a . . d` thi m` c´ thˆ’ biˆn d o’i cho tr`ng nhau bˇ ng ph´p biˆn dang co d˜n liˆn tuc trˆn mˇt ˙´ ˙ ` ´ ¯o . a o e e ¯ˆ ˆ u a e e ae. e a . . phˇng th` khˆng coi l` nh˜.ng d` thi phˇng kh´c nhau. Theo d inh ngh˜ d` thi trong H` ˙ ’ ˙ ’ a ıo au ¯ˆ . a o a ¯. ıa, ¯o . ˆ ınh ˙ ’ 6.1 l` phˇng. aa V´ du 6.1.1 (B`i to´n ba biˆt thu. v` ba nh` m´y). C´ ba biˆt thu. a, b, c v` ba nh` m´y: ı. aa e .a aa o e a aa . . . .´.c d, mˆt nh` m´y ho.i d ot e v` mˆt nh` m´y d iˆn f. Mˆi biˆt thu. nˆi v´.i ˜e ´ ´ mˆt nh` m´y nu o o aa o aa ¯ˆ ao a a ¯e o .oo . . . . . .ng ˆng dˆ n nu.´.c, ˆng dˆ n ho.i v` d u.`.ng dˆy d iˆn. Vˆy c´ thˆ’ v˜ ˙ ` ˜ ˜ ´ ´ c´c nh` m´y bˇ ng nh˜ o a aaa u a oo a a¯o a ¯e a o ee . . ˙ ng ba biˆt thu. v` ba nh` m´y v` tˆ t ca c´c d u.`.ng vˆn chuyˆ’n sao cho khˆng ˙ ’ ´ ˙ a ¯o a a aa ’ trˆn mˇt phˇ e a a e .a a e o . . . c´ hai d u.`.ng n`o cˇt nhau o. mˆt d iˆ’m kh´c c´c d` u m´t cua ch´ng hay khˆng? Ta c´ mˆ ˙ ´ ˙ o ¯e ’. u˙ ’ o ¯o aa a a ¯a ˆ u o oo h` ho´ bo.i d` thi hai phˆn K3,3 : C´c d ınh cua d` thi tu.o.ng u.ng c´c nh` v` c´c nh` m´y ` ınh a ˙ ¯o .’ˆ a ¯˙ ’ ˙ ¯o . ’ˆ a ´ a aaa aa http://www.ebook.edu.vn 149
.......................... ......................... ..... ..... a .... .... .... .... ... ... ... ... ... ... ... ... ... ... . • ... ... ... ... ... .... . ........... . . .. .. ............ .. .. .. . .. . . .. .. ... . . .... ... .. .. ..... .. .. .. .. . . . . .. ... ... ... .. .. ... .. .. . .. ... . . ... .. . .. . ... .. .. ... . . ... ... . . .. .. . . .. .. . ... . ... .. ... ... . . . . . ... .. ...... ...... ... . . . ... ... .. ...... . . . . . .. . .. ... . . . .. ...... ... . . . . . ... .. ... . ..... . . ...... . ... . . ... . . e• . •b . .... ... ... . ... . . .. . . . . . .. . . . . .. . . . .. . . . .. . . . .. . . . . .. . . . . .. . . . .. . . . . . . . . . . . . . . .. . . . . . .. . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .. .. .. . . .. . .. .. .. . .. . . .. .. . .. .. .. . .. . . . . .. .. .. . .. .. .. . • • .. . . ....................................................... ...................................................... ... . . . ... . . ...... ...... . . ...... . .... c .... .. d .... .. .... .... .. .... .. ..... ... ..... ... ...... .... ...... .... ......... ........... ...................... .................. ˙ ’ H` 6.1: V´ du vˆ d` thi phˇng. ı . ` ¯o . a ınh eˆ (xem H` 6.2); mˆt canh liˆn thuˆc hai d ınh tu.o.ng u.ng v´.i mˆt nh` v` mˆt nh` m´y. B`i ¯˙ ’ ınh o. e o ´ oo aa o aa a . . . . .a vˆ kiˆ’m tra t´ phˇng cua d` thi Kuratowski K . Bˇ ng thu.c nghiˆm c´ thˆ’ chı e˙ ˙’ ˙ ’ ` to´n d u ` e ˙ ¯ˆ . ’o oe˙ a¯ ınh a a e . . 3,3 ` ˙’ ra rˇ ng d` thi n`y khˆng phˇng. a ¯ˆ . a o o a a c b •................................ • • .. .. .... .... . . .. . .. . ...... ..... . . ... . ... ... . ... . .... ... . .... ... . . . ... . ... . ... . ..... .... .. . . .... ... . . .... ....... . ... ..... . . ... . ..... ... .... .. . . .... ... . ... ... ..... ... ... . . . .... .... ... .... ..... .... . . . ... ... . . . ... .... .... ... ... . ... . . . . ... ... ... . . .... . .. .... .... ... .... ... .. . . . ... ... ... . . . .... ... ... .... .... ... .... ... . . . ... ... . . . ......... .... ... . ... ..... .... ... ... . . . ... ... . . . ... .... . . . .... . . . .. .. . ..... ... .... ..... . . . ... ... .... ..... ... .. ...... . . . . . . .. . . . ... ... ... . . . .... ... ... ... . ....... .... . . . .... ... ... . . ... ... . .... . ..... ... ... ... .... . . . .... . .. ... .... . . . . ...... ......... .. .. ....... . . .. .. .... . . ..... .... ....... ... ...... . . .. . . . . ... ... ... .... . . .... . ...... ... ..... ... .... .... . ....... . . . . .. . . . ... ... . . . .... ... ... .... . . . ... ... .... .... ... ... . . . .......... . .... .... ......... ... ........ . . . ... ... . . . ... . . . . . ... ......... . . . .... .... .......... ... .... ..... ... ... . . . . . . .. . . . ... ... ... . . . .... ... ... ... .... .... .... . . . ... ... . . . . . ... .. . ... ... ... .... .... . . . .... ... ... .... ... . . . ... . . . ... .... .... .... ..... .. . . . ... ....... ... . . . ... ... ... ....... ... . . . .... ... . . . . .... ... . .... ... . . . . . ... .... .. .... .. . .... . .... ...... .... ... . .... ... . ... . .. ... . . . ... .. . . . . .......... ...... . .... .. . ... . ... . ... . .. ....... . .. . .. • • • .. ...... ...... ..... ..... .... . . . . . e f d -ˆ . H` 6.2: D` thi Kuratowski K3,3 . ınh o V´ du 6.1.2 C˜ng bˇ ng thu.c nghiˆm, c´ thˆ’ ch´.ng to d` thi d` y d u K5 (xem H` 6.3) ˙ ` ˙ ¯o . ¯ˆ ¯ ˙ ’ˆ ’ ı. u a e oeu a ınh . . ˙ ’ l` khˆng phˇng. ao a Vˆ t´ khˆng phˇng cua c´c d` thi K3,3 v` K5 s˜ d u.o.c giai th´ trong nh˜.ng phˆn ˙ ’ ` ınh o ` ˙ a ¯o . ’ ˙ ’ e a ˆ a e¯ . ıch u a .ng t´ chˆ t: ` sau. Ch´ y rˇ ng c´c d` thi K5 v` K3,3 c´ nh˜ ´ u´ a a ¯o . ˆ a ou ınh a ˙ ’ ˙ ’ 1. Ca hai l` khˆng phˇng; ao a 2. Nˆu xo´ mˆt canh hoˇc mˆt d ınh cua d` thi th` s˜ nhˆn d u.o.c mˆt d` thi phˇng. ˙ ’ ´ o ¯˙ .’ ˙ ¯o . ı e a ¯ . ’ˆ e ao. a o ¯o . a .ˆ . . . http://www.ebook.edu.vn 150
d • ..... ...... ... .. ... ... .. . ... ... . . ... ... .. . ... ... . . ...... ... . .. ...... . ... ... . .. ... ... .. ... ... . ... . ... ... ... . . ... . . ... ... ... . .. ... ... . ... . ... . . ... . ... . .. . . . ... ... ... . . ... . . .. . . ... ... . ... . ... . . ... . ... . .. . . ... . ... ... . ... . . . .. . . ... ... . ... . ... . . e• •c ... . ... . ................................................................................... .................................................................................. . .. .. . .. .. . . .... .. .... . . . ... . . . .. . ... . . . . ... . . . .. ... . . . ... . . .. . . . ... . . .. . . . ... . ... . ... . . ... . . . . . ... . . . . . ... . . ... ... . . . . ... . . . . .. . ... . . . . ... . . ... ... . . . . ... . . . . . ..... ... . ..... . . . . . . ... .. ... . . . . ... . . ..... ... . . .. . . .. . . .. . ... ... . . .. . . . ... .... . . ... .. . .. . . . . . ..... ... .. . . ... .. . ..... . . . ... . . ... . . ... . . . . ... . ... . . ... . . ... . . . . ... ..... . ... . . . . ... ..... . . . . . . . . . . . ..... . . . ... .. . . . . .... . . . . . . . ... ..... . ... ..... . . . . . . . . . ... . . ... . . . ... . ... . . . ... . . . ... . . . . ... . ... . . ... . . ... . . . . ... . ... . . . ... . . .. . . . . ... . ... . .. . . ... ... . . .. .. ... .. ... . . ..... ... .. . .. . . ..... ... .. . . ... .. . . . .. . . ... ... . . . . .. . . .. ... . . ... . . . ... .... • • .. .... ....................................................... ........................................................ ... .. .. a b -ˆ . H` 6.3: D` thi Kuratowski K5 . ınh o ˙ ’ ˙ ’ 3. K5 l` d` thi khˆng phˇng c´ sˆ d ınh ´ nhˆ t; K3,3 l` d` thi khˆng phˇng c´ sˆ canh ´ ´’ ´ ´ o o ¯˙ ıt a a ¯o . o ˆ a a ¯ˆ . o o a oo. ıt ´ nhˆ t. a C´c biˆ’u diˆn kh´c nhau cua mˆt d` thi phˇ ng ˙ ˜ ˙ ’ ˙ ’ 6.2 a e e a o ¯ˆ . o a . Tru.´.c hˆt ta c´ kˆt qua sau. ´ ´ ˙ ’ oe oe Dinh l´ 6.2.1 [Fary] Moi d o.n d` thi phˇ ng c´ thˆ’ biˆ’u diˆn trˆn mˆt mˇt phˇ ng sao cho -. ˙˙ ˙ ’ ˜ ˙ ’ y .¯ ¯ˆ . a o oee e e oa a . . ˙ ’ ´ c´c canh l` c´c d oan thˇ ng v` ch´ng chı’ cˇt nhau tai c´c d ı’nh chung. ˙a . a ¯˙ a. a a ¯. a au Ch´.nh minh. Ch´.ng minh cua d .nh l´ n`y kh´ ph´.c tap v` khˆng d ´ng g´p nhiˆu trong ` ˙ ¯i ’ u u ya au. a o ¯o o e ˙u t´ phˇng cua d` thi. Ban d oc quan tˆm c´ thˆ’ xem [24]. Chˇng han, d` thi ’ ınh a ˙ ˙ ’ ˙ ’ ˙ ¯o . ’ viˆc hiˆ e e ˆ . ¯. a oe a . ¯ˆ . o . trong H` 6.1 c´ thˆ’ v˜ lai chı su. dung c´c d oan thˇng nhu. trong H` 6.4. Trong d inh ˙ ˙ ’ ˙˙ . ’’ ınh o ee. a ¯. a ınh ¯. .n v` c´c khuyˆn hoˇc mˆt trong hai canh song song khˆng thˆ’ v˜ ˙ l´ n`y, d` thi cˆn phai d o ı a y a ¯o . ` ˙¯ ’ ˆ a e a o o ee . . . ˙.i c´c d oan thˇng. ˙ ’ ’ a ¯. bo a Diˆn e . K´ hiˆu R(G) l` d` thi phˇng G d u.o.c biˆ’u diˆn trˆn mˇt phˇng. C´c v`ng liˆn thˆng (theo ˙ ˙ ’ ˜ ˙ ’ ye a ¯o . a ˆ ¯. e e e a a au e o . . ˙ ng R2 ) cua tˆp R2 \ R(G) goi l` c´c diˆn. Mˆt diˆn l` mˆt v`ng cua mˇt ’ oo˙ ’ ˙a ’. ˙ ’ tˆ pˆ cua mˇt phˇ a a .aa e o eaou a . . . . . . phˇng d u.o.c gi´.i han bo.i c´c canh goi l` biˆn; hai diˆn goi l` kˆ nhau nˆu c´c d u.`.ng biˆn ˙ ’ e . a` ´ ˙a. ’ a ¯. o. ae e e a ¯o e . . ´o. ˙’ cua ch´ng c´ ´ nhˆ t mˆt canh chung. u o ıt a . http://www.ebook.edu.vn 151
c • . .. .... . ..... .. . .. . .. . . . . ... . .. . ... . .. . .. ... .. . .. .. . .. . . .. .. . . .. a . . .. .. . . .. . .. . .. .. . • .. . .... .. .. . . .. ... .. .. ... . .. . .. .. .. . .. . .. .. .. . . .. .. . .. .. .. . ... .. .. .. . .. . .. .. .. . .. . .. .. . .. .. .. .. . .. .. . .. . .. .. . .. .. . .. .. .. .. . .. . .. . .. . . .. .. .. ... . .. . .. . .. . .. .. . .. ... .. .. .. . .. .. .. . .. .. . .. .. .. ... . • . .. . .. . . .. .. ....... .. .. .. .. ........ . .. . . .. .. .. .. . .. . ... .. .. .. . ... .... ... .. . . e ... ... ... .. .. . .. ... .. ... .. .. .. . ... .. . ... .... .. ... .. .. ... .. . .. ... ... .. . ... ... . ... ... .. . . ... ..... ....... .. ... . ... ...... ..... ... ..... . ... ... . . .... ..... . ... .. .. ... ... ... ..... .... ..... ... ... . ... ... .. ... .... ... .. ...... ....... . ... ... .. .. .. ......................................................................... . .. . ......................................................................... • • ..... .. . .. ... .. .. b d H` 6.4: ınh N´i chung, biˆn cua diˆn gˆm c´c chu tr` d o.n gian v´.i c´c canh r`.i nhau, c´c canh e` e˙ ’ ˙ oa. ’ o .o a ınh ¯ o a. ´ o o ¯˙ ’ treo (canh c´ mˆt d ınh bˆc mˆt), hoˇc c´c canh nˆi hai chu tr` a o aa. o ınh. Diˆn ph´ ngo`i, goi e ıa a . . . . . . . .`.ng biˆn ch´.a bˆn trong n´ c´c canh o`. l` diˆn vˆ han, luˆn luˆn tˆn tai mˆt chu tr` l` d u o ae o. o o o ınh a ¯ e ue oa . . . ´˙ ’ kh´c; d ´ l` chu tuyˆn cua diˆn vˆ han. a ¯o a e e o. . ˙ ’ V´ du 6.2.2 Ban d` d .a l´ l` d` thi tˆ pˆ phˇng khˆng c´ cˆu; d` thi d ´ c´ t´ chˆ t d ac o ` ¯o . ¯o o ınh a ¯ˇ ´. ˙ ¯o ¯i y a ¯ˆ . o o a ’ˆ ı. o o a ˆ ˙ a mˆi d ınh ≥ 3. Mˆt diˆn c´ thˆ’ kˆ v´.i diˆn kh´c o. nhiˆu canh. Trˆn H` ˙` o ˜ ¯˙ ` ’ ’ ˙’ biˆt l`: bˆc cu eaa o o e o ee e a e. e ınh . . . . . ` ` o o ¯˙ ’ 6.5 ta ch´ y rˇ ng c´c diˆn d v` g khˆng kˆ nhau mˇc d` ch´ng c´ mˆt d ınh chung; a l` diˆn u´ a a e a o e auu ae . . . . vˆ han. o. .................... .................. .......... ......... ...... ..... ...... ...... .... .... ..... ..... .... ... .... .... ..... ...... .... .... ..... .. .... ... .. . ... .... .... ... . . . . .. . .... ... .... ... .. .. ... ... .. .. .. . ... .. ... .. .. ... .. .. ... .. .. .. .. .. .. ... ... .. .. ... .. ... . .. .. ... ... .. .. a .. .. .. b .. .. .. .. .. .. .. .. . .. .. .. .. .. . .. .. .. .. .. . .. c .. .. .. . . .. .. . .. . . .. .. .. .. .. . . .. .. . . . . . .. . . .. . . . . .. . . .. . . ..... ... . ... . .. ........... ... .. ........... . . .. . . ... . ... . .. ...... .. . . .. ...... ... . . ... . . ...... .. ...... .. . ... . .. ... . . ...... ...... . . . .. .. e .. .. . .. ....... .... . . ... ... . .. .......... ...... ...... . .. . ... .. ... . . ...... .. ...... ...... .. . .. . ... .. . .... .. ..... ..... . ...... ..... ... . ..... .. ... .. ...... . ... ...... . ..... .. ... . ... .. ... .. .. ...... .. .. .. . ...... ... .. ... .. ... ........................ ... ....................... .. . .... . ... .. .. ... . ...... ......... ... .. .. . ... . ......... ... . ......... .. . . ... .. ... . . .. . . .... . . . .. .. h d ... .. . . . ... .... .... . .. . . . .... .. . . .. . .. ... ... .. . . . ... ... ... . . . .. . . . .. .. . ... .. f . .. . . . . ... ... . . . . .. . .... .. . . . . .. . ... .. . . . ... ... . ... .. . . . .. . . . . g .. . .. . .. . . ... . . ... .. . ... ... ... ... . . . . .. . .. . . .. . ... . . . .... .... . ....... .. . . . . .... . .. . ... . . .. . ... .. .. . ....................................................................................................... . . .. .. ...................................................................................................... . ... . ... . H` 6.5: ınh http://www.ebook.edu.vn 152
Biˆ’u diˆn trˆn mˇt cˆu ˙ ˜ a` e e e .a Dˆ’ tr´nh phˆn biˆt gi˜.a c´c diˆn h˜.u han v` diˆn vˆ han, ch´ng ta thu.`.ng biˆ’u diˆn c´c -e a ˙ ˙ ˜a a eua eu ae o. u o e e . . . . ˙ ng trˆn mˇt cˆu S2 ⊂ R3 du.a v`o ph´p chiˆu nˆ’i t`. S2 lˆn R2 . K´ hiˆu S l` ˙u ’ d` thi phˇ a` ´o ¯o . a ˆ e .a a e e e ye a . . d iˆ’m tiˆp x´c cua mˇt cˆu v´.i mˇt phˇng, v` N l` d iˆ’m thuˆc mˇt cˆu sao cho N S vuˆng ˙ ˙ ˙ ’ ´ a` o a a` eu˙ ’ ¯e a a a a ¯e o a o . . . . g´c v´.i mˇt phˇng. V´.i mˆ i d iˆ’m P ∈ S2 , P = N, d u.`.ng thˇng N P cˇt mˇt phˇng R2 tai ˙ ˙’ ˜ ˙’ ´ ˙ ’ ooa a o o ¯e ¯o a a a a . . . ˙m Q. Nhu. vˆy ta c´ tu.o.ng u.ng mˆt-mˆt t`. mˇt cˆu (bo d i d iˆ’m N ) lˆn mˇt ’ ˙ ` ˙ ¯ ¯e ’ d ung mˆt d iˆ ¯´ o ¯e a o ´ o ouaa e a . . . . . . ˙’ phˇng. a Theo c´ch xˆy du.ng n`y, hiˆ’n nhiˆn rˇ ng d` thi l` phˇng nˆu v` chı nˆu c´ thˆ’ biˆ’u ˙ ˙˙ ` ˙ ’ ´ ’´ e a ˙e o e e a a a e ea ¯o . a a ˆ . ˜oe ´ a` ˙oo ’ a a ¯˙ ’ diˆn n´ trˆn mˆt mˇt cˆu sao cho c´c canh cua n´ khˆng cˇt nhau ngo`i c´c d ınh chung. e o .a a. a . -. Do d o, theo Dinh l´ 6.2.1 ta c´ ¯´ y o Dinh l´ 6.2.3 Mˆt d` thi c´ thˆ’ biˆ’u diˆn trˆn mˇt cˆu sao cho c´c canh khˆng tu. cˇt -. ˙˙ ˜ ´ a` y o ¯ˆ . o e e .o e e .a a. o .a nˆu v` chı’ nˆu n´ c´ thˆ’ biˆ’u diˆn phˇ ng trˆn mˇt phˇ ng. ˙˙ ˜ ˙ ’ ˙ ’ ´ ´ e a ˙e oo e e e a e a a . Mˆt d` thi phˇng d u.o.c biˆ’u diˆn trˆn mˇt cˆu s˜ phˆn chia mˇt cˆu th`nh nhiˆu v`ng ˙ ˙ ’ ˜ a` e a a` `u o ¯o . a ¯ . .ˆ e e e .a .a a e .i nˆi, diˆn vˆ han trˆn mˇt phˇng d u.o.c ´nh ˜ ˙’ a`a` kh´c nhau. Mˆ i v`ng trˆn mˇt cˆu l` miˆn gi´ o a ou e a e o. e o. e a a ¯.a . . . xa th`nh v`ng trˆn mˇt cˆu ch´.a d iˆ’m cu.c bˇc N. Hiˆ’n nhiˆn rˇ ng, bˇ ng ph´p quay th´ ˙ ˙ ´ e` ` a` a u e a u ¯e a e a a e ıch . . . .p qua cˆu ch´ng ta c´ thˆ’ ´nh xa mˆt v`ng bˆ t k` th`nh diˆn vˆ han trˆn mˇt phˇng. ˙a ˙ ’ ˙` ´ya ’a ho u oe .ou a e o. e a a . . . . T`. d ´ ta nhˆn d u.o.c: u ¯o a¯. . -. Dinh l´ 6.2.4 Mˆt d` thi phˇ ng c´ thˆ’ biˆ’u diˆn trˆn mˆt mˇt phˇ ng sao cho diˆn bˆ t k` ˙˙ ˙ ’ ˜ ˙ ’ ´ y o ¯ˆ . a .o oee e e oa a eay . . . .´.c l` diˆn vˆ han. cho tru o a e o .. Mˆi liˆn quan c´c v`ng trˆn mˇt cˆu cho ph´p ch´ng ta thˆ y rˇ ng khˆng c´ su. phˆn a` ´ a` ´a oe au e .a e u o o. a .c su. gi˜.a diˆn vˆ han v` c´c diˆn h˜.u han trˆn mˇt phˇng. Do d ´, khi n´i vˆ c´c ˙ ’ o`a biˆt thu . u e e o. aa eu e a a ¯o e . . . . . . v`ng trong mˆt biˆ’u diˆn cua d` thi phˇng trˆn mˇt phˇng, ch´ng ta x´t ca diˆn vˆ han. ˙ ˜ ˙ ’ ˙ ’ ˙ ¯ˆ . a ’o e˙e o. ’. u o e e e a a u . . . kh´c nhau cˆt yˆu gi˜.a c´c ph´p biˆ’u diˆn d` thi trˆn mˆt mˇt ˙ ˜ ¯ˆ . e ´e ´ Ngo`i ra, do khˆng c´ su a a o o. o ua e e e o o a . . phˇng hay mˇt cˆu (mˇt phˇng c´ thˆ’ xem l` mˇt cˆu bo d i mˆt d iˆ’m), thuˆt ng˜. “biˆ’u ˙ ˙ ˙ ˙ ’ ˙ ’ a` aa` ˙ ¯ o ¯e ’ a a a a oe a a u e . . . . . diˆn phˇng” cua mˆt d` thi thu.`.ng d u.o.c su. dung dˆ’ bao h`m c´c ph´p biˆ’u diˆn trˆn mˇt ˙ ˙ ˜ ˙’ ˜ ˙ ’ ¯. ˙ . ’ e a o ¯ˆ . .o o ¯e a a e e e e a. . trˆn mˇt phˇng. ˙ ’ `u cˆu c˜ng nhu e a a a . Biˆ’u diˆn trˆn mˇt phˇ ng v` t´ liˆn thˆng ˙ ˜ ˙ ’ e e e a a a ınh e o . Trong mˆt d` thi khˆng liˆn thˆng, viˆc biˆ’u diˆn mˆ i th`nh phˆn trˆn mˇt phˇng c´ thˆ’ ˙ ˙ ˜ ˜ ˙ ’ ` o ¯ˆ . o .o e o e e e o a a e a a oe . . .o.c khao s´t mˆt c´ch d ˆc lˆp. Do d o, d` thi l` phˇng nˆu v` chı nˆu c´c th`nh phˆn ˙ ’ ´ ’´ ` ˙a ’ e a ˙e a du . ¯ o a ¯o a ¯´ ¯o . a a ˆ a a . .. .o.ng tu., trong mˆt d` thi t´ch d u.o.c (t´.c 1−liˆn thˆng) viˆc ˙ ’ ˙ oa a ’ liˆn thˆng cua n´ l` phˇng. Tu e o o ¯o . a ¯ . .ˆ u e o e . . http://www.ebook.edu.vn 153
biˆ’u diˆn mˆ i khˆi (t´.c l` d` thi con khˆng t´ch d u.o.c cu.c d ai) trˆn mˇt phˇng c´ thˆ’ d u.o.c ˙ ˙ ˜ ˜ ˙ ’ ´ e e o o u a ¯ˆ . o o a ¯ . . ¯. e a a o e¯ . . .o.c l` phˇng nˆu v` chı nˆu mˆ i khˆi l` phˇng. ˙ ’ ˜ ˙ ’ khao s´t d oc lˆp. Do d o mˆt d` thi t´ch d u . a a ´ ’´ ´ ˙ a ¯ˆ a ’ e a ˙e ¯´ o ¯ˆ . a ¯ .o o oa a .. Vˆy, kiˆ’m tra t´ phˇng cua d` thi chı cˆn x´t d ˆi v´.i d` thi khˆng t´ch d u.o.c. ˙ ˙ ’ ˙ ¯ˆ . ˙ ` ´ ’o ’ a e ¯o o ¯ˆ . o a e ınh a o a ¯. . Mˆt d` thi phˇng khˆng t´ch d u.o.c c´ thˆ’ biˆ’u diˆn duy nhˆ t lˆn mˆt mˇt cˆu khˆng? ˙˙ ˙ ’ ˜ ´ o a` o ¯o . a .ˆ o a ¯. o e e e ae .a o . .´.c khi tra l`.i cˆu hoi n`y, ch´ng ta cˆn giai th´ y ngh˜ cua t`. “biˆ’u diˆn duy nhˆ t”. ˙ ˜ ` ´ ˙o a ’ ˙a ’ ˙ ’ ıa ˙ u ’ Tru o u a ıch ´ e e a ˙u diˆn cua mˆt d` thi phˇng l` giˆng nhau nˆu ch´ng c´ thˆ’ l`m tr`ng nhau bˇ ng ’ ˙a ˜ ˙ ’ ` ´ ´ ˙ ’ Hai biˆ e e o ¯ˆ . a .o ao e u oe u a ph´p quay mˇt cˆu n`y th`nh mˇt cˆu kia v` c´ thˆ’ biˆn dang c´c v`ng (khˆng di chuyˆ’n ˙´. ˙ a` a` e aa a a ao e e au o e . . d ınh bˇng qua canh). Nˆu tˆ t ca c´c ph´p biˆ’u diˆn lˆn mˆt mˇt cˆu l` tr`ng nhau th` ta ˙ ˜e ´´’ a`au ¯˙’ e a ˙a a e e e o .a ı . . ` thi c´ duy nhˆ t mˆt ph´p biˆ’u diˆn. Dinh l´ du.´.i d ay, cho ch´ng ta ch´ x´c cˆu ˜ -. ˙ ´o n´i d o . o o ¯ˆ a e e e y o ¯ˆ u ınh a a . tra l`.i khi n`o th` mˆt d` thi d u.o.c biˆ’u diˆn duy nhˆ t trˆn mˆt mˇt cˆu. ˙ ˜ ´e a` ˙o ’ a ı o ¯o . ¯ . ˆ e e a o a . . . -. Dinh l´ 6.2.5 [Whitney] Ph´p biˆ’u diˆn lˆn mˇt cˆu cu a mˆ i d` thi phˇ ng 3−liˆn thˆng ˙ ˜e ˜o ˙ ’ a` .a˙ ’ y e e e o ¯ˆ . a e o ´ l` duy nhˆ t. a a Ch´.ng minh. Xem [54]. u -. ˙ ’ Dinh l´ n`y d ong mˆt vai tr` quan trong trong viˆc x´c d .nh xem mˆt d` thi c´ phˇng y a ¯´ o o e a ¯i o ¯o . o a .ˆ . . . .i c´c d` thi 3−liˆn thˆng, nˆu c´ thˆ’ biˆ’u diˆn trˆn mˆt mˇt cˆu th` ph´p ˙˙ ˜ ´ a` hay khˆng: V´ a ¯o . o o ˆ e o eoee e e o .a ıe . ˙u diˆn n`y l` duy nhˆ t. ’ ˜aa ´ biˆ e e a ˙ ’ C´c t´ chˆ t cua d` thi phˇ ng ´ ˙ ¯ˆ . ’ 6.3 a ınh a o a Phˆn n`y liˆt kˆ nghiˆn c´.u mˆt sˆ t´ chˆ t co. ban cua d` thi phˇng. Tru.´.c hˆt ta c´ ˙ ’ ` .´ ´ ´ ˙ ’ ˙ ¯o . a ’ˆ aaee eu o o ınh a oe o . Dinh l´ 6.3.1 [Berge] Trong mˆt d` thi tˆ pˆ phˇ ng, c´c chu tuyˆn cu a diˆn h˜.u han tao -. ˙ ’ ´˙ ’ y o ¯ˆ . o o a .o a e eu.. . . so. c´c chu tr`nh d ˆc lˆp. ˙a ’ th`nh mˆt hˆ co a oe ı ¯o a .. .. Ch´.ng minh. Ch´ng ta s˜ ch´.ng minh bˇ ng quy nap theo sˆ diˆn f cua d` thi G. ` ´. ˙ ¯ˆ . ’o u u eu a oe . Hiˆ’n nhiˆn d .nh l´ d ung khi G c´ mˆt hoˇc hai diˆn h˜.u han. Gia su. d .nh l´ d ung ˙ ˙ ˙ ¯i ’’ e e ¯i y ¯´ oo a eu y ¯´ . . . . ` thi phˇng c´ sˆ diˆn h˜.u han l` (f − 1); ta ch´.ng minh d inh l´ d ung cho moi ˙ ’ ´e u cho moi d o . a . ¯ˆ oo . .a u ¯. y ¯´ . d` thi phˇng c´ f diˆn h˜.u han. ˙ ’ ¯o . a ˆ o eu . . Thˆt vˆy, gia su. khˆng phai tˆ t ca c´c chu tuyˆn d` u l` c´c chu tr` khˆng giao nhau ’´’ ´e ˙˙ ’’ o ˙a ˙a aa e ¯ˆ a a ınh o .. .i tru.`.ng ho.p d o th` d inh l´ l` hiˆ’n nhiˆn. Khi d o ta c´ ˙ (theo ngh˜ l` c´ canh chung) v` v´ ıa a o . ıo o ¯´ ı ¯. ya e e ¯´ o . ˙ bo b´.t mˆt canh e n`o d ´ cua G v` d u.o.c d` thi G c´ (f − 1) diˆn h˜.u han m` c´c chu ’˙o thˆ ’ a ¯o ˙ ’ e o. a ¯ . ¯ˆ .o o eu aa . . . http://www.ebook.edu.vn 154
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 . http://www.ebook.edu.vn 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 http://www.ebook.edu.vn 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. . . . . . ˜i d ınh l` d` u m´t ´ nhˆ t cua 6 canh, th` c˜ng bˇ ng c´ch nhu. ` ´ ´’ ≥ 3f, vˆy f ≤ 2m/3. Nˆu mˆ ¯˙ o’ u ıt a ˙ 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 . http://www.ebook.edu.vn 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. . http://www.ebook.edu.vn 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 http://www.ebook.edu.vn 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 ˆ http://www.ebook.edu.vn 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 http://www.ebook.edu.vn 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 http://www.ebook.edu.vn 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 http://www.ebook.edu.vn 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 http://www.ebook.edu.vn 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 . . (d) Ngu.o.c lai (H` 6.9(e)), lu.u tr˜. Pk . Tiˆp tuc giai t´ nhˆp nhˇ ng cua dˆy chuyˆn ` ´ ` ˙ ınh a ’ ˙a ’ ınh u 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 . http://www.ebook.edu.vn 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 . http://www.ebook.edu.vn 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 http://www.ebook.edu.vn 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 ∗ ∈µ∗ http://www.ebook.edu.vn 168