Đồ thị và các thuật toán – Chương 6: Đồ thị phẳng

Chia sẻ: Lão Lão | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

36
lượt xem 3
download

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

Chương 6 về đồ thị phẳng sẽ cung cấp cho người học những kiến thức cơ bản như: Các định nghĩa và các ví dụ, các biểu diễn khác nhau của một đồ thị phẳng, các tính chất của đồ thị phẳng, phát hiện tính thẳng, đối ngẫu hình học, đối ngẫu tổ hợp. Mời các bạn cùng tham khảo

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: Đồ thị phẳng

Chu.o.ng 6 - `ˆ D a˙’ ng o thi. phˇ Ch´ ung ta d¯a˜ nghiˆen c´ u.u c´ac t´ınh chˆa´t cu˙’a c´ac d¯`ˆo thi. con, chˇa˙’ng ha.n, c´ac dˆay chuyˆ`en, chu tr`ınh v`a c´ac cˆay bao tr` . . um trong mˆo.t d¯`oˆ thi. d¯˜a cho. Trong chu o ng n`ay, ch´ ung ta s˜e nghiˆen c´ . ` . ˙ ’ u u to`an bˆo. d¯oˆ thi. G v´o i cˆau hoi sau: khi n`ao G l`a phˇang? ˙ ’ Chu.o.ng n`ay bˇa´t d¯`aˆu v´o.i hai v´ı du. vˆ`e d¯`ˆo thi. Kuratowski d¯´ong vai tr`o trung tˆam trong ˙’ viˆe.c kiˆem tra t´ınh phˇang cu˙’a d¯`ˆo thi.. Kˆe´ tiˆe´p l`a c´ac t´ınh chˆa´t cu˙’a d¯`oˆ thi. phˇa˙’ng, chˇa˙’ng ha.n ˙ ’ d¯.inh l´y Euler v`a gia˙’ thuyˆe´t bˆo´n m`au nˆo˙’i tiˆe´ng “mo.i d¯`oˆ thi. phˇa˙’ng l`a 4−sˇa´c” (ph´at biˆe˙’u nˇam 1850 v`a d¯u.o..c ch´u.ng minh nˇam 1976). Ch´ ung ta c˜ ung t`ım hiˆe˙’u tiˆeu chuˆa˙’n cˆ `an v`a d¯u˙’ d¯ˆe˙’ d¯`oˆ ˙ ’ - thi. l`a phˇang-Di.nh l´ y Kuratowski. Cuˆoi c` ´ ung l`a d¯ˆoi ngˆau h`ınh ho.c cua d¯oˆ thi. phˇa˙’ng. ´ ˜ ˙ ’ ` 6.1 - i.nh ngh˜ıa v` D a c´ ac v´ı du. Nhˇa´c la.i rˇ`a ng d¯`oˆ thi. G d¯u.o..c go.i l`a phˇa˙’ng nˆe´u tˆ `on ta.i mˆo.t ph´ep biˆe˙’u diˆ˜en G lˆen mˆo.t mˇa.t phˇa˙’ng sao cho hai ca.nh bˆa´t k` u. ta.i d¯ı˙’nh cu˙’a ch´ y cu˙’a d¯`ˆo thi. khˆong cˇa´t nhau ngoa.i tr` ung. C´ac ` ˙ ’ ´ ˙ ’ d¯oˆ thi. m`a c´o thˆe biˆen d¯oˆ i cho tr` ` ´ ung nhau bˇa ng ph´ep biˆen da.ng co d˜an liˆen tu.c trˆen mˇa.t phˇa˙’ng th`ı khˆong coi l`a nh˜ u.ng d¯`ˆo thi. phˇa˙’ng kh´ac nhau. Theo d¯i.nh ngh˜ıa, d¯`oˆ thi. trong H`ınh 6.1 l`a phˇa˙’ng. V´ı du. 6.1.1 (B`ai to´an ba biˆe.t thu.. v`a ba nh`a m´ay). C´o ba biˆe.t thu.. a, b, c v`a ba nh`a m´ay: mˆo.t nh`a m´ay nu.´o.c d, mˆo.t nh`a m´ay ho.i d¯oˆ´t e v`a mˆo.t nh`a m´ay d¯iˆe.n f. Mˆo˜i biˆe.t thu.. nˆo´i v´o.i c´ac nh`a m´ay bˇa` ng nh˜ u.ng ˆo´ng dˆa˜n nu.´o.c, ˆo´ng dˆa˜n ho.i v`a d¯u.`o.ng dˆay d¯iˆe.n. Vˆa.y c´o thˆe˙’ v˜e trˆen mˇa.t phˇa˙’ng ba biˆe.t thu.. v`a ba nh`a m´ay v`a tˆa´t ca˙’ c´ac d¯u.`o.ng vˆa.n chuyˆe˙’n sao cho khˆong c´o hai d¯u.`o.ng n`ao cˇa´t nhau o˙’. mˆo.t d¯iˆe˙’m kh´ac c´ac d¯`aˆu m´ ut cu˙’a ch´ung hay khˆong? Ta c´o mˆo . h`ınh ho´a bo˙’ i d¯`oˆ thi. hai phˆ . . `an K3,3 : C´ac d¯ı˙’nh cu˙’a d¯`oˆ thi. tu o ng u . ´ ng c´ac nh`a v`a c´ac nh`a m´ay 149 http://www.ebook.edu.vn
....................................... ............. ......... ........ .... .... ...... ....... a ....... ...... ..... . .... ...... . .. . .... • .. ....................... .... ... .... ......... ..... ..... .... .... .... . .... .. . ...... ... .... .......... .... ..... ... . ..... . .. ... ...... . .. .... . .. . ..... .. ... ...... ... . . .. . ... . .. ...... ... .. ..... .. . . .. .......... ... . ... . ... . . .. ...... ..... . . . . . ....... .... .............. .. ... ...... .. e• ... . ........ ... .. ... ... . ... ... ... ... •b ....... .. ..... .. .. ... .. . . ... .. ..... . . ... ... . ... ... ... ... ... ... ... ... ... ..... ... ... ... ... ... ... .. . ... .. . ... ... ... ... ... ... .. .. .. ... .. . ... .. .. ... .. . . .. .. . ... .. ... ... . ... .. ... .. ... . . .. ... .. ... .. ... ... .. .. .... .. . . ... ... .. ... .. . . ... ... ... .. ... ... .. ... .. ... ...... ...... .. • ................................................................................................................... ........... ............ • ... ... . d ....... ....... ........ ......... ........... c . ...... .... . .. .................. ....... ........................................... `e d¯`oˆ thi. phˇa˙’ng. H`ınh 6.1: V´ı du. vˆ (xem H`ınh 6.2); mˆo.t ca.nh liˆen thuˆo.c hai d¯ı˙’nh tu.o.ng u ´.ng v´o.i mˆo.t nh`a v`a mˆo.t nh`a m´ay. B`ai to´an d¯u.a vˆ `e kiˆe˙’m tra t´ınh phˇa˙’ng cu˙’a d¯`ˆo thi. Kuratowski K3,3 . Bˇ`a ng thu..c nghiˆe.m c´o thˆe˙’ chı˙’ ra rˇ`a ng d¯`ˆo thi. n`ay khˆong phˇa˙’ng. a b c •......................................... • ........... ..... .. ..... ..... .. ..... ... ............. ............ .. • ..... ........ ..... .... ......... ....... .... .. .... ..... ........ ....... ..... .... ... ..... ....... . . ...... . . ..... . . .. ......... ........ ... ..... ....... ..... .... ..... ..... .. ..... ... ..... ....... ..... ..... ....... ..... ... ... ..... ....... ....... ........ ... ..... ....... ... ... ..... ... . . . . ..... ............. ....... . ... ..... .. . ............ . .. . .......... ..... ... ..... ... ....... . . . ... . ..... ... ... ... ..... ... .... . .. . . . . .. .... .... .. ....... ... ..... ...... ....... .. ...... . ..... .... ... .......... ....... . ....... ............. .. ............ ... ... ... .. ... ....... . . . .. ..... ... ............. ... .. ... ....... ... ... .... .... . . .. . ... ... ....... ..... .. .... ...... . . . . ....... . .. . . ..... ..... .. ... .... ..... ........ . ....... ..... ..... ... ....... . .. .. . ........... . . . .... .. .......... ....... ... ... ....... ...... ..... ..... . . . . . ... . . ........... . ...... ... ... .. . . . ... .. . . . .. ........... .. ... ... ....... .. ... ...... ..... ....... . . . . . ..... .... ....... ..... .. ..... ... ... . .. . ... . .... ..... . .. . . . ....... . .......... ..... .. .. .. ... ..... . ... ........ .............. ..... .... ........ ....... .... ... ....... .... .. ... ................. ..... .. ..... .. . ............ ... ..... .. ..... • .............. • ........ ......... . • d e f - `ˆo thi. Kuratowski K3,3 . H`ınh 6.2: D V´ı du. 6.1.2 C˜ ung bˇa` ng thu..c nghiˆe.m, c´o thˆe˙’ ch´ u.ng to˙’ d¯`oˆ thi. d¯`ˆay d¯u˙’ K5 (xem H`ınh 6.3) l`a khˆong phˇa˙’ng. `e t´ınh khˆong phˇa˙’ng cu˙’a c´ac d¯`oˆ thi. K3,3 v`a K5 s˜e d¯u.o..c gia˙’i th´ıch trong nh˜ Vˆ u.ng phˆ `an sau. Ch´uy ´ rˇa` ng c´ac d¯`oˆ thi. K5 v`a K3,3 c´o nh˜. u ng t´ınh chˆa´t: 1. Ca˙’ hai l`a khˆong phˇa˙’ng; 2. Nˆe´u xo´a mˆo.t ca.nh hoˇa.c mˆo.t d¯ı˙’nh cu˙’a d¯`oˆ thi. th`ı s˜e nhˆa.n d¯u.o..c mˆo.t d¯`oˆ thi. phˇa˙’ng. 150 http://www.ebook.edu.vn
d • ............... ...... .. .. ...... ...... .. ... ...... ...... ... .... ............ .... ...... . ... .. ...... .... ... ...... ...... ... ... ...... ...... .. ... ...... . . . ........ ... . . . ...... ...... .. . ...... . .. ... ...... .. .... . ... ...... .. . .. . ...... . . ..... . . ... ...... e• ... ..... ... ....... .. . . ... . . ........................................................................................................................................................................................ .. ... . . •c...... ..... .... . ... ...... . . . .. ...... .. ... ...... .... ... ... ..... .... ... . .. ....... . .. ...... .. ... .... ... ... ..... .. ... ...... ... ... ..... ...... .... ... .......... .. .. . . ....... . .. ... . . . ... ...... ...... ... ... ... .......... ..... .. ... ... ..... ..... ... ..... ...... ... .. .. ... ... ... ...... . . .. ..... .... . . ..... ..... ... ... ..... ..... .. ... ... ... ... .......... ... ... ... .. ..... .......... ... .. ... ... . .. . ....... ...... . .... .. . . ... .. ...... .. ..... ...... ... ... ... .. ..... ..... .. ... ... ... ...... ..... ... ... .......... ...... ..... .... ... ... ....... ...... .. .. ..... ... .. ... ......... ................................................................................................................................ • • a b - `ˆo thi. Kuratowski K5 . H`ınh 6.3: D 3. K5 l`a d¯`oˆ thi. khˆong phˇa˙’ng c´o sˆo´ d¯ı˙’nh ´ıt nhˆa´t; K3,3 l`a d¯`ˆo thi. khˆong phˇa˙’ng c´o sˆo´ ca.nh ´ıt nhˆa´t. 6.2 C´ e˙’u diˆ ac biˆ ˜ ac nhau cu˙’a mˆ e n kh´ o.t d ¯ˆ a˙’ ng `o thi. phˇ Tru.´o.c hˆe´t ta c´o kˆe´t qua˙’ sau. - i.nh l´ D y 6.2.1 [Fary] Mo.i d¯o.n d¯`ˆo thi. phˇa˙’ ng c´o thˆe˙’ biˆe˙’u diˆ˜en trˆen mˆo.t mˇa.t phˇa˙’ ng sao cho c´ac ca.nh l`a c´ac d¯oa.n thˇa˙’ ng v`a ch´ ung chı˙’ cˇa´t nhau ta.i c´ac d¯ı˙’nh chung. Ch´ u.nh minh. Ch´ u.ng minh cu˙’a d¯.inh l´ y n`ay kh´a ph´ u.c ta.p v`a khˆong d¯´ong g´op nhiˆ `eu trong ˙ ’ ˙’ ˙ ’ ˙ ’ viˆe.c hiˆeu t´ınh phˇang cu˙’a d¯`oˆ thi.. Ba.n d¯o.c quan tˆam c´o thˆe xem [24]. Chˇang ha.n, d¯`ˆo thi. trong H`ınh 6.1 c´o thˆe˙’ v˜e la.i chı˙’ su˙’. du.ng c´ac d¯oa.n thˇa˙’ng nhu. trong H`ınh 6.4. Trong d¯i.nh `an pha˙’i d¯o.n v`ı c´ac khuyˆen hoˇa.c mˆo.t trong hai ca.nh song song khˆong thˆe˙’ v˜e y n`ay, d¯`oˆ thi. cˆ l´ bo˙’.i c´ac d¯oa.n thˇa˙’ng. / Diˆ e.n K´ y hiˆe.u R(G) l`a d¯`oˆ thi. phˇa˙’ng G d¯u.o..c biˆe˙’u diˆ˜en trˆen mˇa.t phˇa˙’ng. C´ac v` ung liˆen thˆong (theo ˙ ’ 2 2 tˆo pˆo cu˙’a mˇa.t phˇang R ) cu˙’a tˆa.p R \ R(G) go.i l`a c´ac diˆe.n. Mˆo.t diˆe.n l`a mˆo.t v` ung cu˙’a mˇa.t phˇa˙’ng d¯u.o..c gi´o.i ha.n bo˙’.i c´ac ca.nh go.i l`a biˆen; hai diˆe.n go.i l`a kˆ `e nhau nˆe´u c´ac d¯u.`o.ng biˆen cu˙’a ch´ ung c´o ´ıt nhˆa´t mˆo.t ca.nh chung. 151 http://www.ebook.edu.vn
c • ....... ...... ... ... .. .. .. ... ..... . . . . ... .... ..... ... .. ... .. ... ... ... .... a ... . ... ... .. . ... . .. . ... • . ..... ............. ... ... ...... ... ... ... ... . .. . ... .. . ...... .... ...... ... ... ... .... . . .... . . . .. ... ... ..... . .. . .... .. ... . ... .... .... .. .. . ...... ..... ... ....... . . . ...... .... .. ...... .... . . . ... ..... ... ...... • ....... ...... ............ ...... .... .. .... ... .... .. .... ... . ... .... ... ........ .. ...... ...... ........ . ...... e ...... ...... ...... ...... .... .. .... .. .... ... .. . . . . .... ......... . .... .......... ............. . ......... ......... ............ ............ ...... ....... ...... ..... ................ ............ ........ • .......................................................................................................................................................... .. • b d H`ınh 6.4: `om c´ac chu tr`ınh d¯o.n gia˙’n v´o.i c´ac ca.nh r`o.i nhau, c´ac ca.nh N´oi chung, biˆen cu˙’a diˆe.n gˆ treo (ca.nh c´o mˆo.t d¯ı˙’nh bˆa.c mˆo.t), hoˇa.c c´ac ca.nh nˆo´i hai chu tr`ınh. Diˆe.n ph´ıa ngo`ai, go.i `on ta.i mˆo.t chu tr`ınh l`a d¯u.`o.ng biˆen ch´ l`a diˆe.n vˆo ha.n, luˆon luˆon tˆ u.a bˆen trong n´o c´ac ca.nh kh´ac; d¯´o l`a chu tuyˆe´n cu˙’a diˆe.n vˆo ha.n. V´ı du. 6.2.2 Ba˙’n d¯`oˆ d¯.ia l´ y l`a d¯`ˆo thi. tˆo pˆo phˇa˙’ng khˆong c´o cˆ `au; d¯`oˆ thi. d¯´o c´o t´ınh chˆa´t d¯aˇ. c biˆe.t l`a: bˆa.c cua mˆoi d¯ınh ≥ 3. Mˆo.t diˆe.n c´o thˆe kˆe v´o i diˆe.n kh´ac o˙’. nhiˆ ˙’ ˜ ˙ ’ ˙ ’ ` . `eu ca.nh. Trˆen H`ınh 6.5 ta ch´ uy ´ rˇa` ng c´ac diˆe.n d v`a g khˆong kˆ `e nhau mˇa.c d` ung c´o mˆo.t d¯ı˙’nh chung; a l`a diˆe.n u ch´ vˆo ha.n. .......................................................... ............. ......... .......... ....... ........ ...... . .. ......... ............ .. . . . ..... .. . .......... ..... . .. .. .... . . ....... . . ... ..... ...... . ... .... ...... ... ...... ... ... ...... ... . .... .. ...... . ... . ... ..... .. ... ... ... a .. ... ... b ... . ... ... ... . .. ... . . . ... ... .. ... .. ... ... ... .... ... ... c .... ... ... ... ... ... . .. ... ... .... ... .. ... . ..... ..................... . . .. . . ... . ........ ........... . .... . ........... .. ... ..... .... .. ..... .... ........... ........... .... ... ..... ..... .... ... ...... .... e .. ..... .... ........... ......... ... ........... . .. . .. . . ...... ...... ...... . . ... .. .. ..... ............ .... .......... ...... .. ...... .... ........... ..... ... ...... .. ....... .... ........... ..... ...... ................................................ ....... . ........... .. ....... .... . .... .. ..... .. . .... ........ ................... .... ..... ...... .... ....... ...... .... .... .... ... .. . h . ..... .. ...... d ... . . . ........... .. .... ....... .... .... .... .... ... . . ........ . .... . . . ... ....... ...... .. . . f ... .... ... .... .. .... .. ......... .... .. .... .... .. ..... ........ . .. . . . . .. ...... .. .. . . .... .. ...... g . . . . . . .. ........... . ... .......... . ........................................................................................................................................................................................................ H`ınh 6.5: 152 http://www.ebook.edu.vn
e˙’u diˆ Biˆ ˜ e n trˆ en mˇ `au a.t cˆ D- ˆe˙’ tr´anh phˆan biˆe.t gi˜u.a c´ac diˆe.n h˜u.u ha.n v`a diˆe.n vˆo ha.n, ch´ ung ta thu.`o.ng biˆe˙’u diˆ˜en c´ac d¯`oˆ thi. phˇa˙’ng trˆen mˇa.t cˆ `au S2 ⊂ R3 du..a v`ao ph´ep chiˆe´u nˆo˙’i t` u. S2 lˆen R2 . K´ y hiˆe.u S l`a d¯iˆe˙’m tiˆe´p x´ . `au v´o i mˇa.t phˇa˙’ng, v`a N l`a d¯iˆe˙’m thuˆo.c mˇa.t cˆ uc cu˙’a mˇa.t cˆ `au sao cho N S vuˆong g´oc v´o.i mˇa.t phˇa˙’ng. V´o.i mˆo˜i d¯iˆe˙’m P ∈ S2 , P 6= N, d¯u.`o.ng thˇa˙’ng N P cˇa´t mˇa.t phˇa˙’ng R2 ta.i d¯u ´ng mˆo.t d¯iˆe˙’m Q. Nhu. vˆa.y ta c´o tu.o.ng u ´.ng mˆo.t-mˆo.t t` u. mˇa.t cˆ `au (bo˙’ d¯i d¯iˆe˙’m N ) lˆen mˇa.t phˇa˙’ng. Theo c´ach xˆay du..ng n`ay, hiˆe˙’n nhiˆen rˇa` ng d¯`oˆ thi. l`a phˇa˙’ng nˆe´u v`a chı˙’ nˆe´u c´o thˆe˙’ biˆe˙’u diˆ˜en n´o trˆen mˆo.t mˇa.t cˆ `au sao cho c´ac ca.nh cu˙’a n´o khˆong cˇa´t nhau ngo`ai c´ac d¯ı˙’nh chung. Do d¯o´, theo D - i.nh l´ y 6.2.1 ta c´o - i.nh l´ D y 6.2.3 Mˆo.t d¯`ˆo thi. c´o thˆe˙’ biˆe˙’u diˆ˜en trˆen mˇa.t cˆ `au sao cho c´ac ca.nh khˆong tu.. cˇa´t nˆe´u v`a chı˙’ nˆe´u n´o c´o thˆe˙’ biˆe˙’u diˆ˜en phˇa˙’ ng trˆen mˇa.t phˇa˙’ ng. Mˆo.t d¯`oˆ thi. phˇa˙’ng d¯u.o..c biˆe˙’u diˆ˜en trˆen mˇa.t cˆ `au s˜e phˆan chia mˇa.t cˆ `au th`anh nhiˆ `eu v` ung kh´ac nhau. Mˆo˜i v` ung trˆen mˇa.t cˆ `au l`a miˆ`en gi´o i nˆo.i, diˆe.n vˆo ha.n trˆen mˇa.t phˇa˙’ng d¯u.o..c ´anh . xa. th`anh v` ung trˆen mˇa.t cˆ `au ch´ u.a d¯iˆe˙’m cu..c bˇa´c N. Hiˆe˙’n nhiˆen rˇ`a ng, bˇ`a ng ph´ep quay th´ıch ho..p qua˙’ cˆ `au ch´ ung ta c´o thˆe˙’ ´anh xa. mˆo.t v` ung bˆa´t k` y th`anh diˆe.n vˆo ha.n trˆen mˇa.t phˇa˙’ng. T` . . . u d¯´o ta nhˆa.n d¯u o. c: - i.nh l´ D y 6.2.4 Mˆo.t d¯`ˆo thi. phˇa˙’ ng c´o thˆe˙’ biˆe˙’u diˆ˜en trˆen mˆo.t mˇa.t phˇa˙’ ng sao cho diˆe.n bˆa´t k`y cho tru ´o.c l`a diˆe.n vˆo ha.n. . Mˆo´i liˆen quan c´ac v` ung trˆen mˇa.t cˆ `au cho ph´ep ch´ ung ta thˆa´y rˇ`a ng khˆong c´o su.. phˆan . . biˆe.t thu. c su. gi˜ . u a diˆe.n vˆo ha.n v`a c´ac diˆe.n h˜ . u u ha.n trˆen mˇa.t phˇa˙’ng. Do d¯´o, khi n´oi vˆ `e c´ac v`ung trong mˆo.t biˆe˙’u diˆ˜en cu˙’a d¯`ˆo thi. phˇa˙’ng trˆen mˇa.t phˇa˙’ng, ch´ ung ta x´et ca˙’ diˆe.n vˆo ha.n. . Ngo`ai ra, do khˆong c´o su. kh´ac nhau cˆot yˆeu gi˜ ´ ´ . ˙ ’ u a c´ac ph´ep biˆeu diˆ˜en d¯`ˆo thi. trˆen mˆo.t mˇa.t phˇa˙’ng hay mˇa.t cˆ `au (mˇa.t phˇa˙’ng c´o thˆe˙’ xem l`a mˇa.t cˆ u. “biˆe˙’u `au bo˙’ d¯i mˆo.t d¯iˆe˙’m), thuˆa.t ng˜ diˆ˜en phˇa˙’ng” cu˙’a mˆo.t d¯`ˆo thi. thu.`o.ng d¯u.o..c su˙’. du.ng d¯ˆe˙’ bao h`am c´ac ph´ep biˆe˙’u diˆ˜en trˆen mˇa.t `au c˜ cˆ ung nhu. trˆen mˇa.t phˇa˙’ng. e˙’u diˆ Biˆ ˜ e n trˆ en mˇ a˙’ ng v` a.t phˇ a t´ınh liˆ en thˆ ong Trong mˆo.t d¯`ˆo thi. khˆong liˆen thˆong, viˆe.c biˆe˙’u diˆ˜en mˆo˜i th`anh phˆ `an trˆen mˇa.t phˇa˙’ng c´o thˆe˙’ . . d¯u o. c kha˙’o s´at mˆo.t c´ach d¯ˆo.c lˆa.p. Do d¯o´, d¯`oˆ thi. l`a phˇa˙’ng nˆe´u v`a chı˙’ nˆe´u c´ac th`anh phˆ`an . . . . . liˆen thˆong cu˙’a n´o l`a phˇa˙’ng. Tu o ng tu. , trong mˆo.t d¯`oˆ thi. t´ach d¯u o. c (t´ . u c 1−liˆen thˆong) viˆe.c 153 http://www.ebook.edu.vn
u.c l`a d¯`ˆo thi. con khˆong t´ach d¯u.o..c cu..c d¯a.i) trˆen mˇa.t phˇa˙’ng c´o thˆe˙’ d¯u.o..c biˆe˙’u diˆ˜en mˆo˜i khˆo´i (t´ kha˙’o s´at d¯oˆ. c lˆa.p. Do d¯o´ mˆo.t d¯`ˆo thi. t´ach d¯u.o..c l`a phˇa˙’ng nˆe´u v`a chı˙’ nˆe´u mˆo˜i khˆo´i l`a phˇa˙’ng. `an x´et d¯ˆo´i v´o.i d¯`ˆo thi. khˆong t´ach d¯u.o..c. Vˆa.y, kiˆe˙’m tra t´ınh phˇa˙’ng cu˙’a d¯`ˆo thi. chı˙’ cˆ Mˆo.t d¯`oˆ thi. phˇa˙’ng khˆong t´ach d¯u.o..c c´o thˆe˙’ biˆe˙’u diˆ˜en duy nhˆa´t lˆen mˆo.t mˇa.t cˆ `au khˆong? . . . Tru ´o c khi tra˙’ l`o i cˆau ho˙’i n`ay, ch´ ung ta cˆ `an gia˙’i th´ıch y´ ngh˜ıa cu˙’a t` . u “biˆe˙’u diˆ˜en duy nhˆa´t”. ˙ ’ ˜ ˙ ’ Hai biˆeu diˆen cu˙’a mˆo.t d¯`ˆo thi. phˇang l`a giˆo´ng nhau nˆe´u ch´ ung c´o thˆe˙’ l`am tr` ung nhau bˇa` ng ph´ep quay mˇa.t cˆ `au n`ay th`anh mˇa.t cˆ `au kia v`a c´o thˆe˙’ biˆe´n da.ng c´ac v` ung (khˆong di chuyˆe˙’n d¯ı˙’nh bˇang qua ca.nh). Nˆe´u tˆa´t ca˙’ c´ac ph´ep biˆe˙’u diˆ˜en lˆen mˆo.t mˇa.t cˆ `au l`a tr` ung nhau th`ı ta ` ´ ˙ ’ ˜ n´oi d¯oˆ thi. c´o duy nhˆa t mˆo.t ph´ep biˆeu diˆen. Di.nh l´ - . . y du ´o i d¯aˆy, cho ch´ ung ta ch´ınh x´ac cˆau tra˙’ l`o.i khi n`ao th`ı mˆo.t d¯`oˆ thi. d¯u.o..c biˆe˙’u diˆ˜en duy nhˆa´t trˆen mˆo.t mˇa.t cˆ `au. - i.nh l´ D y 6.2.5 [Whitney] Ph´ep biˆe˙’u diˆ˜e n lˆen mˇa.t cˆ `au cu˙’ a mˆo˜i d¯`ˆo thi. phˇa˙’ ng 3−liˆen thˆong l`a duy nhˆa´t. u.ng minh. Xem [54]. Ch´ / D- i.nh l´ y n`ay d¯o´ng mˆo.t vai tr`o quan tro.ng trong viˆe.c x´ac d¯.inh xem mˆo.t d¯`oˆ thi. c´o phˇa˙’ng hay khˆong: V´o.i c´ac d¯`oˆ thi. 3−liˆen thˆong, nˆe´u c´o thˆe˙’ biˆe˙’u diˆ˜en trˆen mˆo.t mˇa.t cˆ `au th`ı ph´ep ˙’ biˆeu diˆ˜en n`ay l`a duy nhˆa´t. 6.3 C´ a´t cu˙’a d ac t´ınh chˆ ¯ˆ a˙’ ng `o thi. phˇ u.u mˆo.t sˆo´ t´ınh chˆa´t co. ba˙’n cu˙’a d¯`oˆ thi. phˇa˙’ng. Tru.´o.c hˆe´t ta c´o `an n`ay liˆe.t kˆe nghiˆen c´ Phˆ - i.nh l´ D u.u ha.n ta.o y 6.3.1 [Berge] Trong mˆo.t d¯`ˆo thi. tˆo pˆo phˇa˙’ ng, c´ac chu tuyˆe´n cu˙’ a diˆe.n h˜ th`anh mˆo.t hˆe. co. so˙’. c´ac chu tr`ınh d¯ˆo.c lˆa.p. u.ng minh. Ch´ Ch´ u.ng minh bˇ`a ng quy na.p theo sˆo´ diˆe.n f cu˙’a d¯`ˆo thi. G. ung ta s˜e ch´ Hiˆe˙’n nhiˆen d¯.inh l´y d¯u ´ng khi G c´o mˆo.t hoˇa.c hai diˆe.n h˜u.u ha.n. Gia˙’ su˙’. d¯.inh l´ y d¯u ´ng ` ˙ ’ ´ cho mo.i d¯oˆ thi. phˇang c´o sˆo diˆe.n h˜ . u u ha.n l`a (f − 1); ta ch´ . u ng minh d¯i.nh l´ y d¯u ´ng cho mo.i u.u ha.n. d¯`oˆ thi. phˇa˙’ng c´o f diˆe.n h˜ Thˆa.t vˆa.y, gia˙’ su˙’. khˆong pha˙’i tˆa´t ca˙’ c´ac chu tuyˆe´n d¯`ˆeu l`a c´ac chu tr`ınh khˆong giao nhau (theo ngh˜ıa l`a c´o ca.nh chung) v`ı v´o.i tru.`o.ng ho..p d¯o´ th`ı d¯.inh l´ y l`a hiˆe˙’n nhiˆen. Khi d¯o´ ta c´o ˙ ’ . . . thˆe bo˙’ b´o t mˆo.t ca.nh e n`ao d¯´o cu˙’a G v`a d¯u o. c d¯`ˆo thi. G c´o (f − 1) diˆe.n h˜ 0 u.u ha.n m`a c´ac chu 154 http://www.ebook.edu.vn
tuyˆe´n cu˙’a n´o theo gia˙’ thiˆe´t quy na.p lˆa.p th`anh mˆo.t co. so˙’. gˆ `om c´ac chu tr`ınh d¯ˆo.c lˆa.p. Khi tra˙’ la.i ca.nh e, ta c´o mˆo.t diˆe.n h˜ . . u u ha.n m´o i m`a chu tuyˆe´n l`a mˆo.t chu tr`ınh khˆong phu. thuˆo.c . . v`ao c´ac chu tr`ınh tru ´o c (v`ı n´o ch´ u.a mˆo.t ca.nh khˆong thuˆo.c v`ao mˆo.t chu tr`ınh n`ao trong sˆo´ c´ac chu tr`ınh ˆa´y). Do bˆo˙’ sung mˆo.t ca.nh khˆong thˆe˙’ l`am tˇang chu sˆo´ lˆen qu´a mˆo.t d¯o.n vi., nˆen sˆo´ diˆe.n h˜u.u ha.n cu˙’a d¯`oˆ thi. G qua˙’ l`a x´ac d¯i.nh mˆo.t co. so˙’. gˆ `om c´ac chu tr`ınh d¯ˆo.c lˆa.p. / Hˆe. qua˙’ 6.3.2 [Euler, 1752] Gia˙’ su˙’. G l`a d¯`ˆo thi. tˆo pˆo phˇa˙’ ng liˆen thˆong n d¯ı˙’nh, m ca.nh v`a f diˆe.n. Khi d¯´o f = m − n + 2. u.ng minh. Thˆa.t vˆa.y, sˆo´ c´ac diˆe.n h˜ Ch´ u.u ha.n bˇa` ng chu sˆo´ ν(G), nˆen f = ν(G) + 1 = (m − n + 1) + 1 = m − n + 2. u.ng minh c´ach kh´ac nhu. sau. ung c´o thˆe˙’ ch´ C˜ Nhˆa.n x´et rˇ`a ng chı˙’ cˆ `an ch´u.ng minh cho mˆo.t d¯o.n d¯`ˆo thi., v`ı viˆe.c thˆem mˆo.t khuyˆen hoˇa.c thˆem mˆo.t ca.nh song song chı˙’ d¯o.n gia˙’n l`a tˇang sˆo´ diˆe.n v`a sˆo´ ca.nh cu˙’a d¯`oˆ thi. lˆen mˆo.t d¯o.n vi.. Ch´ ung ta c˜ ung c´o thˆe˙’ xo´a tˆa´t ca˙’ c´ac d¯ı˙’nh treo v`a c´ac ca.nh liˆen thuˆo.c n´o. Nˆe´u thˆem (hoˇa.c . b´o t) mˆo.t ca.nh v`a mˆo.t d¯ı˙’nh th`ı hiˆe.u sˆo´ (m − n) khˆong d¯ˆo˙’i. V`ı mˆo˜i d¯o.n d¯`ˆo thi. phˇa˙’ng c´o thˆe˙’ biˆe˙’u diˆ˜en trˆen mˇa.t phˇa˙’ng sao cho mˆo˜i ca.nh l`a mˆo.t d¯oa.n thˇa˙’ng (D y 6.2.1), nˆen mˆo.t d¯`oˆ thi. phˇa˙’ng c´o thˆe˙’ d¯u.o..c v˜e trˆen mˇa.t phˇa˙’ng sao cho - i.nh l´ c´ac diˆe.n l`a c´ac d¯a gi´ac. K´ y hiˆe.u f l`a sˆo´ diˆe.n v`a kp l`a sˆo´ c´ac diˆe.n c´o p ca.nh. V`ı mˆo˜i ca.nh thuˆo.c biˆen cu˙’a d¯u ´ng hai d¯a gi´ac, nˆen 3k3 + 4k4 + 5k5 + · · · + rkr = 2m, trong d¯o´ kr l`a sˆo´ c´ac d¯a gi´ac v´o.i sˆo´ ca.nh cu..c d¯a.i. Mˇa.t kh´ac k3 + k4 + · · · + kr = f. Tˆo˙’ng tˆa´t ca˙’ c´ac g´oc ta.i mˆo˜i d¯ı˙’nh trong d¯a gi´ac tu.o.ng u ´.ng d¯`oˆ thi. l`a 2nπ. Nhˇa´c la.i rˇa` ng tˆo˙’ng tˆa´t ca˙’ c´ac g´oc trong mˆo.t d¯a gi´ac p ca.nh l`a (p − 2)π v`a tˆo˙’ng tˆa´t ca˙’ c´ac g´oc ngo`ai l`a (p + 2)π. Do d¯o´ 2nπ = (3 − 2)πk3 + (4 − 2)πk4 + · · · + (r − 2)πkr + 4π = (2m − 2f )π + 4π. T` u. c´ac d¯ˇa˙’ng th´ u.c trˆen, ta suy ra 2(m − f )π + 4π = 2nπ. Vˆa.y f = m − n + 2. / 155 http://www.ebook.edu.vn
V´ı du. 6.3.3 [Euler] Ta x´et trong khˆong gian ba chiˆ `eu mˆo.t d¯a diˆe.n lˆ `oi c´o n d¯ı˙’nh, m ca.nh v`a f diˆe.n. Hiˆe˙’n nhiˆen ta c´o thˆe˙’ v˜e n´o trˆen mˆo.t mˇa.t cˆ `au sao cho hai ca.nh bˆa´t k` y khˆong cˇa´t nhau ta.i nh˜ . u ng d¯iˆe˙’m kh´ac c´ac d¯`aˆu m´ ut. Sau d¯´o tiˆe´n h`anh ph´ep chiˆe´u nˆo˙’i v´o i tˆam o˙’. gi˜ . u.a mˆo.t trong c´ac diˆe.n ta c´o thˆe˙’ biˆe˙’u diˆ˜en d¯a diˆe.n d¯´o trˆen mˇa.t phˇa˙’ng. V`ı d¯`oˆ thi. l`a phˇa˙’ng nˆen u.c co. ba˙’n sau d¯aˆy cu˙’a c´ac d¯a diˆe.n lˆ ta c´o hˆe. th´ `oi: n − m + f = 2. Hˆ e. qua˙’ 6.3.4 Trong mˆo.t d¯o.n d¯`ˆo thi. phˇa˙’ ng, liˆen thˆong c´o f diˆe.n, n d¯ı˙’nh, m ca.nh (m ≥ 2), u.c sau luˆon nghiˆe.m d¯u c´ac bˆa´t d¯aˇ˙’ ng th´ ´ng ( 2m ≥ 3f, 3n − 6 ≥ m. Ch´ u.ng minh. Mˆo˜i diˆe.n c´o biˆen ´ıt nhˆa´t l`a ba ca.nh, mˆo˜i ca.nh l`a chung cu˙’a ch´ınh x´ac hai diˆe.n, do d¯o´ 2m ≥ 3f. Thay thˆe´ f = m − n + 2 trong cˆong th´ u.c Euler, ta c´o bˆa´t d¯aˇ˙’ ng th´ u.c th´ u. hai. / Ch´ ung ta lu.u y u.c th´ ´ rˇ`a ng bˆa´t d¯aˇ˙’ ng th´ u. hai chı˙’ l`a mˆo.t d¯iˆ `eu kiˆe.n cˆ `an m`a khˆong d¯u˙’ vˆ`e . t´ınh phˇa˙’ng cu˙’a mˆo.t d¯`ˆo thi.. N´oi c´ach kh´ac, mo.i d¯o n d¯`oˆ thi. phˇa˙’ng cˆ `an pha˙’i tho˙’a m˜an c´ac . `eu kiˆe.n n`ay, nhu ng d¯iˆ d¯iˆ . . ´ng. Chˇa˙’ng ha.n d¯`ˆo thi. Kuratowski K3,3 tho˙’a `eu ngu o. c la.i l`a khˆong d¯u 3n − 6 = 3.6 − 6 = 12 ≥ m = 9. Nhu.ng V´ı du. 6.3.5 D - `ˆo thi. K3,3 khˆong phˇa˙’ng. D u.ng minh ch´ - ˆe˙’ ch´ `an chı˙’ ra rˇa` ng trong d¯`oˆ ung ta cˆ ` ´ . thi. n`ay khˆong tˆon ta.i diˆe.n m`a biˆen cu˙’a n´o c´o sˆo ca.nh nho˙’ ho n 5. Thˆa.t vˆa.y, nˆe´u d¯`ˆo thi. l`a phˇa˙’ng th`ı 2m ≥ 4f. u.c Euler Theo cˆong th´ 2m ≥ 4(m − n + 2). Vˆa.y 2.9 ≥ 4(9 − 6 + 2). Hay 18 ≥ 20! Mˆau thuˆa˜n. Do d¯o´ d¯`ˆo thi. K3,3 khˆong phˇa˙’ng. - `ˆo thi. d¯`aˆy d¯u˙’ c´o nˇam d¯ı˙’nh K5 l`a khˆong phˇa˙’ng. Thˆa.t vˆa.y, nˆe´u ngu.o..c la.i th`ı V´ı du. 6.3.6 D K5 s˜e c´o f = m − n + 2 = 10 − 5 + 2 = 7 156 http://www.ebook.edu.vn
diˆe.n. Chu tuyˆe´n cu˙’a mˆo˜i diˆe.n d¯`ˆeu c´o ´ıt nhˆa´t ba ca.nh. Nˆe´u lˆa.p d¯o.n d¯`oˆ thi. liˆen thuˆo.c u. d¯´o diˆe.n-ca.nh, th`ı sˆo´ ca.nh mˆo.t mˇa.t ≤ 2m v`a mˇa.t kh´ac la.i ≥ 3f. T` 20 = 2m ≥ 3f = 21. y, vˆa.y K5 l`a khˆong phˇa˙’ng. Vˆo l´ Hˆe. qua˙’ 6.3.7 Mˆo˜i ba˙’ n d¯`ˆo d¯.ia l´y c´o ´ıt nhˆa´t mˆo.t diˆe.n m`a sˆo´ ca.nh cu˙’ a chu tuyˆe´n nho˙’ ho.n hoˇa.c bˇ`a ng 5. Ch´ u.ng minh. Thˆa.t vˆa.y, trong ba˙’n d¯`ˆo d¯.ia l´ y, mˆo˜i d¯ı˙’nh l`a d¯`aˆu m´ ut cu˙’a ´ıt nhˆa´t 3 ca.nh; nˆe´u . lˆa.p d¯o n d¯`oˆ thi. liˆen thuˆo.c d¯ı˙’nh-ca.nh th`ı sˆo´ ca.nh mˆo.t mˇa.t ≤ 2m, mˇa.t kh´ac la.i ≥ 3n, vˆa.y n ≤ 2m/3. Nˆe´u gia˙’ thiˆe´t rˇa` ng mˆo˜i diˆe.n c´o chu tuyˆe´n gˆ `om ´ıt nhˆa´t 6 ca.nh v`a nˆe´u lˆa.p d¯o.n d¯`oˆ thi. liˆen thuˆo.c diˆe.n-ca.nh, th`ı sˆo´ ca.nh cu˙’a n´o, mˆo.t mˇa.t ≤ 2m, mˇa.t kh´ac la.i ≥ 6f. Vˆa.y f ≤ 2m/6. Ta luˆon luˆon c´o thˆe˙’ gia˙’ thiˆe´t l`a d¯`oˆ thi. liˆen thˆong (nˆe´u khˆong th`ı ch´ u.ng minh hˆe. qua˙’ cho t` . u ng th`anh phˆ `an), v`a do d¯o´ c´o thˆe˙’ viˆe´t 2 = n − m + f ≤ 2m/3 − m + m/3 = 0. - iˆ D `eu d¯´o khˆong thˆe˙’ xa˙’y ra. / Hˆe. qua˙’ 6.3.8 Gia˙’ su˙’. G l`a d¯o.n d¯`ˆo thi. phˇa˙’ ng liˆen thˆong. Khi d¯´o tˆ `on ta.i d¯ı˙’nh v ∈ V sao cho d(v) ≤ 5. Ch´ u.ng minh. Thˆa.t vˆa.y, trong d¯`ˆo thi. G, mˆo˜i diˆe.n d¯u.o..c bao ´ıt nhˆa´t bo˙’.i ba ca.nh kh´ac nhau; nˆe´u lˆa.p d¯`oˆ thi. H liˆen thuˆo.c diˆe.n-ca.nh (t´ u.c l`a d¯`oˆ thi. gˆ `om tˆa.p X c´ac d¯iˆe˙’m d` ung d¯ˆe˙’ biˆe˙’u thi. . c´ac diˆe.n, tˆa.p ho. p Y c´ac d¯iˆe˙’m d` ung d¯ˆe˙’ biˆe˙’u thi. c´ac ca.nh v`a c´ac ca.nh nˆo´i d¯iˆe˙’m x ∈ X v´o.i y ∈ Y nˆe´u diˆe.n x liˆen thuˆo.c ca.nh y) th`ı sˆo´ ca.nh cu˙’a d¯`ˆo thi. H, mˆo.t mˇa.t ≤ 2m, mˇa.t kh´ac la.i ≥ 3f, vˆa.y f ≤ 2m/3. Nˆe´u mˆo˜i d¯ı˙’nh l`a d¯`aˆu m´ ut ´ıt nhˆa´t cu˙’a 6 ca.nh, th`ı c˜ung bˇa` ng c´ach nhu. . . vˆa.y ta thu d¯u o. c n ≤ 2m/6, ngh˜ıa l`a (theo cˆong th´ . u c Euler) 2 = n − m + f ≤ m/3 − m + 2m/3 = 0. Vˆo l´ y! / 6.4 Ph´ at hiˆ a˙’ ng e.n t´ınh phˇ Viˆe.c x´ac d¯i.nh d¯`ˆo thi. G l`a phˇa˙’ng hay khˆong l`a mˆo.t b`ai to´an quan tro.ng, chˇa˙’ng ha.n trong ho´a ho.c: o˙’. d¯´o nhiˆ u.c cˆa´u ta.o cu˙’a n´o c´o thˆe˙’ biˆe˙’u diˆ˜en nhu. mˆo.t `eu chˆa´t ho´a ho.c m`a cˆong th´ 157 http://www.ebook.edu.vn
d¯`oˆ thi. phˇa˙’ng; v`a tra˙’ l`o.i cˆau ho˙’i n`ay bˇ`a ng c´ach cˆo´ gˇa´ng thu˙’. v˜e n´o lˆen mˆo.t mˇa.t phˇa˙’ng r˜o r`ang khˆong pha˙’i l`a mˆo.t cˆau tra˙’ l`o.i tˆo´t. Vˆ `e thuˆa.t to´an th`o.i gian O(n) kiˆe˙’m tra mˆo.t d¯`oˆ thi. c´o phˇa˙’ng hay khˆong, v`a nˆe´u phˇa˙’ng th`ı biˆe˙’u diˆ˜en n´o nhu. thˆe´ n`ao c´o thˆe˙’ xem [34], [18]. C˜ung c´o mˆo.t thuˆa.t to´an [33] th`o.i gian O(n log n) d¯ˆe˙’ kiˆe˙’m tra t´ınh d¯ˇa˙’ng cˆa´u cu˙’a hai ung thu.`o.ng na˙’y sinh trong ho´a ho.c khi ch´ d¯`oˆ thi. phˇa˙’ng. B`ai to´an n`ay c˜ ung ta muˆo´n nghiˆen c´ . . u u c´ac phˆan tu˙’ . C´ac tiˆeu chuˆa˙’n d¯o.n gia˙’n v`a hiˆe.u qua˙’ sau cho ph´ep ph´at hiˆe.n t´ınh phˇa˙’ng cu˙’a d¯`oˆ thi.. Ph´ ut go.n co. so˙’. ep r´ 1. Do d¯`oˆ thi. l`a phˇa˙’ng nˆe´u v`a chı˙’ nˆe´u c´ac th`anh phˆ `an liˆen thˆong cu˙’a n´o l`a phˇa˙’ng, ch´ ung ˙’ ` ` ta chı cˆan x´et mˆo.t th`anh phˆan liˆen thˆong cua n´o. C˜˙ ’ ung vˆa.y, mˆo.t d¯ˆo thi. c´o d¯iˆem kh´o.p ` ˙ ’ l`a phˇa˙’ng nˆe´u v`a chı˙’ nˆe´u c´ac khˆo´i cu˙’a n´o l`a phˇa˙’ng. V`ı vˆa.y d¯ˆo´i v´o.i mˆo.t d¯`ˆo thi. G cho tru.´o.c, x´ac d¯.inh G = {G1 , G2 , . . . , Gk }, trong d¯o´ Gi , i = 1, 2, . . . , k, l`a c´ac d¯`oˆ thi. con khˆong t´ach d¯u.o..c cu˙’a d¯`oˆ thi. G. Rˆ `oi th`ı ch´ ung ta chı˙’ cˆ `an kiˆe˙’m tra t´ınh phˇa˙’ng cu˙’a mˆo˜i Gi . 2. Do viˆe.c thˆem hay x´oa c´ac khuyˆen khˆong l`am mˆa´t t´ınh phˇa˙’ng, ta xo´a c´ac khuyˆen. 3. Tˆa´t ca˙’ c´ac ca.nh song song c˜ ung khˆong a˙’nh hu.o˙’.ng trong viˆe.c x´et t´ınh phˇa˙’ng, v`ı vˆa.y u. mˆo.t ca.nh c`on la.i. xo´a tˆa´t ca˙’ c´ac ca.nh song song tr` 4. Loa.i bo˙’ tˆa´t ca˙’ c´ac d¯ı˙’nh bˆa.c hai v`a coi hai ca.nh nˆo´i v´o.i d¯ı˙’nh d¯´o l`a mˆo.t khˆong a˙’nh hu.o˙’.ng d¯ˆe´n t´ınh phˇa˙’ng cu˙’a d¯`oˆ thi.. N´oi c´ach kh´ac thu..c hiˆe.n “r´ ut go.n chuˆo˜i.” Lˇa.p la.i c´ac Bu.´o.c 3 v`a 4 cho d¯ˆe´n khi ta d¯u.o..c mˆo.t d¯`oˆ thi. d¯o.n gia˙’n nhˆa´t cho ph´ep x´ac d¯.inh dˆ˜e d`ang t´ınh phˇa˙’ng cu˙’a n´o. D- ˆo´i v´o.i mˆo.t d¯`ˆo thi. liˆen thˆong khˆong c´o d¯iˆe˙’m kh´o.p Gi , sau khi ´ap du.ng c´ac Bu.´o.c 3 v`a 4 ta s˜e d¯u.o..c mˆo.t d¯`oˆ thi. Hi c´o c´ac d¯aˇ. c tru.ng: - i.nh l´ D - `ˆo thi. Hi c´o mˆo.t trong ba da.ng y 6.4.1 D 1. Mˆo.t ca.nh d¯o.n; hoˇa.c l`a 2. Mˆo.t d¯`ˆo thi. d¯`ˆay d¯u˙’ c´o bˆo´n d¯ı˙’nh; hoˇa.c l`a 3. Mˆo.t d¯o.n d¯`ˆo thi. khˆong t´ach d¯u.o..c c´o sˆo´ d¯ı˙’nh n ≥ 5 v`a sˆo´ ca.nh m ≥ 7. 158 http://www.ebook.edu.vn
Ch´ u.ng minh. D y c´o thˆe˙’ d¯u.o..c ch´ - i.nh l´ u.ng minh bˇa` ng c´ach kha˙’o s´at tˆa´t ca˙’ c´ac d¯`oˆ thi. liˆen thˆong khˆong t´ach d¯u o. c v´o i sˆo´ ca.nh nho˙’ ho.n hoˇa.c bˇ`a ng s´au. . . . / ´ du.ng d¯.inh l´ Ap y, ch´ung ta thˆa´y rˇ`a ng tˆa´t ca˙’ c´ac d¯`oˆ thi. Hi ro.i v`ao loa.i 1 hoˇa.c 2 l`a `an kiˆe˙’m tra thˆem. phˇa˙’ng, do d¯´o khˆong cˆ T`u. nh˜ u.ng d¯iˆ `eu nˆeu trˆen, ch´ ung ta cˆ `an nghiˆen c´ u.u c´ac d¯o.n d¯`ˆo thi. liˆen thˆong khˆong t´ach d¯u.o..c v´o.i ´ıt nhˆa´t nˇam d¯ı˙’nh, v`a mˆo˜i d¯ı˙’nh c´o bˆa.c l´o.n ho.n hay bˇ`a ng ba. Kˆe´ d¯ˆe´n, ch´ung ta cˆ`an kiˆe˙’m tra bˆa´t d¯aˇ˙’ ng th´u.c m ≤ 3n − 6. Nˆe´u bˆa´t d¯ˇa˙’ng th´ u.c khˆong tho˙’a m˜an, th`ı Hi khˆong phˇa˙’ng. Ngu.o..c la.i, ch´ ung ta kiˆe˙’m tra thˆem bˇa` ng c´ach ´ap du.ng d¯.inh l´ y Kuratowski . . . . ´ ` du ´o i d¯aˆy. Tru ´o c hˆet ta cˆan d¯.inh ngh˜ıa sau. - i.nh ngh˜ıa 6.4.2 (a) Trong mˆo.t d¯`oˆ thi., hai ca.nh d¯u.o..c go.i l`a trong mˆo.t chuˆo˜i, nˆe´u ch´ D ung ´ng mˆo.t d¯ı˙’nh chung bˆa.c hai. c´o d¯u (b) Hai d¯`ˆo thi. d¯u.o..c go.i l`a d¯`oˆng phˆoi nˆe´u d¯`oˆ thi. n`ay c´o thˆe˙’ nhˆa.n d¯u.o..c t` u. d¯`ˆo thi. kia bˇa` ng c´ach ta.o thˆem c´ac ca.nh trong chuˆo˜i (t´ u c l`a ch`en thˆem c´ac d¯ı˙’nh bˆa.c hai) hay ho..p nhˆa´t c´ac . ca.nh trong chuˆo˜i. V´ı du. 6.4.3 C´ac d¯`oˆ thi. G1 v`a G2 trong H`ınh 6.6 l`a d¯`ˆong phˆoi, do c´o thˆe˙’ d¯u.a vˆ `e c` ung d¯`ˆo 0 thi. G . • ... ..... • ............................................................................... ... ... .. . ... ... • ... ... ... ..... • • ............................................................................... .. . ... ... • ... ... ... ..... • ............................................................................... .. . ... ... ... ... ... .. ... ... ... .. ... ... ... .. ... . ... ... .. ... . ... ... .. ... . ... ... .. ... ... ... .... ... ... ... .... ... ... ... .... • ... ... . .. . .... ... ... ... ... .... ... ... ... ... . .. . .... ... ... ... ... .... ... ... ... ... . .. . .... ... ... ... ... .... ... ... ... ... ... .. ... ... ... .. ... ... ... .. . .... ... . ..... ... . . .... ... . ..... ... . . .... ... . ..... ... . . ... ... . ... ... . ... ... ... ...... ... ... ...... ... ... ...... ... •..... ... ... ..... • .. ... . . .. .. ... • ..... ... ... ..... • .. ... . . .. .. ... • ..... ... ... ..... • .. ... . . .. .. ... ... .. .. ... .. .. ... .. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... • . .... ... . .... ... ... ... ... ... . .... ... . .... ... ... ... ... ... . .... ... . .... ... ... ..... ... ... ..... ... ... ..... ... ... ...... ... ... ...... ... ... ...... ... ..... ...... ... ..... ...... ... ..... ...... ...... ........ . ...... ........ . ...... ........ . • ................... .... ... • ................... .... ... • ................... .... ... G1 G2 G0 H`ınh 6.6: Hiˆe˙’n nhiˆen rˇa` ng d¯`ˆo thi. l`a phˇa˙’ng nˆe´u v`a chı˙’ nˆe´u mo.i d¯`ˆo thi. d¯`oˆng phˆoi v´o.i n´o l`a phˇa˙’ng. Ho.n n˜ u.a, quan hˆe. R trˆen tˆa.p c´ac d¯`oˆ thi. x´ac d¯.inh bo˙’.i G1 RG2 nˆe´u v`a chı˙’ nˆe´u G1 v`a G2 d¯`oˆng phˆoi l`a quan hˆe. tu.o.ng d¯u.o.ng. - i.nh l´ D y 6.4.4 [Kuratowski, 1930] D u.a d¯`ˆo thi. - `ˆo thi. G l`a phˇa˙’ ng nˆe´u v`a chı˙’ nˆe´u G khˆong ch´ ong phˆoi v´o.i hoˇa.c K5 hoˇa.c K3,3 . con d¯`ˆ 159 http://www.ebook.edu.vn
Ch´ u.ng minh. D - iˆ `an. R˜o r`ang, v`ı G khˆong thˆe˙’ biˆe˙’u diˆ˜en trˆen mˇa.t phˇa˙’ng sao cho c´ac `eu kiˆe.n cˆ ung khˆong cˇa´t nhau ngoa.i tr` ca.nh cu˙’a ch´ u. ta.i c´ac d¯ı˙’nh chung cu˙’a ch´ ung nˆe´u n´o ch´ u.a d¯`ˆo thi. con d¯`oˆng phˆoi v´o.i K5 hoˇa.c K3,3 . - iˆ D `eu kiˆe.n d¯u˙’. Xem [4]. / V´ı du. 6.4.5 Bˇ`a ng c´ach ´ap du.ng D - i.nh l´ y Kuratowski ta c´o d¯`ˆo thi. trong H`ınh 6.7 khˆong ˙ ’ . . ´ phˇang. Thˆa.t vˆa.y, tru ´o c hˆet xo´a c´ac ca.nh (a, b), (e, f ) v`a (g, h); sau d¯´o “r´ ut go.n” c´ac chuˆo˜i . . . - `ˆo thi. thu d¯u.o..c l`a K3,3 . (a, g), (g, d) v`a (f, h), (h, c) d¯ˆe˙’ d¯u o. c c´ac ca.nh m´o i (a, d) v`a (f, c). D Suy ra G ch´ u.a mˆo.t d¯`oˆ thi. con d¯`oˆng phˆoi v´o.i K3,3 v`a do d¯´o khˆong phˇa˙’ng. a • . ................. ....... ... ... ....... ....... ... .... ............. ............ .. ... . ....... .. ... ....... ....... ... ....... ....... .. ... ....... .. .......... .. . ... . ....... . ..... .. ... ....... .... . . . ....... . . . ... ... . .. ... ....... ...... . . ... ....... . . . . . . ...... ... ... f• .. . . . . ... ..... . ... ....... ... . ... .................................................................................................................................................................................................... . .... ... .. . •b ... ........ ... ........ .. ..... ... .. ... ...... .... ... ... ...... ...... . ... . g. ... ...... .... . ... . ... ... ... ...... ...... ...... ...... ... .. .. • ..... .. .. ...... .... ..... .......... ...... ...... ..... .. ... ... ... ...... .. . . . ... ... ........ .... ..... ....... ... .. .... ... ... .......... .... ...... ..... ... ... .. ...... .... ...... ... ... . ... ...... ..... .......... ... . . .... ... ........ ..... ... .. ... ... ....... ..... ... .... ... ... ... .......... ... ... ... ... ......... .......... ... ... ... ... .. ......... . ...... .... .. . ...... ... .. ...... ... ...... ..... ... .. ..... . ...... .... .... ... .... ..... ..... ......... ... ... .. .......... . .. . .. .......... .... •h ... ... ....... .. . . ............. .. .. ......... • ......... ......... ......... .... .. . . . ... .... . ..... ... ... e ........... ........... ... ............ ... ......... .... .... ... ... ... ... ... ... .......... ... . .. . ... .... ................ ... ... ... .. ......... ... ... .. ............. . ... . . .. .. ............ ..... .... ... ......... .. • ....................................................................................................... • d c H`ınh 6.7: Viˆe.c kiˆe˙’m tra t´ınh phˇa˙’ng du..a v`ao D y Kuratowski l`a kh´o d¯oˆ´i v´o.i c´ac d¯`oˆ thi. l´o.n - i.nh l´ (chˇa˙’ng ha.n, d¯o.n d¯`ˆo thi. khˆong t´ach d¯u.o..c c´o 25 d¯ı˙’nh v`a bˆa.c cu˙’a mˆo˜i d¯ı˙’nh ≥ 3). C´o mˆo.t sˆo´ t´ınh chˆa´t kh´ac d¯aˇ. c tru.ng cho c´ac d¯`ˆo thi. phˇa˙’ng. Mˆo.t trong nh˜ u.ng d¯aˇ. c tru.ng d¯o´ s˜e d¯u.o..c x´et trong phˆ `an kˆe´ tiˆe´p. - i.nh l´ D y 6.4.6 Mo.i d¯`ˆo thi. phˇa˙’ ng d¯`ˆeu 5−sˇa´c. Ch´ u.ng minh. Hiˆe˙’n nhiˆen d¯i.nh l´ ´ng cho c´ac d¯`oˆ thi. phˇa˙’ng c´o sˆo´ d¯ı˙’nh ≤ 5. Gia˙’ su˙’. khˇa˙’ng y d¯u ´ng cho mo.i d¯`oˆ thi. phˇa˙’ng c´o (n − 1) d¯ı˙’nh. Ta s˜e ch´ d¯.inh d¯u u.ng minh d¯.inh l´ y c˜ung d¯u ´ng cho nh˜ . u ng d¯`oˆ thi. phˇa˙’ng c´o n d¯ı˙’nh. 160 http://www.ebook.edu.vn
Thˆa.t vˆa.y, theo Hˆe. qua˙’ 6.3.8, trong G tˆ `on ta.i d¯ı˙’nh v c´o bˆa.c ≤ 5. D- `ˆo thi. con nhˆa.n d¯u.o..c . u G bˇ`a ng c´ach xo´a d¯ı˙’nh v v`a c´ac ca.nh liˆen thuˆo.c n´o l`a 5−sˇa´c; ta tˆo c´ac d¯ı˙’nh cu˙’a n´o bˇa` ng t` nˇam m`au α, β, γ, δ, ². Ta c´o thˆe˙’ tˆo m`au d¯ı˙’nh v, tr`u. khi n´o kˆ `e v´o.i nˇam d¯ı˙’nh mang nˇam m`au kh´ac nhau. Trong tru.`o.ng ho..p d¯´o, gia˙’ su˙’. a, b, c, d, e l`a nˇam d¯ı˙’nh kˆ `e v´o.i v (theo th´ u. tu.. v`ong quanh v) v`a gia˙’ su˙’. α, β, γ, δ, ² l`a c´ac m`au tu.o.ng u ´.ng. K´ y hiˆe.u Gα,β l`a d¯`oˆ thi. con sinh bo˙’.i tˆa.p ho..p . . . c´ac d¯ı˙’nh c´o m`au α hay β, v.v. C´o hai tru `o ng ho. p xa˙’y ra: 1. Nˆe´u a v`a c khˆong thuˆo.c nh˜ u.ng th`anh phˆ `an cu˙’a d¯`ˆo thi. Gα,γ th`ı trong th`anh phˆ u.a `an ch´ a ta tˆo m`au γ cho c´ac d¯ı˙’nh c´o m`au α v`a ngu.o..c la.i. C´ach tˆo m`au m´o.i cho G l`a chˆa´p nhˆa.n d¯u.o..c, v`a d¯ı˙’nh v bˆay gi`o. d¯u.o..c bao quanh bo˙’.i c´ac d¯ı˙’nh c´o m`au γ, β, γ, δ, ² nˆen c´o thˆe˙’ tˆo n´o bˇa` ng m`au α. 2. Nˆe´u a v`a c thuˆo.c c` ung mˆo.t th`anh phˆ `an cu˙’a d¯`ˆo thi. Gα,γ th`ı c´ac d¯ı˙’nh b v`a d khˆong thˆe˙’ nˆo´i v´o i nhau trong d¯`ˆo thi. Gβ,δ (v`ı nˆe´u ngu.o..c la.i, G ch´ . u.a d¯`oˆ thi. K5 ). Khi ho´an vi. c´ac m`au β v`a δ trong th`anh phˆ `an cu˙’a d¯`ˆo thi. Gβ,δ (ch´ u.a d¯ı˙’nh b) ta c´o thˆe˙’ tˆo m`au β cho . . d¯ı˙’nh v d¯u o. c. y d¯u.o..c ch´ - i.nh l´ D u.ng minh. / Tuy nhiˆen, ta c`on c´o thˆe˙’ l`am tˆo´t ho.n: - i.nh l´ D y 6.4.7 [Gia˙’ thuyˆe´t bˆo´n m`au] Sˇa´c sˆo´ cu˙’ a mo.i d¯`ˆo thi. phˇa˙’ ng bˇa` ng bˆo´n. Ch´ u.ng minh. Gia˙’ thuyˆe´t bˆo´n m`au xuˆa´t hiˆe.n lˆ u.a Morgan `an d¯`aˆu tiˆen trong cuˆo.c trao d¯oˆ˙’i gi˜ v`a ngu.`o.i ho.c tr`o cu˙’a ˆong v`ao nˇam 1850. Sau d¯´o, Morgan d¯˜a d¯`ˆe cˆa.p b`ai to´an n`ay v´o.i Hamilton trong mˆo.t b´ u.c thu. viˆe´t ng`ay 23 th´ang 10 nˇam 1852. Kˆe´t qua˙’ l`a rˆa´t nhiˆ `eu “ch´ u.ng minh” c˜ ung nhu. c´ac “pha˙’n v´ı du.” v`a c´ac gia˙’ thuyˆe´t kh´ac c´o liˆen quan xuˆa´t hiˆe.n (d¯ˆe˙’ c´o thˆem nh˜u.ng thˆong tin chi tiˆe´t, xem [48]). Tuy nhiˆen, pha˙’i d¯ˆe´n nˇam 1976, hai nh`a to´an ho.c ngu.`o.i M˜ y l`a Appel v`a Haken (xem [1]), su˙’. du.ng h`ang ng`an gi`o. trˆen m´ay t´ınh d¯iˆe.n tu˙’., d¯˜a ch´ u.ng minh t´ınh d¯u ´ng d¯ˇa´n cu˙’a gia˙’ thuyˆe´t bˆo´n m`au. / 6.4.1 e˙’m tra t´ınh phˇ Kiˆ a˙’ ng Viˆe.c x´ac d¯i.nh mˆo.t d¯`ˆo thi. c´o phˇa˙’ng hay khˆong l`a mˆo.t b`ai to´an c´o y ´ ngh˜ıa. Nhu. d¯a˜ chı˙’ ra, c´ac d¯aˇ. c tru.ng cu˙’a Kuratowski v`a Whitney cho ph´ep kiˆe˙’m tra t´ınh phˇa˙’ng cu˙’a d¯`oˆ thi.. Tuy nhiˆen c´ac d¯aˇ. c tru.ng n`ay khˆong ph` u ho..p khi thu..c hiˆe.n trˆen m´ay t´ınh do kh´o thˆe˙’ hiˆe.n bˇ`a ng chu.o.ng tr`ınh; ngo`ai ra nˆe´u d¯`oˆ thi. l`a phˇa˙’ng, th`ı c´ac kˆe´t qua˙’ n`ay khˆong chı˙’ ra phu.o.ng ph´ap 161 http://www.ebook.edu.vn
v˜e n´o nhu. thˆe´ n`ao. Ngu.`o.i ta biˆe´t rˇ`a ng [52], nˆe´u su˙’. du.ng tiˆeu chuˆa˙’n cu˙’a Kuratowski d¯ˆe˙’ kiˆe˙’m tra t´ınh phˇa˙’ng cu˙’a d¯`oˆ thi. n d¯ı˙’nh (n > 5) th`ı th`o.i gian thu..c hiˆe.n ´ıt nhˆa´t l`a O(n6 ). C´o mˆo.t sˆo´ thuˆa.t to´an kiˆe˙’m tra t´ınh phˇa˙’ng cu˙’a d¯`oˆ thi. (xem [52] d¯ˆe˙’ c´o tˆo˙’ng quan vˆ `e ´ ˙ ’ ` ´ . . . c´ac kˆet qua n`ay). Hˆau hˆet c´ac phu o ng ph´ap n`ay ´ap du.ng c´ach “xˆay du. ng ban d¯oˆ”: Dˆau ˙ ’ ` - ` tiˆen, cho.n mˆo.t d¯`oˆ thi. con phˇa˙’ng g cu˙’a G v`a biˆe˙’u diˆ˜en n´o trˆen mˇa.t phˇa˙’ng. (Trong hˆ `au hˆe´t c´ac thuˆa.t to´an, g l`a mˆo.t chu tr`ınh). Sau d¯´o thˆem c´ac ca.nh v`ao d¯`oˆ thi. g sao cho n´o khˆong cˇa´t c´ac ca.nh kh´ac (ngoa.i tr` u. ta.i c´ac d¯ı˙’nh chung). Nˆe´u ch´ ung ta th`anh cˆong khi biˆe˙’u diˆ˜en . . la.i th`ı d¯`oˆ thi. G l`a phˇa˙’ng; ngu o. c la.i kˆe´t luˆa.n G khˆong phˇa˙’ng. Kh´o khˇan ch´ınh cu˙’a mˆo.t thuˆa.t to´an nhu. vˆa.y o˙’. chˆo˜ trong nh˜ u.ng giai d¯oa.n tru.´o.c d¯o´, viˆe.c thˆem c´ac ca.nh v`ao g t` . u nh˜ . u ng kha˙’ nˇang c´o thˆe˙’ khˆong d¯ˆe˙’ y ´ d¯ˆe´n c´ac giai d¯oa.n sau n`ay. Mˆo.t c´ach d¯aˇ. t ca.nh o˙’ bu ´o c n`ao d¯o´ c´o thˆe dˆan d¯ˆe´n khˆong thˆe d¯ˇa.t ca.nh o˙’. bu.´o.c sau, mˇa.c d` . . . ˙ ’ ˜ ˙ ’ u d¯`oˆ thi. d¯a˜ cho l`a phˇa˙’ng. Chˇa˙’ng ha.n, trong H`ınh 6.8(a), gia˙’ su˙’. ta bˇa´t d¯`ˆau v´o.i d¯`ˆo thi. con g l`a chu tr`ınh {v1 , v2 , v3 , v4 , v5 , v1 }. Sau d¯o´ ta thˆem c´ac ca.nh (v1 , v4 ), (v4 , v6 ), (v3 , v6 ) v`a (v1 , v6 ) sao cho d¯`oˆ thi. thu d¯u.o..c vˆa˜n phˇa˙’ng. Hiˆe˙’n nhiˆen l`a ca.nh (v2 , v5 ) khˆong thˆe˙’ d¯aˇ. t d¯u.o..c! T`u. d¯´o ta cho rˇa` ng d¯`ˆo thi. khˆong phˇa˙’ng. Tuy nhiˆen, d¯`ˆo thi. n`ay c´o thˆe˙’ biˆe˙’u diˆ˜en phˇa˙’ng nhu trong . H`ınh 6.8(b). v4 v4 ........... .............. ......................................... • ...................................... .. . .. ..... .. ..... ........... .............. ......................................... • .......................................... .. .. ... ..... ....................... ......... ..... .... ......... ......... ..... ..... ........ .. .. .. ..... ..... .. .. .. ..... ..... .. . ........ ........ .. ... ..... . ...... . . ........ ..... .............. .. .... ..... ... ..... .. .... ..... ..... ....... ....... .... ......... . . ..... ..... .... ......... ..... ...... ....... ... ....... .... ... . . ..... ... ..... ..... ....... ... ....... . . . . . ..... ..... .... ......... ..... . ....... ....... .... . ..... .... ..... ....... ... ... . . ... ... .. ..... ... . .. .... . . . ..... ..... ... ... .... .. . ....... ....... ... ... ... ... ..... ... ... v5 ...... ... . ..... . . . . . . . . . ..... ..... v3 ..... ..... ... ... v5 ....... ...... ... ....... .v3 ...... ....... ....... ....... ....... • v6 ... .. . ... . . .. ... ... ... • . .. .... .......... . . . . . ... .. .. . . .... . . .. • ... ..................... ... ... • . . ......... ......... • ..... . ................................................................................. . ... ... ... . ... ...... ... ....... ... ....... •... . . ........................... ... ...... .. ... . ... ... ... ... ... ....... ... ...... ... . ...... ... ..... .. .. .. .... .... .... .... ... ... ... ...... ...... ...... ...... ...... .... ... .. ... v6 .. ... ... .... .... .... .... ... ... ... ...... ...... ...... ...... .. .. ... . .. .. . .... ... ... .... ... ...... ... .. .. .... ... ... ........ .... . . .... ... ...... ...... ... .. .... .... . ... ........... ... .... .... .. . ...... ... .. .... .... ... ...... .. .. .... .... ...... .. .. ... .... ... .... ... ... .. ...... ...... ... .... ... .... ... ...... ...... ... ... .... ... .. ........ ... .... ... ...... ...... ... ... .... ... ..... ...... ..... ... .... ... ...... .. . ... . ....... .. .. ....... .. .. ... ........................................................................................... ......................................................................................... • • • .... .... • ... ... ... v1 v2 v1 .... ..... ..... ..... v2 .... ... .. .. ...... ..... ....... ........ ... ......... .......... ........ ................ .......... ......................................... (a) (b) H`ınh 6.8: Hai c´ach biˆe˙’u diˆ˜en cu˙’a c` ung mˆo.t d¯`oˆ thi.. - ˆay ch´ınh l`a mˆo.t tro˙’. nga.i cu˙’a phu.o.ng ph´ap xˆay du..ng ba˙’n d¯`oˆ; v`a ta cˆ D `an mˆo.t sˆo´ thu˙’ tu.c kh´ac gia˙’i quyˆe´t. Nhu. d¯˜a biˆe´t, mˆo.t d¯`oˆ thi., n´oi chung, c´o thˆe˙’ thu go.n th`anh d¯`oˆ thi. nho˙’ ho.n d¯ˆe˙’ d¯o.n gia˙’n ho´a tiˆe´n tr`ınh kiˆe˙’m tra. C´ac bu.´o.c thu go.n khˆong a˙’nh hu.o˙’.ng d¯ˆe´n t´ınh phˇa˙’ng (hoˇa.c khˆong phˇa˙’ng) cu˙’a d¯`ˆo thi.. 162 http://www.ebook.edu.vn
u.ng th`anh 1. Kiˆe˙’m tra t´ınh liˆen thˆong cu˙’a d¯`ˆo thi.. Nˆe´u d¯`ˆo thi. khˆong liˆen thˆong, x´et t` `an liˆen thˆong. phˆ 2. Xo´a c´ac khuyˆen, v`a thay tˆa´t ca˙’ c´ac ca.nh song song bo˙’.i d¯u ´ng mˆo.t ca.nh. 3. Xo´a c´ac d¯ı˙’nh bˆa.c hai v`a ho..p nhˆa´t hai ca.nh liˆen thuˆo.c d¯ı˙’nh n`ay. Lˇa.p la.i c´ac Bu.´o.c 2 v`a 3 cho d¯ˆe´n khi khˆong thˆe˙’ r´ut go.n thˆem. ´ du.ng Thuˆa.t to´an Tremaux-Tarjan d¯ˆe˙’ phˆan hoa.ch d¯`oˆ thi. th`anh c´ac th`anh phˆ 4. Ap `an . . khˆong t´ach d¯u o. c . 5. V´o.i mˆo˜i th`anh phˆ`an khˆong t´ach d¯u.o..c, thu..c hiˆe.n ph´ep thu go.n su˙’. du.ng c´ac Bu.´o.c 3 v`a 2 cho d¯ˆe´n khi khˆong thˆe˙’ thu go.n thˆem. 6. V´o.i mˆo˜i th`anh phˆ `an khˆong t´ach d¯u.o..c c´o n d¯ı˙’nh, m ca.nh, kiˆe˙’m tra c´ac bˆa´t d¯aˇ˙’ ng th´ u.c n ≥ 5, m ≥ 9, m ≤ 3n − 6. uc; ngu.o..c la.i kiˆe˙’m tra th`anh Nˆe´u c´ac r`ang buˆo.c n`ay khˆong thoa˙’ m˜an, thuˆa.t to´an kˆe´t th´ phˆ `an khˆong t´ach d¯u.o..c kh´ac. Mo.i d¯`ˆo thi. c´o n < 5 hoˇa.c m < 9 l`a phˇa˙’ng, v`a mo.i d¯o.n d¯`ˆo thi. c´o m > 3n − 6 khˆong phˇa˙’ng. Mˆo˜i d¯`ˆo thi. khˆong t´ach d¯u.o..c c´o thˆe˙’ t´ach th`anh c´ac th`anh phˆ `an 3−liˆen thˆong. Su˙’. du.ng kˆe´t qua˙’ cu˙’a Tutte [54]: D - `ˆo thi. l`a phˇa˙’ng nˆe´u v`a chı˙’ nˆe´u tˆa´t ca˙’ c´ac th`anh phˆ`an 3−liˆen thˆong ˙ ’ . . ` cua n´o l`a phˇang. Tuy nhiˆen, phu o ng ph´ap n`ay khˆong hiˆe.u qua bˇa ng thuˆa.t to´an cu˙’a Hopcroft ˙ ’ ˙ ’ v`a Tarjan sau d¯ˆay. Thuˆ a.t to´ an Hopcroft-Tarjan Thuˆa.t to´an kiˆe˙’m tra t´ınh phˇa˙’ng cu˙’a d¯`ˆo thi. rˆa´t ph´ u.c ta.p. Do d¯o´ ch´ ung ta s˜e chı˙’ tr`ınh b`ay nh˜ . . u ng d¯ˇa.c tru ng cˆo´t yˆe´u. D- ˆe˙’ hiˆe˙’u thuˆa.t to´an ch´ınh, x´et thu˙’ tu.c phˆan r˜a sau ´ap du.ng cho c´ac d¯o n d¯`ˆo thi. khˆong t´ach d¯u.o..c G c´o n d¯ı˙’nh v`a m ca.nh. . `en: Phˆan r˜a chu tr`ınh-dˆay chuyˆ 1. T`ım chu tr`ınh µ trong G. G´an g = µ. G´an nh˜an c´ac d¯ı˙’nh v`a c´ac ca.nh cu˙’a g l`a v1 , v2 , . . . , v`a e1 , e2 , . . . , tu.o.ng u ´.ng. D - ˇa.t i = 1. 2. Nˆe´u c´o mˆo.t ca.nh n`ao cu˙’a G chu.a c´o nh˜an th`ı t`ım mˆo.t dˆay chuyˆ `en µi bˇa´t d¯`aˆu v`a kˆe´t th´ . . . ` uc ta.i c´ac d¯ı˙’nh d¯u o. c g´an nh˜an nhu ng dˆay chuyˆen n`ay chı˙’ gˆom nh˜ ` u.ng ca.nh chu.a . . . d¯u o. c g´an nh˜an. Lu u tr˜ . . . u µi . Nˆe´u tˆa´t ca˙’ c´ac ca.nh d¯a˜ d¯u o. c g´an nh˜an, chuyˆe˙’n sang . . Bu ´o c 4. 163 http://www.ebook.edu.vn
- ˇa.t g = g ∪ µi ; v`a i = i + 1. G´an nh˜an c´ac ca.nh v`a c´ac d¯ı˙’nh chu.a d¯u.o..c g´an nh˜an trong 3. D g v`a chuyˆe˙’n sang Bu.´o.c 2. 4. Xuˆa´t g v`a c´ac dˆay chuyˆ u.ng. `en µ1 , µ2 , . . . , µe . D` C´o thˆe˙’ ch´u.ng minh rˇa` ng [52] thu˙’ tu.c trˆen s˜e phˆan r˜a d¯o.n d¯`oˆ thi. khˆong t´ach d¯u.o..c G th`anh mˆo.t chu tr`ınh v`a e = m − n dˆay chuyˆ `en. V`ı chu tr`ınh c´o thˆe˙’ xem l`a kˆe´t nˆo´i cu˙’a hai dˆay chuyˆ `en khˆong c´o chung ca.nh, nˆen G d¯u o..c phˆan r˜a th`anh m − n + 2 dˆay chuyˆ . `en. Cˆ `an ch´uy ` ´ rˇa ng, mˇa.c d` ´ . ´ ` . . u phˆan r˜a trˆen l`a khˆong duy nhˆa t, nhu ng sˆo c´ac dˆay chuyˆen d¯u o. c phˆan u. G l`a hˇ`a ng sˆo´. Chˇa˙’ng ha.n, H`ınh 6.8, x´et hai phˆan r˜a sau th`anh mˆo.t chu tr`ınh v`a bˆo´n r˜a t` (10 − 6 = 4) dˆay chuyˆ `en: {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 )}. Trong qu´a tr`ınh phˆan r˜a chu tr`ınh-dˆay chuyˆ `en, ch´ung ta c´o thˆe˙’ biˆe˙’u diˆ˜en chu tr`ınh µ ˙ ’ ´ ` . trˆen mˇa.t phˇang, v`a tiˆep tu.c thˆem c´ac dˆay chuyˆen m´o i µ1 , µ2 , . . . , khi ch´ ung d¯u.o..c sinh ra. Mˆo.t dˆay chuyˆ . `en µi m´o i hoˇa.c s˜e phˆan chia mˆo.t diˆe.n d¯ang tˆ `on ta.i th`anh hai diˆe.n m´o.i hoˇa.c s˜e khiˆe´n cho g ∪ µi khˆong phˇa˙’ng khi thˆem n´o v`ao g. Do ch´ ung ta thˆem tu` yy ´, nˆen c´o thˆe˙’ . xa˙’y ra t`ınh tra.ng nhu trong H`ınh 6.8. D - ˆe˙’ gia˙’i quyˆe´t kh´o khˇan n`ay, ta c´o thˆe˙’ hoˇa.c 1. Tiˆe´p tu.c thˆem c´ac dˆay chuyˆ `en cho d¯ˆe´n khi khˆong thˆe˙’ thu..c hiˆe.n d¯u.o..c n˜u.a. Sau d¯o´ tro˙’. . la.i t`ım kiˆe´m cho.n lu. a c´ach biˆe˙’u diˆ˜en kh´ac (t´ . u c l`a d` . . ung phu o ng ph´ap lˆ `an ngu.o..c) thay cho qu´a tr`ınh tru.´o.c d¯´o; hoˇa.c l`a 2. Tiˆe´p tu.c t`ım c´ac dˆay chuyˆ `en kh´ac nhau nhu.ng khˆong d¯aˇ. t ch´ ung v`ao µ, cho d¯ˆe´n khi . . ` ` . . t`ım d¯u o. c diˆe.n m`a mˆo.t dˆay chuyˆen cˆan d¯u o. c d¯aˇ. t v`ao, hoˇa.c l`a biˆe´t chˇa´c rˇa` ng khˆong c´o tro˙’. nga.i v´o.i diˆe.n m`a d¯aˇ. t dˆay chuyˆ`en v`ao. C´o mˆo.t sˆo´ thuˆa.t to´an tiˆe´p cˆa.n theo hu.´o.ng th´u. nhˆa´t, nhu.ng Hopcroft v`a Tarjan tiˆe´p cˆa.n theo c´ach th´ . u hai v`a d¯˜a ch´ u ng minh rˇa` ng thuˆa.t to´an cu˙’a ho. l`a hiˆe.u qua˙’ ho.n. Y . ´ ch´ınh . cu˙’a thuˆa.t to´an n`ay l`a gia˙’i quyˆe´t su. nhˆa.p nhˇa` ng khi thˆem c´ac dˆay chuyˆ ˙ ’ `en; cu. thˆe l`a: Gia˙’ su˙’. rˇ`a ng o˙’. bu.´o.c n`ao d¯´o, ch´ ung ta c´o mˆo.t dˆay chuyˆ `en µi (trˆen d¯ı˙’nh cu˙’a mˆo.t danh s´ach ch´ . u a c´ac dˆay chuyˆ `en cˆ . `an xu˙’ l´ y) m`a ch´ung ta cˆ `an gia˙’i quyˆe´t su.. nhˆa.p nhˇ`a ng cu˙’a n´o. Gia˙’ su˙’. a v`a b l`a c´ac d¯ı˙’nh xuˆa´t ph´at v`a kˆe´t th´ uc cu˙’a dˆay chuyˆ `en n`ay. C´ac tru.`o.ng ho..p kh´ac . . nhau c´o thˆe˙’ xa˙’y ra v`a phu o ng ph´ap xu˙’ l´ . . . ´ ng s˜e d¯u o. c tr`ınh b`ay du.´o.i d¯ˆay. C´ac t`ınh y tu o ng u . . . huˆo´ng n`ay d¯u.o..c gia˙’i th´ıch du..a v`ao H`ınh 6.9. 1. Nˆe´u khˆong tˆ `on ta.i dˆay chuyˆ u.a hai d¯ı˙’nh a v`a b. `en kh´ac Pi v`a ch´ 164 http://www.ebook.edu.vn
(a) Nˆe´u stack kh´ac trˆo´ng th`ı lu.u tr˜ u. Pi v`a gia˙’i quyˆe´t su.. nhˆa.p nhˇ`a ng cu˙’a dˆay chuyˆ `en kˆe´ tiˆe´p trong stack. (b) Ngu.o..c la.i (stack bˇ`a ng trˆo´ng) th`ı thˆem Pi v`ao g; gia˙’i quyˆe´t su.. nhˆa.p nhˇ`a ng cu˙’a dˆay chuyˆ `en kˆe´ tiˆe´p trong stack. 2. Ngu.o..c la.i gia˙’ su˙’. Pj l`a dˆay chuyˆ`en (kh´ac Pi ) ch´u.a hai d¯ı˙’nh a v`a b (xem H`ınh 6.9(a)). u. la.i Pi trong danh s´ach. Xˆay du..ng dˆay chuyˆ Gi˜ `en Pk xuˆa´t ph´at t` u. d¯ı˙’nh x n`ao d¯´o trˆen Pi v`a nˇa` m gi˜ . . u a a v`a b (gia˙’ su˙’ Pk kˆe´t th´ uc ta.i y). (a) Nˆe´u y thuˆo.c Pk (xem H`ınh 6.9(b)) th`ı d¯aˇ. t dˆay chuyˆ `en Pk trˆen Pi v`ao stack v`a ` gia˙’i quyˆe´t t´ınh nhˆa.p nhˇa ng cu˙’a dˆay chuyˆ `en Pk . (b) Ngu.o..c la.i v`a nˆe´u y khˆong thuˆo.c Pj (H`ınh 6.9(c)) th`ı dˆay chuyˆ `en Pi d¯˜a d¯u.o..c gia˙’i. Loa.i Pi kho˙’i stack. Gia˙’i su.. nhˆa.p nhˇ`a ng cu˙’a dˆay chuyˆ `en kˆe´ tiˆe´p trong stack. (c) Ngu.o..c la.i nˆe´u y nˇ`a m gi˜ u.a a v`a b (H`ınh 6.9(d)) th`ı lu.u tr˜ u. Pk . Tiˆe´p tu.c gia˙’i t´ınh nhˆa.p nhˇa` ng cu˙’a dˆay chuyˆ `en Pi bˇ`a ng c´ach ta.o dˆay chuyˆ `en kh´ac gi˜ u.a a v`a b. (d) Ngu.o..c la.i (H`ınh 6.9(e)), lu.u tr˜ u. Pk . Tiˆe´p tu.c gia˙’i t´ınh nhˆa.p nhˇ`a ng cu˙’a dˆay chuyˆ `en Pi bˇ`a ng c´ach ta.o dˆay chuyˆ `en kh´ac gi˜ . u a y v`a b. Trong H`ınh 6.9(a), dˆay chuyˆ `en µi c´o thˆe˙’ xoay ta.i hai d¯ı˙’nh a v`a b, v`a do d¯o´ s˜e phˆan . . d¯oˆi diˆe.n “trˆen” hoˇa.c “du ´o i” dˆay chuyˆ`en µj . Su.. nhˆa.p nhˇa` ng n`ay cˆ `an d¯u.o..c xu˙’. l´ - ˆe˙’ gia˙’i y. D . quyˆe´t, ta xˆay du. ng mˆo.t dˆay chuyˆ `en µk xuˆa´t ph´at t` . u d¯ı˙’nh x n`ao d¯o´ trˆen dˆay chuyˆ `en µi . (Dˆay chuyˆ `en µk ch´ . . . . u a c´ac ca.nh chu a d¯u o. c g´an nh˜an v`a kˆe´t th´uc ngay khi n´o gˇa.p mˆo.t d¯ı˙’nh d¯u.o..c g´an nh˜an, chˇa˙’ng ha.n y). Nˆe´u ca˙’ hai d¯ı˙’nh x v`a y cu˙’a dˆay chuyˆ `en µk thuˆo.c dˆay chuyˆ `en µi nhu. trong H`ınh 6.9(b), th`ı µk c´o thˆe˙’ d¯u.o..c xoay ta.i hai d¯ı˙’nh x v`a y v`a do d¯´o s˜e phˆan d¯oˆi diˆe.n ph´ıa “trˆen” hoˇa.c ph´ıa “du.´o.i” dˆay chuyˆ `en µi . V`ı vˆa.y ch´ ung ta khˆong nh˜ u.ng cˆ `an xu˙’. l´ y cho µi m`a tru.´o.c hˆe´t c`on pha˙’i gia˙’i quyˆe´t su.. nhˆa.p nhˇ`a ng cho ca˙’ dˆay chuyˆ `en m´o.i µk . Do d¯´o cˆ `an cˆa´t µk sau khi cˆa´t µi . trong mˆo.t ngˇan xˆe´p, v`a ta bˇa´t d¯`ˆau xu˙’ l´ y tu o ng tu.. µi d¯oˆ´i v´o.i µk . . . Kha˙’ nˇang kh´ac l`a d¯ı˙’nh y khˆong nˇa` m trˆen hai dˆay chuyˆ`en µi v`a µj nhu.ng la.i thuˆo.c mˆo.t dˆay chuyˆ `en kh´ac nhu. trong H`ınh 6.9(c). Trong tru.`o.ng ho..p n`ay dˆay chuyˆ `en µi khˆong . thˆe˙’ xoay sang ph´ıa bˆen kia, v`a do d¯´o khˆong c´o su. nhˆa.p nhˇ`a ng vˆ `e diˆe.n m`a dˆay chuyˆ`en n`ay phˆan chia. Nhu. trong H`ınh 6.9(d), nˆe´u d¯ı˙’nh cuˆo´i cu˙’a dˆay chuyˆ `en µk nˇ`a m trˆen dˆay chuyˆ `en µj gi˜ u.a hai d¯ı˙’nh a v`a b th`ı dˆay chuyˆ `en µi (c` ung v´o.i µk ) vˆa˜n c´o thˆe˙’ xoay ta.i a v`a b. Do d¯´o vˆa˜n c´o su.. nhˆa.p nhˇ`a ng d¯ˆo´i v´o.i dˆay chuyˆ`en µi . Tuy nhiˆen khi d¯o´ dˆay chuyˆ `en µk phˆan d¯oˆi diˆe.n x´ac d¯.inh . . bo˙’ i chu tuyˆe´n (a, x, b, y, a) khˆong c´o su. nhˆa.p nhˇa` ng. V`ı vˆa.y, ch´ ung ta cˆ `an mˆo.t dˆay chuyˆ `en kh´ac xuˆa´t ph´at t` . ˙ ’ . . u mˆo.t d¯ı˙’nh trˆen µi d¯ˆe gia˙’i quyˆe´t su. nhˆa.p nhˇ`a ng v´o i µi . 165 http://www.ebook.edu.vn
µi •...............................•..........................•...........................•..........................•......... ... .... ... ... .. •..............................................................................•.............................................................................................................•..................................................................................•... (a) a b µj µk •...............................•..........................•......... . ... .... ... ... .. •..............................•.............................•...........................•..............................•........ .... ... x µi y ....... ................................................................................................................................................................................................. • . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .• .. . • • (b) a b µj µk •.........................•........ •..............................•...........................•......... ... ... . ... ... . .... .. µi y •..................................•...... • •.. • • ................................................................................................................ .... ... • . ... ... ... . . .... .. . x .... .... .. • • • • .................................................................................................................................................................................................................................................... (c) a b µj x µi •..............................•................................•...........................•..........................•......... ... ... ... ... ... ... .. ... ... • ... ... • ............................ ... . • ... ... ... • ... ... ... ... ... ... . µk ... ... ... • • . • ... • .......................................................................................................................................................................................................................................................................... . • (d) a y b µj µk •...............................•..........................•...........................•......... .. ... .. ... ... ... µi • ... ... ... • • • • ............................................................................................................... . .. ... • ... ... . .... . . x ... ... ... .. .. • • . . • • • ............................................................................................................................................................................................................................................................................. . (e) y a b µj `en µi . H`ınh 6.9: Phˆan t´ıch c´ac kha˙’ nˇang xa˙’y ra cu˙’a dˆay chuyˆ ung, trong tru.`o.ng ho..p dˆay chuyˆ Cuˆo´i c` `en µk c´o d¯ı˙’nh y nˇ`a m trˆen dˆay chuyˆ `en µj nhu.ng nˇa` m ngo`ai d¯oa.n x´ac d¯.inh bo˙’.i a v`a b nhu. trong H`ınh 6.9(e). Dˆay chuyˆ `en µi vˆa˜n c´o thˆe˙’ xoay. . . . . . . Nhu ng kh´ac v´o i tru `o ng ho. p cu˙’a H`ınh 6.9(b), khˆong c´o su. nhˆa.p nhˇ`a ng cu˙’a dˆay chuyˆ `en µk . . tu o ng u . . ´ ng v´o i µi . Do d¯o´, cˆ`an t`ım mˆo.t dˆay chuyˆ . ˙ ’ . `en m´o i d¯ˆe gia˙’i quyˆe´t su. nhˆa.p nhˇ`a ng cu˙’a ` ` . ˙ ’ ´ dˆay chuyˆen µi v`a dˆay chuyˆen m´o i n`ay c´o thˆe xuˆa t ph´at t` u. mˆo.t d¯ı˙’nh bˆa´t k` y trˆen dˆay chuyˆ `en y, a, x, b; ngo`ai ra ta c˜ . ung mo˙’ rˆo.ng dˆay chuyˆ `en µi d¯ˆe´n d¯ı˙’nh y trˆen µj . T´om la.i, thuˆa.t to´an kiˆe˙’m tra t´ınh phˇa˙’ng cu˙’a d¯`ˆo thi. gˆ `om c´ac thu˙’ tu.c: `an khˆong t´ach d¯u.o..c; 1. T`ım c´ac th`anh phˆ `an khˆong t´ach d¯u.o..cth`anh c´ac dˆay chuyˆ 2. Phˆan hoa.ch c´ac th`anh phˆ `en; 166 http://www.ebook.edu.vn
3. X´ac d¯i.nh vi. tr´ı d¯ˆe˙’ thˆem c´ac dˆay chuyˆ `en n`ay; v`a 4. Xˆay du..ng mˆo.t biˆe˙’u diˆ˜en phˇa˙’ng. Su˙’. du.ng thuˆa.t to´an t`ım kiˆe´m theo chiˆ `eu sˆau d¯ˆe˙’ gia˙’i quyˆe´t c´ac Bu.´o.c 1 v`a 2. C´ac dˆay chuyˆ `en . . . . . d¯u o. c ta.o bo˙’ i hai bu ´o c trˆen c´o nh˜ . . u ng t´ınh chˆa´t th´ıch ho. p cho c´ac tiˆe´n tr`ınh vˆ `e sau. Th`o.i . . gian d¯`oi ho˙’i trong mˆo˜i bu ´o c (ngoa.i tr` . . . . . . u Bu ´o c 4) tı˙’ lˆe. v´o i n. Th`o i gian xˆay du. ng mˆo.t biˆe˙’u diˆ˜en phˇa˙’ng l`a O(n log n). V`ı vˆa.y th`o i gian thu..c hiˆe.n cu˙’a thuˆa.t to´an l`a O(n log n) (do cˆong . th´ u.c Euler, sˆo´ ca.nh m tı˙’ lˆe. v´o.i sˆo´ d¯ı˙’nh n trong mˆo.t d¯`ˆo thi. phˇa˙’ng). Thuˆa.t to´an n`ay c`on c´o thˆe˙’ ca˙’i thiˆe.n tˆo´t ho.n v´o.i th`o.i gian thu..c hiˆe.n l`a O(n) (xem [34]). 6.5 -ˆ D ˜u h`ınh ho.c o´i ngˆ a X´et d¯`ˆo thi. phˇa˙’ng liˆen thˆong G khˆong c´o d¯ı˙’nh cˆo lˆa.p. Khi d¯o´ ta c´o thˆe˙’ thiˆe´t lˆa.p mˆo.t d¯`oˆ thi. phˇa˙’ng G∗ nhu. sau: bˆen trong mˆo˜i diˆe.n s cu˙’a R(G) d¯aˇ. t mˆo.t d¯ı˙’nh s∗ cu˙’a G∗ ; v´o.i mˆo˜i ca.nh e cu˙’a G thiˆe´t lˆa.p tu.o.ng u ´.ng mˆo.t ca.nh e∗ cu˙’a G∗ bˇ`a ng c´ach nˆo´i c´ac d¯ı˙’nh s∗ v`a t∗ tu.o.ng u ´.ng c´ac diˆe.n s v`a t trˆen hai ph´ıa cu˙’a ca.nh e trong R(G). D - `ˆo thi. G go.i l`a d¯oˆ´i ngˆa˜u (tˆo pˆo) cu˙’a ∗ G (hay c`on go.i l`a d¯oˆ´i ngˆa˜u h`ınh ho.c cu˙’a G). - `ˆo thi. G (d¯u.`o.ng liˆ V´ı du. 6.5.1 D `en n´et) v`a d¯oˆ´i ngˆa˜u cu˙’a n´o (d¯u.`o.ng d¯u ´.t n´et) cho trong H`ınh 6.10. • ... ........ ... ... ... ... .. ... ... ... .... .. .. .. .. .... ..... ... ... ... ... . ... ... ....... ..... .... .. . .. .. .... .. .... .... ..... . .. .... . ... ... ... ... . . .... ... ... . ... .... .. ... .. ... .. . .. . . .......... . • • •. . .. . . ...... ... .. ........ ........ .. ... ....... . . ..... . . ....... . . ... . . .. .. ... . . .......... .. ..... . .... . ... .. . .. .... . ..... .. .... ... ..... . ..... .... ..... ..... ..... ........ ... .. . .. . ... ........ . ..... ... ..... ... . .... ...... ..... ... .. . ..... ...... . . ... . .. . . ....... ...... . . ...... ... ...... .. ..... ... .. .. .• ..... . . . .. ..... .. ...... ....... ... ... ... . ...... . ...... . . .. . .. .. ..... ... . .... ... ......... .. ... .... . . . .. ....... .. .... .. ... . . . . ......... .................... ....... ..... . .... . . • ... .. ... ....... ... .. . . ..... .. .. . ........ . ... ... ..... ........... . ... ... .... • ... ......................................................................................................................................................... . . ... . • ... .... .. . ... ..... ... ..... ....... .. ...... ....... ...... ....... ...... .......... ... ... . .......... . .......... ........... • .. .. ............. . ...... ... .. . H`ınh 6.10: Mˆo.t chu tr`ınh so. cˆa´p cu˙’a R(G) chia mˇa.t phˇa˙’ng th`anh hai v` ung liˆen thˆong kh´ac trˆo´ng . . . v`a r`o i nhau. Bo˙’ d¯i tˆa´t ca˙’ c´ac ca.nh d¯oˆ´i ngˆa˜u tu o ng u. ´ ng c´ac ca.nh trˆen chu tr`ınh n`ay s˜e phˆan 167 http://www.ebook.edu.vn
hoa.ch R(G∗ ) th`anh hai th`anh phˆ `an liˆen thˆong. N´oi c´ach kh´ac, mˆo˜i chu tr`ınh so. cˆa´p cu˙’a G, . . qua d¯oˆ´i ngˆa˜u, tu o ng u ´ ng mˆo.t d¯ˆo´i chu tr`ınh so. cˆa´p cu˙’a G∗ , v`a ngu.o..c la.i. T´ınh chˆa´t n`ay rˆa´t . u.u ´ıch v`ı ta c´o thˆe˙’ t`ım mˆo.t d¯oˆ´i chu tr`ınh cu˙’a G bˇ`a ng c´ach t`ım mˆo.t chu tr`ınh cu˙’a G∗ . h˜ R˜o r`ang c´o mˆo.t su.. tu.o.ng u ´.ng mˆo.t-mˆo.t gi˜ u.a c´ac ca.nh cu˙’a d¯`ˆo thi. G v`a d¯`oˆ thi. d¯oˆ´i ngˆa˜u G −mˆo.t ca.nh cu˙’a G giao v´o i mˆo.t ca.nh cu˙’a G. Ho.n n˜ ∗ ∗ . u.a ch´ ung ta c´o mˆo.t v`ai nhˆa.n x´et sau: 1. Ca.nh l`a khuyˆen trong G tu.o.ng u ´.ng ca.nh treo trong G∗ . 2. Ca.nh l`a ca.nh treo trong G tu.o.ng u ´.ng khuyˆen trong G∗ . 3. Nˆe´u G c´o d¯iˆe˙’m kh´o.p th`ı G∗ c˜ ung c´o d¯iˆe˙’m kh´o.p. 4. C´ac ca.nh trong chuˆo˜i cu˙’a G tu.o.ng u ´.ng c´ac ca.nh song song trong G∗ . 5. C´ac ca.nh song song trong G tu.o.ng u ´.ng c´ac ca.nh trong chuˆo˜i cu˙’a G∗ . 6. Sˆo´ c´ac ca.nh ta.o th`anh biˆen trong diˆe.n F cu˙’a G, bˇ`a ng bˆa.c cu˙’a d¯ı˙’nh tu.o.ng u ´.ng trong G∗ v`a ngu.o..c la.i. - `ˆo thi. G∗ l`a phˇa˙’ng. 7. D u.c l`a (G∗ )∗ = G. - `ˆo thi. d¯oˆ´i ngˆa˜u cu˙’a G∗ l`a G; t´ 8. D y hiˆe.u n, m v`a f l`a sˆo´ c´ac d¯ı˙’nh, ca.nh v`a diˆe.n tu.o.ng u 9. Nˆe´u k´ ´.ng cu˙’a d¯`oˆ thi. phˇa˙’ng liˆen thˆong G, v`a k´ y hiˆe.u n , m v`a f l`a sˆo´ c´ac d¯ı˙’nh, ca.nh v`a diˆe.n cu˙’a d¯`ˆo thi. d¯ˆo´i ngˆa˜u G∗ ∗ ∗ ∗ tu.o.ng u ´.ng, th`ı n∗ = f, m∗ = m, f ∗ = n. V´ı du. 6.5.2 X´et mˆo.t ma.ng vˆa.n ta˙’i phˇa˙’ng (vˆo hu.´o.ng) G m`a mˆo˜i ca.nh e c´o kha˙’ nˇang thˆong qua c(e) ≥ 0, d¯ı˙’nh v`ao s v`a d¯ı˙’nh ra t d¯u.o..c xˆe´p trˆen c` ung mˆo.t d¯u.`o.ng nˇ`a m ngang. Ta lˆa.p d¯`oˆ thi. d¯ˆo´i ngˆa˜u G bˇ`a ng c´ach cho hai d¯ı˙’nh kh´ac nhau s v`a t∗ tu.o.ng u ∗ ∗ ´.ng v´o.i diˆe.n vˆo ha.n cu˙’a G : d¯ı˙’nh s∗ u ´.ng v´o.i nu˙’.a mˇa.t phˇa˙’ng du.´o.i, d¯ı˙’nh t∗ u ´.ng v´o.i nu˙’.a mˇa.t phˇa˙’ng trˆen. G´an tro.ng . . ∗ lu o. ng w(e ) = c(e) cho ca.nh e (´ ∗ u ng v´o i e). Bˆay gi`o. ta x´et c´ac b`ai to´an sau: . . B` ai to´ u.c l`a l`am cu..c an 1. Trong G t`ım thiˆe´t diˆe.n A c´o kha˙’ nˇang thˆong qua nho˙’ nhˆa´t; t´ tiˆe˙’u X c(A) = c(v). v∈A B` an 2. Trong G∗ t`ım d¯u.`o.ng d¯i ngˇa´n nhˆa´t µ∗ d¯i t` ai to´ u. s∗ d¯ˆe´n t∗ ; t´ u.c l`a l`am cu..c tiˆe˙’u X w(µ∗ ) = w(v ∗ ). v ∗ ∈µ∗ 168 http://www.ebook.edu.vn