Đường đi Euler

Ý tưởng

Thành phố Konigsberg (Đức) có 2 vùng bị ngăn cách bởi một dòng sông và có 2 đảo ở giữa sông. Có 7 chiếc cầu nối những vùng này với nhau.
Bài toán: Người dân trong vùng thách đố nhau là thử tìm cách xuất phát từ một vùng đi dạo qua mỗi chiếc cầu đúng một lần và trở về nơi xuất phát.
Năm 1736, nhà toán học Euler (1707 - 1783) đã mô hình bài toán này bằng một đồ thị vô hướng với mỗi đỉnh ứng với một vùng, mỗi cạnh ứng với một chiếc cầu.

Giải thuật tìm chu trình Euler

Giả sử G = (V, E) là đồ thị vô hướng, liên thông, tất cả các đỉnh đều có bậc chẵn hơn nữa G là hữu hạn. Khi đó, tất cả các đỉnh đều có bậc lớn hơn 1.

Giải thuật 2: Không đi qua cầu

Một cạnh của đồ thị G được gọi là cầu, nếu khi xóa cạnh đó khỏi đồ thị thì làm tăng số thành phần liên thông của G.

Code mẫu

1 #include <stdio.h>   2 #include <conio.h>  3 #define TRUE 1  4 #define FALSE 0  5 #define VAIN 99  6 #define MAX 10  7   8 int G[MAX][MAX];  9 // Ma Tran ke Dinh-Dinh (co Khuyen) 10 int S[MAX][MAX]; 11 // Ma Tran danh dau Cung da su dung 12 int Pred[MAX]; 13 // Mang Nua-Bac-Trong cua 1 Dinh 14 int Succ[MAX]; 15 // Mang Nua-Bac-Ngoai cua 1 Dinh 16 int path[MAX]; 17 // Mang duong di cua chu trinh 18  19 // khai bao ham 20 void ReadData(); 21 void PrintData(); 22 int Check(int k); 23 //bien toan cuc 24 int N, k, l = 0; 25 void Euler(); 26  27 void main() { 28     ReadData(); 29     PrintData(); 30     Euler(); 31 } 32  33 void ReadData() { 34     int i, j; 35     FILE * f = fopen("EU_in.txt", "rt"); 36  37     if (f == NULL) { 38         printf("\nError Loading File!\n"); 39         return; 40     } 41     fscanf(f, "%d", & N); // gia tri dau tien cho biet so dinh cua Do Thi G 42     for (i = 1; i <= N; i++) { 43         Succ[i] = Pred[i] = 0; 44         for (j = 1; j <= N; j++) { 45             S[i][j] = FALSE; 46             // danh dau Cung khong con su dung nua 47             fscanf(f, "%d", & G[i][j]); //lan luot doc cac phan tu MT ke 48         } 49     } 50     fclose(f); 51     for (i = 1; i <= N; i++) 52         for (j = 1; j <= N; j++) 53             if (G[i][j] > 0) { 54                 S[i][j] = TRUE; 55                 Succ[i]++; 56                 Pred[j]++; 57             } 58     // Tinh Bac moi Dinh  59 } 60  61 void PrintData() { 62     clrscr(); 63     int i, j; 64     printf("\nMa Tran Ke G[%d*%d]:\n", N, N); 65     for (i = 1; i <= N; i++) { 66         for (j = 1; j <= N; j++) 67             printf("%4d", G[i][j]); 68         printf("\n"); 69     } 70 } 71  72 void Euler() { 73     FILE * g = fopen("EU_out.txt", "wt"); 74     int i; 75     for (i = 1; i <= N; i++) 76         if ((Pred[i] + Succ[i]) % 2) // neu co dinh bac Le 77     { 78         printf("\nTon tai Dinh %d Bac Le!", i); 79         printf("\nKhong co chu trinh Euler\n"); 80         fclose(g); 81         return; 82     } 83     printf("\nDo thi co chu trinh Euler\n"); 84     int k, ok; 85     // kiem tra va in ra man hinh chu trinh Euler 1 net ve 86     printf("\nKet qua kiem tra xuat phat tu dinh 1:\n"); 87     for (k = 2; k <= N; k++) 88     // kiem tra xuat phat tu Dinh 1 89     { 90         if ((G[1][k] != 0)) 91         // co Cung noi Dinh 1 voi Dinh k 92         { 93             S[1][k] = FALSE; 94             // danh dau Cung(1,k) da duoc su dung 95             ok = Check(k); 96             // xet tiep Dinh k 97             if (ok == FALSE) 98                 S[1][k] = TRUE; //duong nay khong nen qua Dinh k=>tra danh dau 99             else // ok==TRUE100             {101                 //printf(" %d",k);//lan luot hien thi nguoc cac Dinh da qua102                 printf("Tong so dinh cua chu trinh: %d\n", l + 2);103                 fprintf(g, "%d\n", l + 2);104                 printf("Cac dinh cua duong di chu trinh:\n");105                 printf("1 %d ", k);106                 fprintf(g, "1 %d ", k);107                 for (int r = l - 1; r >= 0; r--) {108                     printf("%d ", path[r]);109                     fprintf(g, "%d ", path[r]);110                 }111                 fclose(g);112                 getch();113                 return;114             }115         }116     }117     // end for 118 }119 120 int Check(int k) // tiep tuc kiem tra, xuat phat tu Dinh k 121 {122     int i, j, ok;123     for (i = 1; i <= N; i++) {124         if ((S[k][i] == TRUE) && (G[k][i] != 0)) //co Cung tu k den cac Dinh con lai ?125         {126             S[k][i] = FALSE; // neu co, danh dau khong su dung lai Cung(k,i) nua127             ok = Check(i);128             // xet tiep Dinh i den cac Dinh khac129             if (ok == FALSE)130                 S[k][i] = TRUE; //lan nay khong nen qua Dinh i => bo danh dau131             else {132                 //printf(" %d",i);133                 path[l] = i;134                 l++;135                 return TRUE;136             }137         }138     }139     for (i = 1; i <= N; i++)140         // khi khong con Cung di tu Dinh k nua141         for (j = 1; j <= N; j++) // quet duyet do thi G xem da het Cung chua?142             if (S[i][j] == TRUE)143                 // neu con sot Cung tren Ma Tran danh dau S =>144                 return FALSE; //huong di theo Dinh k nay la sai=>chon Dinh k khac145     return TRUE;146     // thanh cong, tra ve cac dinh nguoc tren duong di Euler147 }