Đang chuẩn bị liên kết để tải về 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 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. để biết thêm nội dung chi tiết. | Đồ thị và các thuật toán – Chương 5: Bài toán Euler và bài toán Hamilton Chu.o.ng 5 B` ai to´ an Euler v` a b` ai to´ an Hamilton L´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 Euler v`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 u mˆ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´t nhˆ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.oc ph´at biˆe˙’u rˆa´t giˆo´ng nhau, nhu.ng m´ u.c d¯oˆ. kh´o trong viˆ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.oc tr`ınh ha˙’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¯a th´u.c khˆong d¯u.oc 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 ta chı˙’ 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`ınh hay 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.c c´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.vn Euler l`a dˆay chuyˆ u.a tˆa´t .