Niên luận tìm đường đi của chu trình hamilton trên đồ thị vô hướng

GIÁO VIÊN CHẤM NHẬN XÉT ………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………… GIÁO VIÊN HƯỚNG DẪN NHẬN XÉT ……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………………………………………… 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 Chương 1 Tổng Quan I. GIỚI THIỆU - Lý thuyết đồ thị là một lĩnh vực đã được nghiên cứu từ những năm đầu của thế kĩ 18 bởi nhà toán học Leonhard Euler người Thụy sĩ .Đồ thị được sử dụng để giải nhiều bài toán trong nhiều lĩnh vực khác nhau, trong tin học là một trường hợp cụ thể . - Lý thuyết đồ thị cung cấp một hình thức thuận tiện cho việc mô tả mối liên hệ của các đối tượng được quan tâm, góp phần quan trọng vào việc giải các bài toán phức tạp . II.MỤC TIÊU ĐẠT ĐƯỢC về lý thuyết : - Nắm vững kiền thức về toán rời rạc về cách tìm đường đi của chu trình Hamilton . - Hiểu rỏ về ngôn ngữ lật trình c để giải quyết vấn đề đặt ra. - Cho phép nhập vào các ma trận kề và số đỉnh tự do để tạo ra một chu trình ,từ đó áp dụng phương pháp về cách tìm chu trình Hamilton, để tìm ra đường đi của một chu trình Hamilton từ các thuật toán . về chương trình: - Xây dựng giao diện thân thiện với người sử dụng . Dể sử dụng,kết quả tính toán chính xác. III.HƯỚNG GIẢI QUYẾT Về lý thuyết:tìm hiểu các khái niệm về chu trình Hamilton , sự tồn tại của chu trình Hamilton , điều kiện để có chu trình … và các kiến thức về lập trình trên ngôn ngữ sử dụng để giải quyết yêu cầu đề tài. về chương trình:sử dụng ngôn ngữ lập trình chính là C để viết chương trình ,cài đặt thuật toán theo yêu cầu đề tài ,nghiên cứu cài đặt các thủ tục hàm đồ họa để hỗ trợ giao diện thân thiện với người sử dụng . Chương 2 LÝ THUYẾT NỘI DUNG TRÌNH BÀY Giới thiệu bài toán Định nghĩa Chu trình Hamilton Mô hình bài toán Các bước giải quyết bài toán Thủ tục mô tả thuật toán Thời gian thực hiện GIỚI THIỆU BÀI TOÁN Một người khách du lịch muốn đi thăm n thành phố được đánh số từ 1 đến n. Mạng lưới giao thông giữa n thành phố này là 2 chiều và được cho bởi ma trận A[i,j] trong đó A[i,j] = 1 nếu có đường đi giữa thành phố i và thành phố j, A[i,j] = 0 trong trường hợp ngược lại. Thiết lập đường đi cho người khách thông báo tồn tại đường đi hoặc không tồn tại đường đi. ĐỊNH NGHĨA CHU TRÌNH HAMILTON Cho đồ thị G=(V, E) có n đỉnh Chu trình (x 1 , x 2 , …, x n , x 1 ) được gọi là Chu trình Hamilton nếu x i x j với 1<=i<j<=n Đường đi (x 1 , x 2 , …, x n ) được gọi là Đường đi Hamilton nếu x i x j với 1<=i<j<=n Chu trình Hamilton là chu trình xuất phát từ một đỉnh, đi thăm tất cả những đỉnh còn lại, mỗi đỉnh đúng một lần, cuối cùng quay lại đỉnh xuất phát. Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. VÍ DỤ VỀ CHU TRÌNH VÀ ĐƯỜNG ĐI HAMILTON Một đồ thị đầy đủ có nhiều hơn hai đỉnh là đồ thị Hamilton. Mọi đồ thị vòng là Hamilton. Đồ thị khối ba chiều là đồ thị Haminton. MÔ HÌNH BÀI TOÁN (1) Ta có file: Input: Là file văn bản Input.pas Dòng 1 ghi số đỉnh n<=50 và số cạnh m của đồ thị cách nhau một dấu cách. m dòng tiếp theo, mỗi dòng có dạng 2 số nguyên dương u, v cách nhau một dấu cách, thể hiện u, v là 2 đỉnh kề nhau trong đồ thị. Output: là file văn bản Output.pas Liệt kê tất cả các chu trình Hamilton MÔ HÌNH BÀI TOÁN (2) 1 5 4 2 3 Input.pas Output.pas 5 7 1 2 1 4 2 3 2 5 3 4 3 5 4 5 1 2 3 5 4 1 1 2 5 3 4 1 1 4 3 5 2 1 1 4 5 3 2 1 CÁC BƯỚC GIẢI QUYẾT BÀI TOÁN Gán đỉnh đầu tiên bằng 1 Thử các cách chọn đỉnh thứ i trong hành trình với i>=2 và i<=n. Chọn tất cả các đỉnh j để tìm đỉnh thứ i X[i] kề với X[i-1] và chưa bị đi qua Nếu tìm thấy đỉnh j thỏa mãn điều kiện trên thì gán X[i] = j . Nếu i < n thì Đánh dấ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[i] 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[i] := 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[i], ' '); 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 hoặc 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 đã cho 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 Đỉnh b thuộc G’ còn đỉnh a không thuộc G’. Do vậy, sẽ có đỉnh ai là đỉnh đầu tiên của đường đi không thuộc G’. Xét đường đi sau đây trong đồ thị G: Lấy chu trình vô hướng Hamilton của G’, bỏ đi một cạnh kề với ai-1 và thêm vào cạnh (ai-1, ai). Đường đi này có độ dài bằng số đỉnh của G’, trong khi đó đường đi đơn dài nhất đã cho trong G chỉ có độ dài là số đỉnh của G’ bớt đi 1. Vậy trái với giả thiết. ð Định lý 7.12: Giả sử đồ thị G có n đỉnh. 1) Nếu ∀a, b ∈ V, r(a) + r(b) ≥ n-1 thì G có đường đi vô hướng Hamilton. 2) Nếu ∀a, b ∈ V, r(a) + r(b) ≥ n thì G có chu trình vô hướng Hamilton. Chứng minh: 1) Giả sử là đường đi đơn vô hướng dài nhất của G. Đường đi này có độ dài là q. - Nếu q = n-1 thì đó là đường đi Hamilton của đồ thị G. - Nếu q ≤ n-2 thì r(x0) + r(xq) ≥ n-1 ≥ q +1 và theo Bổ đề 7.10 đồ thị con G’ tạo bởi tập đỉnh {x0 , ..., xq} có chu trình vô hướng Hamilton. Giả sử chu trình vô hướng Hamilton đó là [y0 , y1 , ... , yq]. Vì q ≤ n-2 nên có ít nhất một đỉnh y của G nằm ngoài chu trình trên. Từ 1) suy ra đồ thị G liên thông. Vậy đỉnh y phải nối được với một đỉnh yj nào đó trong chu trình bằng một đường đi đơn vô hướng. Ta nhận được đường đi có độ dài lớn hơn q +1. Vậy mâu thuẫn với tính cực đại của đường đi . Do vậy q = n-1. Đồ thị G luôn có đường đi vô hướng Hamilton. 2) Theo 1) thì trong đồ thị G có đường đi đơn vô hướng dài nhất chứa tất cả n đỉnh là . Hơn nữa, r(y0) + r(yn-1) ≥ n = (n-1) +1, nên theo Bổ đề 7.10 thì đồ thị con G’ sinh bởi tập đỉnh {y0, y1, ... , yn-1} có chu trình vô hướng Hamilton, và đó cũng chính là chu trình Hamilton của đồ thị G. ð Ví dụ 7.9: Xét đồ thị có hướng sau đây. Hình 7.12. Đồ thị có hướng có chu trình vô hướng Hamilton Đồ thị thoả mãn điều kiện 2) nên nó có chu trình vô hướng Hamilton. Nếu ta bỏ cạnh (c, d) thì điều kiện 1) thoả mãn còn điều kiện 2) không thoả mãn nữa. Đồ thị chỉ có đường đi vô hướng Hamilton. Hệ quả 7.13 (Dirac): Nếu ∀a ∈ V, r(a) ≥2n thì đồ thị G có chu trình vô hướng Hamilton. Chứng minh: Suy ra từ phần 2) của Định lý 7.12. ð Một số nhận xét: 1. Đồ thị có đỉnh có bậc ≤ 1 thì không có chu trình Hamilton. 2. Đồ thị có các đỉnh đều có bậc ≥ 2. Nếu có đỉnh nào có bậc bằng 2 thì mọi chu trình Hamilton (nếu có) phải đi qua hai cạnh kề với đỉnh này. 3. Nếu trong đồ thị có đỉnh có ba đỉnh bậc 2 kề với nó thì đồ thị không có chu trình Hamilton. 4. Nếu đỉnh a có hai đỉnh kề bậc 2 là b và c thì mọi cạnh (a, x), x ∉{b, c} sẽ không thuộc bất kỳ chu trình Hamilton nào. 5. Đồ thị có đường đi vô hướng . Với chỉ số k < n và các đỉnh trên đường đi (trừ a1 và ak) đều có bậc 2 thì cạnh (a1,ak) sẽ không thuộc bất kỳ chu trình Hamilton nào. 6. Đồ thị hai phần G = (V1,V2, F) với | V1 | ≠ | V2 | sẽ không có một chu trình Hamilton nào. Chương 3 ỨNG DỤNG 1 GIỚI THIỆU CHƯƠNG TRÌNH: CODE : #include #include #include #include #include #include #include #include #include #define Max 100 #define bp(x) (x)*(x) //#define path "E:\\TC\\BGI\\mouse.h" #define path "E:\\TC\\BGI" //==========Khai bao bien================== typedef struct chitietdinh { float x; float y; }; int sodinh,i; int a[100][100]; int X[100]; int x[100],y[100]; int chuaxet[100]; int j,n,kt=1,ch; int flag=0,v0,spt; int x1,x2,y1,y2,xm,ym,chuottrai,chuotphai,banphim,dinh1,dinh2,dinh3,dinh4; unsigned char rm=0,lm=0; int man_hinh,kieu; int midx=639/2; int midy=479/2; int ke[Max][Max]; chitietdinh ctd[Max]; //============Ham hamilton 1==================== void Hamilton(int k){ int y; for(y=0;y<sodinh;y++) if(a[k][y]!=0){ if((spt==sodinh-1)&&(y==v0)){ flag=1; return; } else if(chuaxet[y]) { spt++; X[spt]=y; chuaxet[y]=0; Hamilton(y); if(flag) return ; chuaxet[y]=1; spt--; } } } //----------Cac ham lien quan den chuot--- //==================khoi tao ma tran ke========= void khoi_tao_ke(int ke[Max][Max]) { int i,j; for(i=1;i<=sodinh;i++) for(j=1;j<=sodinh;j++); ke[i][j]=0; } //-----------ham tinh toa do tam thoi ban dau cua moi dinh-------- void tinhtoado(chitietdinh ctd[Max]) { float goc; goc=2*M_PI/sodinh; int r=2*getmaxx()/7; int i; for(i=1;i<=sodinh;i++) { ctd[i].x=(midx-r*cos(i*goc)); ctd[i].y=midy-r*sin(i*goc)+30; } } //Ve xong luu trong chi tiet dinh ctd[i]:i(1-n:so dinh) //------ve mot dinh----------- void ve_dinh(int chiso,int x, int y) //x,y la toa do cua dinh { char s[1]=""; setcolor(10); circle(x,y,10); floodfill(x,y,10); setcolor(RED); itoa(chiso,s,10); settextjustify(1,1); outtextxy(x,y,s); } //=============ham ve canh========== void in_dinh(int chiso,int x,int y) { char s[1]=""; setcolor(WHITE); itoa(chiso,s,10); settextjustify(1,1); outtextxy(x,y,s); } //---------------------------------- void ve_canh(int ke[Max][Max]) { int i,j; for(i=1;i<=sodinh;i++) for(j=1;j<=sodinh;j++) if(ke[i][j]==1) { line(ctd[i].x,ctd[i].y,ctd[j].x,ctd[j].y); setcolor(13); circle(abs(ctd[i].x+ctd[j].x)/2,abs(ctd[i].y+ctd[j].y)/2,2); floodfill( (ctd[i].x+ctd[j].x)/2,(ctd[i].y+ctd[j].y)/2,13); } } //-------------ham dua ra dang do thi ban dau------------- void vedothibandau(chitietdinh ctd[]) { int i,j; rectangle(0,5,636,479); rectangle(2,7,634,477); cleardevice(); for(i=1;i<=sodinh;i++) { ve_dinh(i,ctd[i].x,ctd[i].y); } ve_canh(ke); show_mouse(); } //======================xoa dinh=========== void xoadinh(int chisodinh) { int i,j,k; for(i=chisodinh;i<=sodinh;i++) for(j=1;j<=sodinh;j++) { ke[i][j]=ke[i+1][j]; ke[j][i]=ke[j+1][i]; } for(k=chisodinh;k<=sodinh;k++) { ctd[k].x=ctd[k+1].x; ctd[k].y=ctd[k+1].y; } sodinh--; } //------------Xoa canh------------------- void xoa_canh(int chiso1,int chiso2) { ke[chiso1][chiso2]=0; ke[chiso2][chiso1]=0; } //-------------Them dinh moi---------- void them_dinh(long x,long y) { int i; sodinh++; ctd[sodinh].x=x; ctd[sodinh].y=y; for(i=1;i<=sodinh;i++) { ke[sodinh][i]=0; ke[i][sodinh]=0; } } //------------ham kiem tra toa do chuot co thuoc dinh nao khong---------- int xy_danhsachdinh(long x, long y, chitietdinh d[Max],int sodinh,int &chiso) { int i; for(i=1;i<=sodinh;i++) if( ( (x-d[i].x)*(x-d[i].x) + (y-d[i].y)*(y-d[i].y)) <=400) { chiso=i; return 1; } return 0; } //==============kiem tra xy thuoc canh============ int xy_danhsachcanh(long x,long y,int &chiso1,int &chiso2) { int i,j; for(i=1;i<sodinh;i++) { for(j=i+1;j<=sodinh;j++) if((ke[i][j]==1)&&( bp(x-(ctd[i].x+ctd[j].x)/2)+ bp(y-(ctd[i].y+ctd[j].y)/2)) <100 ) { chiso1=i; chiso2=j; return 1; } } return 0; } //-----------cho su kien cua chuot||ban phim------------ void sukien(int &banphim,int &chuottrai,int &chuotphai) { setcolor(7); rectangle(0,5,636,479); rectangle(2,7,634,477); show_mouse(); banphim=0; do { get_mouse_button(&lm,&rm,&xm,&ym); } while(!kbhit() && !lm && !rm); x1=xm; y1=ym; if(kbhit()) banphim=getch(); chuottrai=lm; chuotphai=rm; while (lm||rm) { get_mouse_button(&lm,&rm,&xm,&ym); } x2=xm; y2=ym; hide_mouse(); } //---------------ham di chuyen dinh-------------- void di_chuyen_dinh(chitietdinh ctd[Max],int chiso,float x, float y) { ctd[chiso].x=x; ctd[chiso].y=y; } //======================================== //========================Nhap text================== void nhapchuoi(int x, int y,char *tentt) { char ch; tentt[0]=NULL; settextjustify(0,1); do { ch=getch(); if ((97<=ch && ch<=122) || (14<=ch && ch<=95)|| ch==126) { tentt[strlen(tentt)+1]=NULL; tentt[strlen(tentt)]=ch; } if (ch==8) { setcolor(BLACK); outtextxy(x,y,tentt); tentt[strlen(tentt)-1]=NULL; } if (ch==27) { tentt[0]=27; tentt[1]=NULL; ch=13; } setcolor(10); outtextxy(x,y,tentt); } while (ch!=13); } //==============case 1=================== void case1() { char *file; FILE *f; char *pt; //------------------------------------------------ //Khoi tao che do do hoa cleardevice(); setcolor(11); rectangle(0,5,636,479); rectangle(2,7,634,477); rectangle(4,9,632,475); fflush(stdin); setcolor(WHITE); outtextxy(120,20,"------CHUONG TRINH TIM CHU TRINH HAMILTON------"); outtextxy(120,40,"----------TU DO THI CO SAN TRONG FILE----------"); outtextxy(180,60,"---------===(--)===---------"); setcolor(WHITE); outtextxy(30,90,"Huong dan :"); setcolor(12); line(25,100,30+textwidth("Huong dan :"),100); setcolor(13); outtextxy(30,110,"1.Nhap vao ten file co chua ma tran ke."); outtextxy(30,130,"2.Kiem tra ma tran dau vao."); outtextxy(30,150,"3.Mo phong dang do thi nhap vao."); outtextxy(30,170,"4.Tim va in ra chu trinh hamilton neu co."); setcolor(WHITE); outtextxy(180,185,"---------===(--)===---------"); setcolor(WHITE); outtextxy(30,200,"Nhap vao ten file : "); setcolor(12); line(25,210,30+textwidth("Nhap vao ten file :"),210); setcolor(10); nhapchuoi(30+textwidth("Nhap vao ten file : "),204,file); outtextxy(30,220,"Search "); for(i=0;i<6;i++) { outtextxy(30+textwidth("Search ")+4*i,220,"."); delay(500); } f=fopen(file,"r"); if(f==NULL) { outtextxy(30+textwidth("Search......"),220,"==> Khong tim thay file! "); outtextxy(30,460,"Exit "); for(i=0;i<6;i++) { outtextxy(30+textwidth("Exit ")+4*i,460,"."); delay(500); } return; } else outtextxy(30+textwidth("Search......"),220,"==> Da tim thay file ! "); //Kiem tra ma tran ke nhap vao outtextxy(30,240,"Kiem tra ma tran nhap vao "); for(i=0;i<6;i++) { outtextxy(30+textwidth("Kiem tra ma tran nhap vao ")+4*i,240,"."); delay(500); } fscanf(f,"%d",&sodinh); for(i=0;i<sodinh;i++) for(j=0;j<sodinh;j++)fscanf(f,"%d",&a[i][j]); for(i=0;i<sodinh;i++) for(j=0;j<sodinh;j++)if(a[i][j]!=a[j][i]) { kt=0; break; } if(kt==1) { outtextxy(30,260,"==> Ma tran nhap vao thoa yeu cau ! "); outtextxy(30,460,"Waiting "); for(i=0;i<6;i++) { outtextxy(30+textwidth("Waiting ")+4*i,460,"."); delay(500); } } else { outtextxy(30,260,"==> Ma tran nhap vao khong thoa yeu cau ! "); outtextxy(30,460,"Exit "); for(i=0;i<6;i++) { outtextxy(30+textwidth("Exit ")+4*i,460,"."); delay(500); } return ; } //================Thiet lap chu trinh hamilton============== for(i=0;i<sodinh;i++) chuaxet[i]=1; v0=0; spt=0; chuaxet[v0]=0; flag=0; Hamilton(v0); //closegraph(); //---------------------------------------------------- //Ve do thi luc dau //---------------------------------------------------- cleardevice(); setcolor(7); rectangle(0,5,636,479); rectangle(2,7,634,477); setcolor(WHITE); outtextxy(120,40,"--------MO PHONG DANH DO THI NHAP VAO--------"); outtextxy(180,60,"---------===(--)===---------"); setcolor(12); outtextxy(30,440,"Loading"); for(i=0;i<7;i++) { outtextxy(30+textwidth("Loading ")+4*i,440,"."); delay(500); } //=================ve do thi luc dau========================== tinhtoado(ctd); for(i=1;i<=sodinh;i++) { ve_dinh(i,ctd[i].x,ctd[i].y); } setcolor(14); for(i=0;i<sodinh;i++) for(j=0;j<sodinh;j++)if(a[i][j]!=0)line(ctd[i+1].x,ctd[i+1].y,ctd[j+1].x,ctd[j+1].y); setcolor(12); outtextxy(60,460,"Continue"); for(i=0;i<7;i++) { outtextxy(30+textwidth("Continue ")+4*i,460,"."); delay(500); } //closegraph(); //---------------ve do thi luc da xu ly xong--------------------- cleardevice(); setcolor(7); rectangle(0,5,636,479); rectangle(2,7,634,477); setcolor(WHITE); outtextxy(300,40,"--------MO PHONG DUONG DI CHU TRINH HAMILTON--------"); outtextxy(300,60,"-----------===(--)===-----------"); setcolor(WHITE); outtextxy(60,420,"Loading"); for(i=0;i<7;i++) { outtextxy(30+textwidth("Loading ")+4*i,420,"."); delay(500); } setcolor(10); if(flag==0) { outtextxy(195,440,"Do thi tren khong co chu trinh hamilton !"); outtextxy(50,460,"Exit "); for(i=0;i<6;i++) { outtextxy(30+textwidth("Exit ")+4*i,460,"."); delay(500); } return; } for(i=1;i<=sodinh;i++) { ve_dinh(i,ctd[i].x,ctd[i].y); } setcolor(14); for(i=0;i<sodinh;i++) for(j=0;j<sodinh;j++)if(a[i][j]!=0)line(ctd[i+1].x,ctd[i+1].y,ctd[j+1].x,ctd[j+1].y); //Ve duong noi cac dinh delay(1000); setcolor(4); setlinestyle(CENTER_LINE,4,3); for(i=0;i<sodinh-1;i++) { line(ctd[X[i]+1].x,ctd[X[i]+1].y,ctd[X[i+1]+1].x,ctd[X[i+1]+1].y); delay(1000); } line(ctd[X[i]+1].x,ctd[X[i]+1].y,ctd[X[0]+1].x,ctd[X[0]+1].y); setcolor(WHITE); outtextxy(450,470,"Bam phim bat ky de xem chu trinh Hamilton..."); getch(); //closegraph(); //---------------------------------------------------------------- cleardevice(); setlinestyle(SOLID_LINE,0,1); setcolor(7); rectangle(0,5,636,479); rectangle(2,7,634,477); setcolor(WHITE); outtextxy(300,40,"--------XUAT CHU TRINH HAMILTON--------"); outtextxy(300,60,"---------===(--)===---------"); setcolor(10); outtextxy(60,420,"Proccesing"); for(i=0;i<7;i++) { outtextxy(20+textwidth("Proccessing ")+4*i,420,"."); delay(500); } outtextxy(128,440,"==>Chu trinh Hamilton la : "); setcolor(YELLOW); for(i=0;i<sodinh;i++)in_dinh(X[i]+1,50+textwidth("Chu trinh hamilton la : ")+12*i,440); in_dinh(X[0]+1,50+textwidth("Chu trinh hamilton la : ")+12*i,440); setcolor(WHITE); outtextxy(35,460,"Exit"); for(i=0;i<6;i++) { outtextxy(30+textwidth("Exit ")+4*i,460,"."); delay(500); } /*int tl; FILE *pp; textcolor(YELLOW); gotoxy(2,4); cprintf(" Luu lai ?"); textcolor(7); gotoxy(4,5); cprintf("1==> Co luu."); gotoxy(4,6); cprintf("0==> Khong luu."); textcolor(YELLOW); gotoxy(2,7); cprintf(" ==>Tra loi : "); scanf("%d",&tl); if(tl==1) { pp=fopen("d:/Hamilton.txt","wt"); for(i=0;i<sodinh;i++)fprintf(pp,"%4d",X[i]+1); } fclose(pp); initgraph(&man_hinh,&kieu,path);*/ cleardevice(); outtextxy(100,20,"Cam on ban da su dung chuong trinh nay !"); } //===================================================== //-----------------------case 2------------------------ void case2() { cleardevice(); reset_mouse(); fflush(stdin); setcolor(12); rectangle(0,5,636,479); rectangle(2,7,634,477); rectangle(4,9,632,475); setcolor(11); outtextxy(120,30,"------CHUONG TRINH TIM CHU TRINH HAMILTON------"); outtextxy(120,50,"----------TU DO THI TU VE BANG CHUOT-----------"); outtextxy(180,70,"---------===(--)===---------"); setcolor(WHITE); outtextxy(30,100,"Huong dan :"); setcolor(12); line(25,110,30+textwidth("Huong dan :"),110); setcolor(YELLOW); outtextxy(30,120,"1.Nhap vao so dinh cua do thi."); outtextxy(30,140,"2.Dung chuot phai de xoa dinh va canh neu can."); outtextxy(30,160,"3.Dung chuot trai de tao dinh va canh noi giua cac dinh."); outtextxy(30,180,"4.Nhan Esc de thoat khoi viec ve do thi."); setcolor(WHITE); outtextxy(180,195,"---------===(--)===---------"); setcolor(WHITE); outtextxy(30,210,"Nhap vao so dinh ban dau cua do thi : "); printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n ==> "); scanf("%d",&sodinh); khoi_tao_ke(ke); tinhtoado(ctd); vedothibandau(ctd); do{ setcolor(WHITE); rectangle(0,5,636,479); rectangle(2,7,634,477); sukien(banphim,chuottrai,chuotphai); if(chuottrai) { if(xy_danhsachdinh(x1,y1,ctd,sodinh,dinh1)&&!xy_danhsachdinh(x2,y2,ctd,sodinh,dinh2)) di_chuyen_dinh(ctd,dinh1,x2,y2); if(xy_danhsachdinh(x1,y1,ctd,sodinh,dinh1)&&xy_danhsachdinh(x2,y2,ctd,sodinh,dinh2)&&x1!=x2) { ke[dinh1][dinh2]=1; ke[dinh2][dinh1]=1; } if(!xy_danhsachdinh(x2,y2,ctd,sodinh,dinh2)) them_dinh(x2,y2); } if(chuotphai) if(xy_danhsachdinh(x2,y2,ctd,sodinh,dinh1)) xoadinh(dinh1); if(xy_danhsachcanh(x2,y2,dinh3,dinh4)) { xoa_canh(dinh3,dinh4); dinh3=dinh4=0; } vedothibandau(ctd); } while(banphim!=13); setcolor(WHITE); rectangle(0,5,636,479); rectangle(2,7,634,477); //----------------------Thiet lap ma tran ke----------- for(i=0;i<sodinh;i++) for(j=0;j<sodinh;j++)a[i][j]=ke[i+1][j+1]; //--------------Thiet lap chu trinh Hamilton----------- for(i=0;i<sodinh;i++) chuaxet[i]=1; v0=0; spt=0; chuaxet[v0]=0; flag=0; Hamilton(v0); //closegraph(); //---------------Ve danh do thi dau vao----------------- cleardevice(); setcolor(7); rectangle(0,5,636,479); rectangle(2,7,634,477); setcolor(11); outtextxy(300,40,"--------MO PHONG DUONG DI CHU TRINH HAMILTON--------"); outtextxy(300,60,"-----------===(--)===-----------"); setcolor(10); outtextxy(60,420,"Loading"); for(i=0;i<7;i++) { outtextxy(30+textwidth("Loading ")+4*i,420,"."); delay(500); } setcolor(10); if(flag==0) { for(i=1;i<=sodinh;i++) for(j=1;j<=sodinh;j++)ke[i][j]=0; outtextxy(195,440,"Do thi tren khong co chu trinh hamilton !"); outtextxy(50,460,"Exit "); for(i=0;i<6;i++) { outtextxy(30+textwidth("Exit ")+4*i,460,"."); delay(500); } return; } for(i=1;i<=sodinh;i++) { ve_dinh(i,ctd[i].x,ctd[i].y); } setcolor(11); for(i=0;i<sodinh;i++) for(j=0;j<sodinh;j++)if(a[i][j]!=0)line(ctd[i+1].x,ctd[i+1].y,ctd[j+1].x,ctd[j+1].y); //Ve duong noi cac dinh delay(1000); setcolor(12); setlinestyle(CENTER_LINE,4,3); for(i=0;i<sodinh-1;i++) { line(ctd[X[i]+1].x,ctd[X[i]+1].y,ctd[X[i+1]+1].x,ctd[X[i+1]+1].y); delay(1000); } line(ctd[X[i]+1].x,ctd[X[i]+1].y,ctd[X[0]+1].x,ctd[X[0]+1].y); setcolor(10); outtextxy(450,470,"Bam phim bat ky de xem chu trinh Hamilton..."); getch(); //---------------------------------------------------------------- cleardevice(); setlinestyle(SOLID_LINE,0,1); setcolor(7); rectangle(0,5,636,479); rectangle(2,7,634,477); setcolor(WHITE); outtextxy(300,40,"--------XUAT CHU TRINH HAMILTON--------"); outtextxy(300,60,"---------===(--)===---------"); setcolor(10); outtextxy(60,420,"Proccesing"); for(i=0;i<7;i++) { outtextxy(20+textwidth("Proccessing ")+4*i,420,"."); delay(500); } outtextxy(128,440,"==>Chu trinh Hamilton la : "); setcolor(YELLOW); for(i=0;iChu trinh hamilton la : ")+12*i,440); in_dinh(X[0]+1,50+textwidth("==>Chu trinh hamilton la : ")+12*(i+1),440); setcolor(10); outtextxy(35,460,"Exit"); for(i=0;i<6;i++) { outtextxy(30+textwidth("Exit ")+4*i,460,"."); delay(500); } cleardevice(); outtextxy(100,20,"Cam on ban da su dung chuong trinh nay !"); for(i=1;i<=sodinh;i++) for(j=1;j<=sodinh;j++)ke[i][j]=0; /* closegraph(); fflush(stdin); int tl; FILE *pp; textcolor(YELLOW); gotoxy(2,4); cprintf(" Luu lai ?"); textcolor(7); gotoxy(4,5); cprintf("1==> Co luu."); gotoxy(4,6); cprintf("0==> Khong luu."); textcolor(YELLOW); gotoxy(2,7); cprintf(" ==>Tra loi : "); scanf("%d",&tl); fflush(stdin); if(tl==1) { pp=fopen("d:/Hamilton.txt","wt"); for(i=0;i<sodinh;i++)fprintf(pp,"%4d",X[i]+1); } fclose(pp); initgraph(&man_hinh,&kieu,path);*/ } //------------------------------------------------------------- void welcome() { //ve cac hinh chu nhat line(1,80,90,80); line(90,80,90,240); line(1,240,90,240); line(450,90,637,90); line(450,90,450,220); line(450,220,637,220); line(300,360,470,360); line(300,360,300,480); line(470,360,470,480); rectangle(1,5,637,479); rectangle(45,160,190,360); rectangle(120,260,360,400); rectangle(360,20,520,120); rectangle(420,280,600,410); rectangle(30,300,150,430); rectangle(280,180,510,310); rectangle(140,60,410,240); setlinestyle(0,0,3); rectangle(110,140,490,250); //do mau vao setfillstyle(1,12); setcolor(getmaxcolor()); floodfill(220,250,getmaxcolor()); floodfill(20,10,getmaxcolor()); floodfill(180,450,getmaxcolor()); floodfill(540,450,getmaxcolor()); floodfill(400,330,getmaxcolor()); setfillstyle(1,15); floodfill(430,160,getmaxcolor()); floodfill(275,175,getmaxcolor()); floodfill(112,145,getmaxcolor()); floodfill(185,165,getmaxcolor()); floodfill(285,185,getmaxcolor()); floodfill(112,185,getmaxcolor()); floodfill(455,210,getmaxcolor()); floodfill(445,185,getmaxcolor()); floodfill(485,145,getmaxcolor()); floodfill(200,245,getmaxcolor()); } //-------------------gioi thieu----------------------- void gioithieu() { welcome(); setcolor(15); rectangle(0,3,636,477); rectangle(1,4,634,476); rectangle(2,5,632,475); setcolor(WHITE); moveto(155,90); outtext("****** TRUONG DAI HOC BAC LIEU ******"); moveto(175,110); outtext("*** KHOA CONG NGHE THONG TIN ***"); setcolor(12); moveto(190,160); outtext("------=====(-><-)=====------"); moveto(170,140); outtext("*********& NIEN LUAN 1 &*********"); line(170,150,170+textwidth("*********& NIEN LUAN 1 &*********"),150); setcolor(0); moveto(230,180 ); outtext("CHU TRINH HAMILTON"); moveto(170,200); outtext("CHUONG TRINH TIM CHU TRINH HAMILTON"); setcolor(12); moveto(190,220); outtext("------=====(*__*)=====------"); setcolor(0); moveto(110,240); outtext(" GVHD:Tran Phuoc Nghia ** SVTH:Nguyen Duong Phat"); getch(); } //---------------------------------------------------- void gioithieu1() { setcolor(11); rectangle(0,5,636,479); rectangle(2,7,632,475); rectangle(4,9,628,471); moveto(230,50); setcolor(WHITE); outtext(" TRUONG DAI HOC BAC LIEU "); moveto(230,70); outtext(" KHOA CONG NGHE THONG TIN "); moveto(250,120); setcolor(YELLOW); outtext("Nguoi Thuc Hien :"); line(250,130,250+textwidth("Nguoi thuc hien :"),130); moveto(160,160); setcolor(YELLOW); outtext("**");setcolor(WHITE); outtext(" Nguyen Duong Phat ");setcolor(YELLOW); moveto(370,160);outtext("MSSV:");setcolor(WHITE);moveto(420,160);outtext("1TH3037"); moveto(160,180); outtext("** Giang Vien Huong Dan : Tran Phuoc Nghia **"); setcolor(WHITE); outtextxy(20,460,"Bam phim bat ky de thoat khoi chuong trinh......"); getch(); } //==================================================== //----------------------Chon menu--------------------- //==================================================== char chon() { setcolor(WHITE); outtextxy(30,100,"Menu :"); setcolor(12); line(25,110,30+textwidth("Menu :"),110); setcolor(11); outtextxy(30,120,"1.Tim chu trinh Hamilton tu do thi co san trong file text..."); delay(1000); outtextxy(30,140,"2.Tim chu trinh Hamilton tu do thi tu ve..."); delay(1000); outtextxy(30,160,"3.Thoat khoi chuong trinh..."); setcolor(WHITE); outtextxy(180,180,"---------===(--)===---------"); setcolor(WHITE); outtextxy(30,200,"Lua chon"); setcolor(12); line(25,210,30+textwidth("Lua chon"),210); return getch(); } //======================Main()======================== void main() { int lc,tt; man_hinh=VGA; kieu=VGAHI; initgraph(&man_hinh,&kieu,path); //------------------------------------------------- //===============Gioi thieu nguoi thuc hien========= gioithieu(); do{ initgraph(&man_hinh,&kieu,path); cleardevice(); setcolor(9); rectangle(0,5,636,479); rectangle(2,7,634,477); rectangle(4,9,632,475); setcolor(WHITE); outtextxy(120,20,"------CHUONG TRINH TIM CHU TRINH HAMILTON------"); outtextxy(120,40,"-------------TRONG DO THI VO HUONG-------------"); outtextxy(180,60,"---------===(--)===---------"); lc=chon(); switch (lc) { case '1':case1();break; case '2':case2();break; case '3':cleardevice();gioithieu1();return; } closegraph(); }while(lc!=3); } Chương 4 KẾT LUẬN I. KẾT QUẢ ĐẠT ĐƯỢC Sau gần tám tuần nghiên cứu và tìm hiểu đề tài, cùng với sự hướng dẫn tận tình của thầy cô và sự giúp đỡ của bạn bè. Hôm nay, Niên Luận cơ bản đã được hoàn thành và đạt được một số kết quả như sau : - Hiểu và cài đặt được các thuật toán đã được yêu cầu bằng ngôn ngữ C biết cách sử dụng các thao tác và các hàm trong C. - Chương trình chạy ổn định, giao diện thân thiện với người dùng và dễ sử dụng, có thể nhập dữ liệu trực tiếp từ bàn phím. - Chương trình được thiết kế dưới dạng các chương trình con độc lập nhau nên dễ dàng kiểm tra và sửa chữa khi yêu cầu chỉnh sửa. II. HẠN CHẾ - Mặc dù có cố gắng để hoàn thành Niên Luận 1, nhưng đây là lần đầu tiên viết một chương trình hoàn chỉnh nên vẫn còn thiếu nhiều kinh nghiệm trong kỹ thuật lập trình cũng như trong cách tổ chức dữ liệu. Mặt khác, do thời gian hạn chế nên chương trình vẫn còn nhiều sai xót ngoài ý muốn. - Có thể giao diện còn chưa đáp đầy đủ các chức năng người sử dụng yêu cầu. III. HƯỚNG PHÁT TRIỂN - Thiết kế giao diện thân thiện với người sữ dung. - Cải tiến chương trình đầy đủ và hoàn thiện hơn. - Phát triển chương trình sang các ngôn ngữ khác như Turbo, Visua Basic, Java,…để được hổ trợ nhiều hơn. Chương 5 CHƯƠNG TRÌNH DEMO I.GIAO DIỆN : Giao diện chính của chương trình: II.HƯỚNG DẪN SỬ DỤNG Chạy từ file Hamilton.exe vào giao diện chính của chương trình . Nhấn phím bất kỳ để tiếp tục . Chọn theo hướng dẫn của Menu . - Chọn 1 Tìm chu trình Hamilton từ đồ thị có sẵn trong file text … In ra số đỉnh và đường đi của chu trình Hamilton từ ma trận nhập vào … Xuất ra chu trình Hamilton là … - Chọn 3 để thoát khỏi chương trình …. TÀI LIỆU THAM KHẢO 1) A. Aho, J. Ullman, Data Structures and Algorithms 2) Wirth, Chương trình = Cấu trúc dữ liệu + Giải thuật 3) Nguyễn Trung Trực, Cấu trúc dữ liệu  - ĐHBK TP HCM 4) Robert Sedgewick, Cẩm nang thuật toán 1,2 5) Đoàn Nguyên Hải, Lập trình căn bản 6) Nguyễn Văn Linh, Giáo trình Giải thuật -