Đồ thị và các thuật toán – Chương 5: Bài toán Euler và bài toán Hamilton

Trong chương này người học sẽ tìm hiểu các nội dung cụ thể về: Bài toán Euler, thuật toán tìm dây chuyền Euler, bài toán người đưa thư Trung Hoa, bài toán Hamilton, các điều kiện đủ về sự tồn tại chu trình Hamilton. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Đồ thị và các thuật toán – Chương 5: Bài toán Euler và bài toán HamiltonChu.o.ng 5B` ai to´ an Euler v` a b` ai to´ an HamiltonL´y thuyˆe´t d¯`oˆ thi. ph´at triˆe˙’n bˇa´t nguˆ u. nh˜ `on t` u.ng b`ai to´an cˆo˙’ d¯iˆe˙’n, trong sˆo´ d¯o´ b`ai to´an Eulerv`a b`ai to´an Hamilton t`ım h`anh tr`ınh d¯i qua mˆo˜i ca.nh d¯u ´ng mˆo.t lˆ `an v`a qua mˆo˜i d¯ı˙’nh d¯u ´ng . . `an tu o ng umˆo.t lˆ . ´ ng d¯o´ng vai tr`o quan tro.ng. u.ng u Hai b`ai to´an n`ay c´o liˆen quan d¯ˆe´n nh˜ ´.ng du.ng: c´ac b`ai to´an t`ım h`anh tr`ınh tˆo´tnhˆa´t (ngu.`o.i d¯u.a thu. Trung Hoa, ngu.`o.i ch`ao h`ang), tu.. d¯ˆo.ng ho´a thiˆe´t kˆe´ bˇ`a ng m´ay t´ınh,lˆa.p li.ch, vˆan vˆan. Mˇa.c d`u hai b`ai to´an n`ay d¯u.o..c ph´at biˆe˙’u rˆa´t giˆo´ng nhau, nhu.ng m´ u.c d¯oˆ. kh´o trongviˆe.c gia˙’i quyˆe´t ch´ ung l`a rˆa´t kh´ac nhau. Ch´ung ta s˜e ch´ u.ng minh rˇa` ng trong d¯`ˆo thi. vˆo hu.´o.ng, tˆ u.c t`ım `on ta.i thuˆa.t to´an d¯a th´h`anh tr`ınh Euler v`a b`ai to´an ngu.`o.i d¯u.a thu. Trung Hoa c´o thˆe˙’ d¯u.a vˆ `e t`ım cˇa.p gh´ep ho`an . . ´ ung xem Phˆan 7.5). C´ac thuˆa.t to´an n`ay s˜e d¯u.o..c tr`ınhha˙’o c´o tro.ng lu o. ng nho˙’ nhˆa t [30] (c˜ `b`ay trong c´ac Phˆ `an 5.1 v`a 5.2. Mˇa.t kh´ac, vˆa´n d¯`ˆe tˆ `on ta.i chu tr`ınh hay ma.ch Hamilton l`a nh˜ u.ng b`ai to´an khˆong d¯ath´u.c khˆong d¯u.o..c d¯`ˆe cˆa.p o˙’. d¯ˆay. Ba.n d¯o.c quan tˆam c´o thˆe˙’ xem, chˇa˙’ng ha.n [30]. Ch´ ung tachı˙’ tr`ınh b`ay trong Phˆ `an 5.3 nh˜ u.ng kˆe´t qua˙’ ch´ınh liˆen quan d¯ˆe´n su.. tˆ `on ta.i cu˙’a c´ac chu tr`ınhhay ma.ch Hamilton. Khi c´o d¯iˆ `eu kiˆe.n, c´ac ch´ u.ng minh c´o t´ınh kiˆe´n thiˆe´t thuˆa.t to´an hoˇa.cc´o thˆe˙’ d¯`ˆe xuˆa´t nh˜. . . u ng phu o ng ph´ap heuristic.5.1 B` ai to´ an Euler- i.nh ngh˜ıa 5.1.1 Gia˙’ su˙’. G = (V, E) l`a d¯`oˆ thi. vˆo hu.´o.ng (d¯o.n hoˇa.c d¯a d¯`ˆo thi.). Dˆay chuyˆD `en 127 http://www.ebook.edu.vnEuler l`a dˆay chuyˆ u.a tˆa´t ca˙’ c´ac ca.nh cu˙’a d¯`oˆ thi., mˆo˜i ca.nh d¯u `en ch´ `an. Chu tr`ınh ´ng mˆo.t lˆ `en Euler m`a d¯ı˙’nh d¯`ˆau tr`Euler l`a dˆay chuyˆ . ung v´o i d¯ı˙’nh cuˆo´i.V´ı du. 5.1.2 (B`ai to´an Euler) C´ach d¯ˆay khoa˙’ng ba trˇam nˇam, nhiˆ `eu ngu.`o.i dˆan th`anh phˆo´K¨onigsberg cu˙’a nu.´o.c Nga (sau n`ay l`a th`anh phˆo´ Kaliningrat) d¯a˜ t` u.ng thˇa´c mˇa´c vˆa´n d¯`ˆe nhu.sau: Th`anh phˆo´ c´o sˆong Pregel cha˙’y qua, gi˜ u.a sˆong c´o c`u lao Kneiphof, v`a c´o 7 chiˆe´c cˆ `au .bˇa´c qua sˆong nhu trˆen H`ınh 5.1(a); c´o thˆe˙’ d¯i da.o qua khˇa´p c´ac cˆ . `au nhu ng mˆo˜i cˆ `au chı˙’ d¯imˆo.t lˆ . . `an thˆoi khˆong? Nˆe´u ta coi mˆo˜i khu vu. c a, b, c, d cu˙’a th`anh phˆo´ nhu mˆo.t d¯ı˙’nh, mˆo˜i cˆ `au . . ´ ˙ ’ ˙ ’ ` ´qua la.i hai khu vu. c nhu mˆo.t ca.nh nˆoi hai d¯ınh, th`ı ban d¯ˆo th`anh phˆo K¨onigsberg l`a mˆo.td¯`oˆ thi. (H`ınh 5.1(b)). Thˇa´c mˇa´c cu˙’a ngu.`o.i dˆan th`anh phˆo´ ch´ınh l`a: c´o thˆe˙’ v˜e d¯u.o..c d¯`ˆo thi.bˇa` ng mˆo.t n´et b´ut liˆ`en hay khˆong? N´oi c´ach kh´ac: tˆ `on ta.i chu tr`ınh Euler? Nh`a to´an ho.c L. Euler (1707-1783) l`a ngu.`o.i d¯`aˆu tiˆen d¯˜a ch´ u.ng minh b`ai to´an khˆongc´o l`o.i gia˙’i (nˇam 1736, xem [22], [23]), v`a v`ı ...