Cách tìm đường đi và chu trình hamilton bằng code java

Xin chào tất cả các bạn đã ghé thăm blog của Phong nè,chúc các bạn đầu tuần vui vẻ nhé!Ahihi

Đầu tiên là xin lổi các bạn vì thời gian qua Phong hơi bận nên không cập nhật blog thường xuyên nè,hôm nay Phong bù đắp các bạn nè.Hôm nay Phong sẽ cập nhật code về phần tìm đường đi và chu trình hamilton.Thì về cấu trúc bài này giống giống phần bài tìm đường đi và chu trình euler nếu bạn nào chưa xem bài này thì quay lại xem để hiểu thêm nhé.

Như thường lệ thì mình lướt sơ qua lý thuyết một chút nhé!Tham khảo trang wiki luôn nè:

Cho đồ thị G = (V,E), có n đỉnh
Đường đi x0,x1,...,xn-1,xn là đường đi Hamilton nếu V = {x0,x1,...,xn-1,xn} xi!=xj , 0 ≤ i < j ≤ n
Chu trình x0,x1,...,xn,x0 là chu trình Hamilton nếu x0,x1,...,xn là đường đi Hamilton
-Dây chuyền Hamilton là dây chuyền đi qua các đỉnh của đồ thị và đi qua mỗi đỉnh đúng 1 lần.
-Chu trình Hamilton là dây chuyền Hamilton xuất phát từ một đỉnh, đi qua tất cả các đỉnh khác của đồ thị, mỗi đỉnh đúng một lần và quay trở về nơi xuất phát.
-Đồ thị Hamilton là đồ thị có chứa ít nhất một chu trình Hamilton.

Các định lý hỗ trợ cho việc kiểm tra đồ thị có chu trình hay đường đi hamilton không :

-Cho đồ thị G có n đỉnh, bao đóng cl(G) được tạo ra từ G bằng cách bổ sung cho mỗi cặp đỉnh không kề nhau u và v với degree(v) + degree(u) ≥ n một cạnh mới uv.
-Dirac (1952) Xét G là đơn đồ thị vô hướngvới n đỉnh (n ≥ 3). Nếu d(x) ≥ n/2 với mọi đỉnh x của G thì G là đồ thị Hamilton.
-Ore (1960) Một đồ thị có n đỉnh (n > 2) là Hamilton nếu tổng các bậc của hai đỉnh không kề nhau đều bằng n hoặc lớn hơn.
-Định lý Bondy-Chvátal(1972) Một đồ thị là Hamilton nếu và chỉ nếu bao đóng của nó là Hamilton. Vì đồ thi đầy đủ là Hamilton, nên tất cả các đồ thị mà bao đóng đầy đủ là Hamilton.
-Ghouila-Houiri (1960) Một đồ thị liên thông mạnh với n đỉnh là đồ thị Hamilton nếu mọi đỉnh có bậc ≥ n
-Meyniel(1973) Một đồ thị liên thông mạnh với n đỉnh là đồ thị Hamilton nếu d(x)+d(y) ≥ 2n-1 với mọi cặp đỉnh x,y không kề nhau.
==>Đồ thị đủ luồn là đồ thị Hamilton, với n lẻ ≥ 3 thì Kn(Kn là đồ thị đủ với n đỉnh) có (n-1)/2 chu trình Hamilton đôi một không có cạnh chung.

Quy tắc để tìm chu trình Hamilton

Hiện nay, dù chưa tìm ra thuật toán tổng quát, nhưng có một số quy tắc khá tốt để sử dụng trong quá trình tìm chu trình Hamilton trong đồ thị. Những quy tắc này có thể phối hợp với nhận xét về các tính chất đối xứng hay về tính chất nào đó của một đồ thị cụ thể để khỏi phải xét nhiều trường hợp khác nhau.
Xét đồ thị G=(X,E) gồm n đỉnh, trong quá trình tìm chu trình Hamilton chúng ta có thể vận dụng 4 quy tắc sau đây:
Quy tắc 1: Lấy hết các cạnh kề với đỉnh bậc 2.
Quy tắc 2: Không cho phát sinh chu trình ít hơn n cạnh.
Quy tắc 3: Nếu đã lấy 2 cạnh kề với định x thì có thể bỏ tất cả các cạnh còn lại kề với x.
Quy tắc 4: Duy trì tính liên thông và bảo đảm bậc mỗi đỉnh luôn lớn hơn hay bằng 2.

Quy tắc 3 được minh họa trong hình,khi thực hiện quy tắc này thì bậc của một số đỉnh bị giảm xuống: nhờ vậy chúng ta có thể tận dụng trở lại quy tắc 1 và quy tắc 4.

Hii,đọc lý thuyết xong muốn nghỉ luôn,hehe.Từ đóng lý thuyết đó chúng ta phải rút ra 2 cái như sau để code nè.Cái đầu tiên là khi nào thì đồ thị cho có chu trình hay đường đi,cái thứ 2 là tìm nó như thế nào?

Từ đó ta có ngay các phương thức sau trong lớp Graph

Dưới đây là code của bài tập này,các bạn xem tham khảo nhé!

Ở phần directedGraph các bạn làm tương tự nhé,chúc các bạn hoàn thành tốt bài tập này nhé!

Giấy phép Creative Commons Giấy phép Creative Commons Attribution-ShareAlike 4.0 Quốc tế .

Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :