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<br /> <br /> Chu trình, Đường đi Hamilton<br /> I.<br /> <br /> Chu trình Hamilton, Đường đi Hamilton, Đồ thị Hamilton<br /> <br /> 1. Các khái niệm:<br />  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<br /> mỗi đỉnh đúng 1 lần, cuối cùng quay trở lại đỉnh xuất phát.<br />  Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần.<br /> 2. Ví dụ 1:<br /> b<br /> <br /> a<br /> <br /> c<br /> <br /> e<br /> <br /> d<br /> <br />  Chu trình Hamilton: baedcb<br />  Đường đi Hamilton (nhưng không phải là chu trình Hamilton): baecd<br /> 3. Ví dụ 2:<br /> Xét 3 đơn đồ thị G1, G2, G3 sau:<br /> a<br /> <br /> b<br /> <br /> e<br /> <br /> e<br /> <br /> c<br /> <br /> d<br /> <br /> f<br /> <br /> G1<br /> <br /> GVHD: Lương Trần Hy Hiến<br /> <br /> G2<br /> <br /> m<br /> <br /> G3<br /> <br /> Trang 1<br /> <br /> Thực hành Lý thuyết đồ thị Chu trình, Đường đi Euler, Haminton<br />  G1 có chu trình Hamilton (a, b, c, d, e, a).<br />  G2 không có chu trình Hamilton vì deg(a) = 1 nhưng có đường đi Hamilton (a,<br /> b, c, d).<br />  G3 không có cả chu trình Hamilton lẫn đường đi Hamilton.<br /> <br /> II.<br /> <br /> Thuật toán<br /> <br /> 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<br /> 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<br /> 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ự<br /> hiệu quả hơn phương pháp đệ qui quay lui để tìm dù chỉ một chu trình Hamilton cũng<br /> như đường đi Hamilton trong trường hợp đồ thị tổng quát.<br /> 1. Tìm chu trình Hamilton<br /> Thuật toán gọi đệ qui hàm tìm trong đó thực hiện những công việc sau:<br />  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<br /> đỉ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<br /> B2<br />  B2: Duyệt qua tất cả các đỉnh i (chưa xét) kề với đỉnh x<br />  B3: Lưu lại đỉnh i trong đường đi và đánh dấu i đã xét. Gọi đệ qui tìm tiếp.<br />  B4: Bỏ đánh dấu i đã xét.<br /> Lưu ý: ban đầu đỉnh 0 được đánh dấu đã xét và được lưu trong đường đi.<br /> 2. Tìm đường đi Hamilton<br /> 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<br /> kiểm tra số lần gọi đệ qui == số đỉnh của đồ thị là được.<br /> <br /> III.<br /> <br /> Nội dung thực hành<br /> <br /> 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<br /> trình Hamilton trong đồ thị đó.<br /> Ví dụ:<br /> Nội dung tập tin văn bản<br /> 4<br /> 0<br /> 1<br /> 1<br /> 1<br /> 1<br /> 0<br /> 1<br /> 1<br /> 1<br /> 1<br /> 0<br /> 1<br /> 1<br /> 1<br /> 1<br /> 0<br /> <br /> GVHD: Lương Trần Hy Hiến<br /> <br /> Ý nghĩa và yêu cầu<br /> Cho đồ thị gồm 4 đỉnh. Tìm một chu trình Hamilton trong đồ thị đó.<br /> Ví dụ: 0 1 2 3 0 là một chu trình Hamilton trong đồ thị<br /> <br /> Trang 2<br /> <br /> Thực hành Lý thuyết đồ thị Chu trình, Đường đi Euler, Haminton<br /> Khai báo CTDL cần thiết:<br /> #include <br /> using namespace std;<br /> #define MAX 20<br /> #define FOUND 1 //1: cho biết ý nghĩa của các hằng số này<br /> #define NOT_FOUND 0<br /> struct GRAPH<br /> {<br /> int sodinh;<br /> int a[MAX][MAX];<br /> };<br /> <br /> 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.<br /> int dfsHamilton(int path[], GRAPH g)<br /> {<br /> int start = 0;<br /> int flag = NOT_FOUND; //2: cho biết ý nghĩa của biến flag<br /> int visited[MAX]; //3: cho biết ý nghĩa của mảng visited<br /> for(int i = 0; i < g.sodinh; i++) {<br /> visited[i] = 0;<br /> }<br /> count = 0; //đếm số lượng đỉnh trong chu trình Hamilton đang tìm<br /> path[count] = start;<br /> count++;<br /> visited[start] = 1;<br /> flag = visit(start,visited,count,flag,path,g);<br /> if(flag) return FOUND;<br /> return<br /> NOT_FOUND;<br /> }<br /> Hàm visit cài tương tự thuật toán duyệt theo chiều sâu DFS<br /> int visit(int u, int visited[],int&count,int&flag, int path[],<br /> GRAPH g) {<br /> if(flag == FOUND) return flag;<br /> for(int v = 0; v < g.sodinh; v++)<br /> if(visited[v] == 0 && g.a[u][v] != 0) {//nếu u kề v, v chưa thăm<br /> visited[v] = 1;<br /> path[count] = v;<br /> count++;<br /> if(count == g.sodinh && g.a[v][path[0]] == 1) //4: cho<br /> biết ý nghĩa<br /> <br /> flag = FOUND;<br /> visit(v,visited,count,flag,path, g);<br /> }<br /> GVHD: Lương Trần Hy Hiến<br /> <br /> Trang 3<br /> <br /> Thực hành Lý thuyết đồ thị Chu trình, Đường đi Euler, Haminton<br /> if(flag == NOT_FOUND) {//5: cho biết ý nghĩa của đoạn chtr này<br /> visited[u] = 0;<br /> count--;<br /> }<br /> return flag;<br /> }<br /> <br /> Hàm main<br /> void main()<br /> {<br /> GRAPH g;<br /> readGRAPH("dothi.txt", g);<br /> int path[MAX];<br /> if(dfsHamilton(path, g) ==<br /> {<br /> // Tìm cách in ra chu<br /> }<br /> else<br /> cout