duybeo_ngo_hihi
New Member
Link tải luận văn miễn phí cho ae Kết Nối
Niên luận tìm đường đi của chu trình hamilton trên đồ thị vô hướng
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:
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
1. NỘI DUNG TRÌNH BÀY
o Giới thiệu bài toán
o Định nghĩa Chu trình Hamilton
o Mô hình bài toán
o Các bước giải quyết bài toán
o Thủ tục mô tả thuật toán
o Thời gian thực hiện
2. GIỚI THIỆU BÀI TOÁN
o 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 hay không tồn tại đường đi.
3. ĐỊNH NGHĨA CHU TRÌNH HAMILTON
o Cho đồ thị G=(V, E) có n đỉnh
o 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
o Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần.
4. 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.
5. MÔ HÌNH BÀI TOÁN (1)
o 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
6. 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
7. CÁC BƯỚC GIẢI QUYẾT BÀI TOÁN
o Gán đỉnh đầu tiên bằng 1
o 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 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 = 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 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.
8. THỦ TỤC MÔ TẢ THUẬT TOÁN
o procedure Try (i: Integer);
o var
o j: Integer;
o 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;
o 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;
9. CÁC THỦ TỤC KHỞI TẠO (1)
o Nhập dữ liệu vào
o procedure Inputdata ;
o var
o i, u, v, m: Integer;
o fs: Text;
o begin
o Assign(fs, InputFilename); Reset(fs);
o FillChar(A, SizeOf(A), False);
o ReadLn(fs, n, m);
o for i := 1 to m do
o begin
o ReadLn(fs, u, v);
o a[u, v] := True;
o a[v, u] := True;
o end;
o Close(fs);
o 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;
10. CÁC THỦ TỤC KHỞI TẠO (2)
o 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.
11. 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 .
12. 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) = < x1 , x2 , ... , xn >
Nếu trong G có cạnh (xn, a) thì đường < (H) , a > sẽ là đường Hamilton.
Nếu trong G có cạnh (a, x1) thì đường < a , (H) > 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 < x1 , ..., xi , a , xi+1 , ..., xn > 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.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Niên luận tìm đường đi của chu trình hamilton trên đồ thị vô hướng
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:
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
1. NỘI DUNG TRÌNH BÀY
o Giới thiệu bài toán
o Định nghĩa Chu trình Hamilton
o Mô hình bài toán
o Các bước giải quyết bài toán
o Thủ tục mô tả thuật toán
o Thời gian thực hiện
2. GIỚI THIỆU BÀI TOÁN
o 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 hay không tồn tại đường đi.
3. ĐỊNH NGHĨA CHU TRÌNH HAMILTON
o Cho đồ thị G=(V, E) có n đỉnh
o 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
o Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần.
4. 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.
5. MÔ HÌNH BÀI TOÁN (1)
o 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
6. 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
7. CÁC BƯỚC GIẢI QUYẾT BÀI TOÁN
o Gán đỉnh đầu tiên bằng 1
o 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 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 = 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 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.
8. THỦ TỤC MÔ TẢ THUẬT TOÁN
o procedure Try (i: Integer);
o var
o j: Integer;
o 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;
o 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;
9. CÁC THỦ TỤC KHỞI TẠO (1)
o Nhập dữ liệu vào
o procedure Inputdata ;
o var
o i, u, v, m: Integer;
o fs: Text;
o begin
o Assign(fs, InputFilename); Reset(fs);
o FillChar(A, SizeOf(A), False);
o ReadLn(fs, n, m);
o for i := 1 to m do
o begin
o ReadLn(fs, u, v);
o a[u, v] := True;
o a[v, u] := True;
o end;
o Close(fs);
o 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;
10. CÁC THỦ TỤC KHỞI TẠO (2)
o 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.
11. 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 .
12. 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) = < x1 , x2 , ... , xn >
Nếu trong G có cạnh (xn, a) thì đường < (H) , a > sẽ là đường Hamilton.
Nếu trong G có cạnh (a, x1) thì đường < a , (H) > 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 < x1 , ..., xi , a , xi+1 , ..., xn > 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.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: