Download miễn phí Niên Luận Tìm chu trình Hamilton
MỤC LỤC
ĐÁNH GIÁ KẾT QUẢ THỰC HIỆN NIÊN LUẬN 1 1
NHẬN XÉT 2
CHƯƠNG 01 : TỔNG QUAN .5.
I. GIỚI THIỆU 5.
II.MỤC TIÊU CẦN ĐẠT ĐƯỢC 5.
III.HƯỚNG GIẢI QUYẾT 5.
CHƯƠNG 02 : LÝ THUYẾT 5
1 NỘI DUNG TRÌNH BÀY 6
2 GIỚI THIỆU BÀI TOÁN .6
3 ĐỊNH NGHĨA CHU TRÌNH HAMILTON 6
4 VÍ DỤ VỀ CHU TRÌNH VÀ ĐƯỜNG ĐI HAMILTON 6
5 MÔ TẢ BÀI TOÁN (1).6
6 MÔ TẢ BÀI TOÁN (1).6
7 CÁC BƯỚC GIẢI QUYẾT BÀI TOÁN .6
8 THỦ TỤC MÔ TẢ THUẬT TOÁN .7
9 CÁC THỦ TỤC KHỞI TẠO (1).7
10 CÁC THỦ TỤC KHỞI TẠO (1).8
11 THỜI GIAN THỰC HIỆN . 8
12 MỘT SỐ VÍ DỤ VÀ CÁC ĐỊNH LÝ MINH HỌA .8
CHƯƠNG 03: ỨNG DỤNG 13
1 GIỚI THIỆU CHƯƠNG TRÌNH 33.
CHƯƠNG 04: KẾT LUẬN 34.
I. NHẬN XÉT KẾT QUẢ ĐẠT ĐƯỢC 34.
II. HẠN CHẾ 34.
III. HƯỚNG PHÁT TRIỂN 34.
CHƯƠNG 05: CHƯƠNG TRÌNH DEMO 34.
I .GIAO DIỆN 35.
II.HƯỚNG DẪN CHƯƠNG TRÌNH 37.
TÀI LIỆU THAM KHẢO.38
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-04-10-nien_luan_tim_chu_trinh_hamilton.PcqSW2ZKZx.swf /tai-lieu/de-tai-ung-dung-tren-liketly-5956/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
đỉnh j là đã đi qua để cho các bước tiếp theo không chọn j nữa.
Sau đó chọn đỉnh thứ i+1 trong hành trình
Thử phương án khác cho X
nên sẽ bỏ đánh dấu đỉnh vừa thử
Ngược lại , nếu đã thử chọn đến X[n] thì kiểm tra nếu X[n] lại kề với X[1] thì ta có chu trình Hamilton.
THỦ TỤC MÔ TẢ THUẬT TOÁN
procedure Try (i: Integer);
var
j: Integer;
begin
for j := 1 to n do
if Mask[j] and A[X[i - 1], j] then
begin
X := j;
if i < n then
begin
Mask[j] := False;
Try(i + 1);
Mask[j] := True;
end
else
if A[j, X[1]] then Print;
end;
end;
Khai báo Const Max=50; Inputfilename=‘D:BPBININPUT.PAS’ Outputfilename=‘D:BPBINOUTPUT.PAS’ var ft: Text; A: array[1..max, 1..max] of Boolean; Mask: array[1..max] of Boolean; X: array[1..max] of Integer; n: Integer;
CÁC THỦ TỤC KHỞI TẠO (1)
Nhập dữ liệu vào
procedure Inputdata ;
var
i, u, v, m: Integer;
fs: Text;
begin
Assign(fs, InputFilename); Reset(fs);
FillChar(A, SizeOf(A), False);
ReadLn(fs, n, m);
for i := 1 to m do
begin
ReadLn(fs, u, v);
a[u, v] := True;
a[v, u] := True;
end;
Close(fs);
end;
In kết quả procedure Print; var i: Integer; begin for i := 1 to n do Write(ft, X, ' '); WriteLn(ft, X[1]); writeln; end;
CÁC THỦ TỤC KHỞI TẠO (2)
Chương trình chính
BEGIN
Inputdata;
FillChar(Mask, SizeOf(Mask), True);
X[1] := 1; Mask[1] := False;
Assign(ft, Outputfilename); Rewrite(ft);
Try(2);
Close(ft);
readln;
END.
THỜI GIAN THỰC HIỆN T(n) = O(n*m) trong đó n là số đỉnh và m là số cạnh giữa các đỉnh 1 5 4 2 3 3 1 2 4 5 3 2 1 3 1 2 3 5 2 1 5 1 2 5 4 1 3 3 4 1 1 5 4 5 1 4 Đồ thị có 5 đỉnh và 7 cạnh Cây liệt kê chu trình Hamilton của đồ thị theo thuật toán quay lui .
MỘT SỐ VÍ DỤ VÀ CÁC ĐỊNH LÝ MINH HỌA :
- Chu trình Hamilton : Năm 1857 W. R. Hamilton, nhà toán học người Ailen đã đưa ra trò chơi sau đây: Trên mỗi đỉnh trong số 20 đỉnh của một khối đa diện 12 mặt ngũ giác đều có ghi tên một thành phố lớn của thế giới. Hãy tìm cách đi bằng các cạnh của khối này để đi qua tất cả các thành phố, mỗi thành phố đúng một lần.
Bài toán này đã dẫn tới những khái niệm sau đây.
Định nghĩa 7.5: Đường Hamilton là đường đi qua mỗi đỉnh của đồ thị đúng một lần. Chu trình Hamilton là chu trình đi qua mỗi đỉnh của đồ thị đúng một lần.
Ví dụ 7.6:
1. Tổ chức tour du lịch sao cho người du lịch thăm quan mỗi thắng cảnh trong thành phố đúng một lần.
2. Cho quân mã đi trên bàn cờ vua sao cho nó đi qua mỗi ô đúng một lần (bài toán mã đi tuần).
Với một đồ thị đã cho, đường (chu trình) Hamilton có thể tồn tại hay không.
Ví dụ 7.7:
Hình 7.6. Đồ thị có và đồ thị không có chu trình Hamilton
Định lý 7.6 (Rédei): Đồ thị đầy đủ luôn có đường đi Hamilton.
Chứng minh:
Xét đồ thị có hướng G.
Ta chứng minh bằng quy nạp theo số đỉnh n của G.
n = 1, 2 : hiển nhiên.
(n) ⇒ (n+1) : Giả sử G là đồ thị đầy đủ có n+1 đỉnh và đồ thị G’ xây dựng từ
G bằng cách bớt một đỉnh a và các cạnh kề với a. Đồ thị G’ có n đỉnh và cũng đầy đủ nên theo giả thiết quy nạp, nó có đường Hamilton:
(H) =
Nếu trong G có cạnh (xn, a) thì đường sẽ là đường Hamilton.
Nếu trong G có cạnh (a, x1) thì đường sẽ là đường Hamilton.
Trong trường hợp ngược lại, đồ thị G phải có các cạnh (a, xn) và (x1, a) nghĩa là có các cạnh ngược hướng nhau. Khi đó sẽ phải có ít nhất một cặp cạnh sát nhau nhưng ngược hướng nhau là (xi, a) và (a, xi+1).
Hình 7.7. Cách tìm đường đi Hamilton
Ta có đường là một đường đi Hamilton của G. ð
Đồ thị G được gọi là đồ thị có bậc 1 nếu tại mỗi đỉnh có đúng một cạnh vào và một cạnh ra. Hiển nhiên, chu trình Hamilton là một đồ thị riêng bậc 1 của đồ thị đã cho.
Định lý 7.7: Đồ thị G = (V, F) có đồ thị riêng bậc 1 khi và chỉ khi:
∀ B ⊆ V, | B | ≤ | F(B) |.
Chứng minh: Ký hiệu tập đỉnh của đồ thị là V = {a1, a2, ... , an}. Lập tập V’ = {b1,
b2, ... , bn} sao cho: V∩V’ = ∅. Ta xây dựng đồ thị hai phần H = (V, V’, F’) với:
bj ∈F’(ai) ⇔ aj ∈F(ai)
Hình 7.8. Cách xây dựng đồ thị hai phần
Nếu đồ thị G có đồ thị riêng bậc 1 là G1 = (V, F1) thì xét tập cạnh W của H như sau: (ai, bj) ∈W ⇔ aj ∈ F1(ai). Đó là một cặp ghép n cạnh trong H.
Ngược lại, ứng với một cặp ghép n cạnh W trong H sẽ có một đồ thị riêng bậc 1 của G.
Theo Hệ quả 5.4 thì:
| W | = n ≤ | V | - d0 ⇒ d0 = 0
mà d0 = max {| B | - | F’(B) | ⏐B ⊆ V} =
= max {| B | - | F(B) | ⏐B ⊆ V} = 0
Suy ra: | B | ≤ | F(B) |. Đó là điều phải chứng minh. ð
Ví dụ 7.8: Xét đồ thị có hướng G = (V, F) được cho trong hình vẽ dưới đây.
Hình 7.9. Đồ thị định hướng và đồ thị hai phần tương ứng
Đặt V’ = {1, 2, 3, 4} và xây dựng đồ thị hai phần H. Chọn cặp ghép lớn nhất
W = {(a, 2), (b, 3), (c, 4), (d, 1)}. Từ đó xây dựng được chu trình Hamilton cho đồ thị G là [a, b, c, d].
Hệ quả 7.8: Nếu đồ thị G có chu trình Hamilton thì:
∀ B ⊆ V , | B | ≤ | F(B) |.
Chứng minh:
Vì chu trình Hamilton là đồ thị riêng bậc 1. Điều ngược lại là không đúng vì đồ thị riêng có thể gồm nhiều mảng liên thông rời nhau. ð
Từ Hệ quả này chúng ta có thể khẳng định rằng: Nếu trong đồ thị có một tập con B các đỉnh mà | B | > | F(B) | thì đồ thị này không có chu trình Hamilton.
Hệ quả 7.9: Giả sử đồ thị có hướng G có đường đi Hamilton.
Ký hiệu: d = max {| B | - | F(B) |⏐B ⊆ V}. Khi đó, số d ∈ {0, 1}.
Chứng minh:
Giả sử đồ thị có hướng G có đường đi Hamilton .
Nếu trong đồ thị G có cạnh (b, a) thì G có chu trình Hamilton và theo Hệ quả 7.8 thì d = 0.
Ngược lại, giả sử __________đồ thị G không có cạnh (b, a). Xét đồ thị G’ xây dựng từ đồ thị G và thêm cạnh (b, a). Thế thì đồ thị G’ sẽ có d' = 0. Mặt khác, vì ta chỉ thêm một cạnh mà không thêm đỉnh, nên: d ≤ d' + 1. Từ đó suy ra d ≤ 1. ð
Cũng theo Hệ quả này chúng ta có thể khẳng định rằng: Nếu đồ thị nào đó có d ≥ 2 thì đồ thị ấy không có đường đi Hamilton.
Bổ đề 7.10: Giả sử đồ thị G có đường đi đơn vô hướng cực đại .
Nếu r(a0) + r(aq) ≥ q +1 thì đồ thị con G’ tạo bởi tập đỉnh {a0, a1, ..., aq} có chu trình vô hướng Hamilton.
Chứng minh:
Ký hiệu r'(a) là bậc của đỉnh a trong G’. Vì đường đơn đã đánh giá là cực đại nên: r'(a0) = r(a0), r'(aq) = r(aq).
Hình 7.10. Cách tìm chu trình Hamilton
Giả sử r(a0) = k, nghĩa là đỉnh a0 kề với k đỉnh trên đường đi là a1 , ai2 , ... , aik.
- Nếu a0 kề với aq thì G’ có chu trình vô hướng Hamilton.
- Nếu như aq không kề với a0 , ai2-1 , ... , aik-1. Đó là những đỉnh nằm bên trái của dãy đỉnh trong đường đi nói trên.
Thế thì: r(aq) ≤ q - k. Do đó: r(a0) + r(aq) ≤ q, trái với giả thiết. Vậy phải có ít nhất một đỉnh ai-1 sao cho a0 kề với ai và aq
kề với ai-1. Khi đó dãy các đỉnh [a0 , ai , ... , aq , ai-1, ..., a0] là một chu trình vô hướng của G’. ð
Bổ đề 7.11: Giả sử đồ thị G liên thông.
Nếu các đỉnh của đường đi đơn vô hướng dài nhất tạo nên một đồ thị con G’ có chu trình vô hướng Hamilton thì chu trình đó cũng chính là chu trình vô hướng Hamilton của đồ thị G.
Chứng minh:
Ta chỉ cần chứng minh rằng, đồ thị con G’ chính là đồ thị G. Giả sử ngược lại, có đỉnh a thuộc G nhưng không thuộc đồ thị con G’. Vì đồ thị G liên thông nên với đỉnh b thuộc G’ sẽ có đường đi vô hướng trong G nối đỉnh b với đỉnh a là .
Hình 7.11. Đường đi nối đỉnh a với chu trình
