Thực hành Lý thuyết đồ thị Chu trình, Đường đi Euler, Haminton

Thực hành Lý thuyết đồ thị Chu trình, Đường đi Euler, Haminton

Chu trình, Đường đi Hamilton
I.

Chu trình Hamilton, Đường đi Hamilton, Đồ thị Hamilton

1. Các khái niệm:
 Chu trình Hamilton là chu trình xuất phát từ 1 đỉnh đi thăm tất cả những đỉnh còn lại
mỗi đỉnh đúng 1 lần, cuối cùng quay trở 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 1 lần.
2. Ví dụ 1:
b

a

c

e

d

 Chu trình Hamilton: baedcb
 Đường đi Hamilton (nhưng không phải là chu trình Hamilton): baecd
3. Ví dụ 2:
Xét 3 đơn đồ thị G1, G2, G3 sau:
a

b

e

e

c

d

f

G1

GVHD: Lương Trần Hy Hiến

G2

m

G3

Trang 1

Thực hành Lý thuyết đồ thị Chu trình, Đường đi Euler, Haminton
 G1 có chu trình Hamilton (a, b, c, d, e, a).
 G2 không có chu trình Hamilton vì deg(a) = 1 nhưng có đường đi Hamilton (a,
b, c, d).
 G3 không có cả chu trình Hamilton lẫn đường đi Hamilton.

II.

Thuật toán

Dưới đây là phần hướng dẫn cài đặt thuật toán liệt kê tất cả các chu trình Hamilton
xuất phát từ đỉnh 0, các chu trình Hamilton khác có thể có được bằng cách hoán vị vòng
quanh. Lưu ý rằng cho tới nay, người ta vẫn chưa tìm ra một phương pháp nào thực sự
hiệu quả hơn phương pháp đệ qui quay lui để tìm dù chỉ một chu trình Hamilton cũng
như đường đi Hamilton trong trường hợp đồ thị tổng quát.
1. Tìm chu trình Hamilton
Thuật toán gọi đệ qui hàm tìm trong đó thực hiện những công việc sau:
 B1: Kiểm tra nếu số lần gọi đệ qui > số đỉnh của đồ thị và tồn tại cạnh nối từ x tới
đỉnh đầu tiên trong đường đi thì kết luận có chu trình Hamilon. Ngược lại làm tiếp
B2
 B2: Duyệt qua tất cả các đỉnh i (chưa xét) kề với đỉnh x
 B3: Lưu lại đỉnh i trong đường đi và đánh dấu i đã xét. Gọi đệ qui tìm tiếp.
 B4: Bỏ đánh dấu i đã xét.
Lưu ý: ban đầu đỉnh 0 được đánh dấu đã xét và được lưu trong đường đi.
2. Tìm đường đi Hamilton
Cũng làm tương tự như tìm chu trình chỉ khác trong điều kiện kiểm tra ở B1. Chỉ cần
kiểm tra số lần gọi đệ qui == số đỉnh của đồ thị là được.

III.

Nội dung thực hành

Cho một tập tin văn bản chứa số đỉnh và ma trận kề biểu diễn đồ thị. Viết chương trình tìm chu
trình Hamilton trong đồ thị đó.
Ví dụ:
Nội dung tập tin văn bản
4
0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0

GVHD: Lương Trần Hy Hiến

Ý nghĩa và yêu cầu
Cho đồ thị gồm 4 đỉnh. Tìm một chu trình Hamilton trong đồ thị đó.
Ví dụ: 0 1 2 3 0 là một chu trình Hamilton trong đồ thị

Trang 2

Thực hành Lý thuyết đồ thị Chu trình, Đường đi Euler, Haminton
Khai báo CTDL cần thiết:
#include
using namespace std;
#define MAX 20
#define FOUND 1 //1: cho biết ý nghĩa của các hằng số này
#define NOT_FOUND 0
struct GRAPH
{
int sodinh;
int a[MAX][MAX];
};

Hàm tìm chu trình Hamilton, kết quả trả về cho biết có tìm được chu trình Hamilton hay không.
int dfsHamilton(int path[], GRAPH g)
{
int start = 0;
int flag = NOT_FOUND; //2: cho biết ý nghĩa của biến flag
int visited[MAX]; //3: cho biết ý nghĩa của mảng visited
for(int i = 0; i < g.sodinh; i++) {
visited[i] = 0;
}
count = 0; //đếm số lượng đỉnh trong chu trình Hamilton đang tìm
path[count] = start;
count++;
visited[start] = 1;
flag = visit(start,visited,count,flag,path,g);
if(flag) return FOUND;
return
NOT_FOUND;
}
Hàm visit cài tương tự thuật toán duyệt theo chiều sâu DFS
int visit(int u, int visited[],int&count,int&flag, int path[],
GRAPH g) {
if(flag == FOUND) return flag;
for(int v = 0; v < g.sodinh; v++)
if(visited[v] == 0 && g.a[u][v] != 0) {//nếu u kề v, v chưa thăm
visited[v] = 1;
path[count] = v;
count++;
if(count == g.sodinh && g.a[v][path[0]] == 1) //4: cho
biết ý nghĩa

flag = FOUND;
visit(v,visited,count,flag,path, g);
}
GVHD: Lương Trần Hy Hiến

Trang 3

Thực hành Lý thuyết đồ thị Chu trình, Đường đi Euler, Haminton
if(flag == NOT_FOUND) {//5: cho biết ý nghĩa của đoạn chtr này
visited[u] = 0;
count--;
}
return flag;
}

Hàm main
void main()
{
GRAPH g;
readGRAPH("dothi.txt", g);
int path[MAX];
if(dfsHamilton(path, g) ==
{
// Tìm cách in ra chu
}
else
cout