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

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
Nội dung trích xuất từ tài liệu:
Đồ 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 ....... ...... ..... . .... ...... . .. ...