Đường đi Euler

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm
Hỏi: Các hình này có vẽ được một nét không?
Trả lời: Được! Nhưng điểm cuối không trùng điểm xuất phát
Trả lời: Được! Và điểm cuối trùng điểm xuất phát

Trong lý thuyết đồ thị, một đường đi trong đồ thị G = (X, E) được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần. Đường đi Euler có đỉnh cuối cùng trùng với đỉnh xuất phát gọi là chu trình Euler. Khái niệm chu trình Euler xuất phát từ bài toán bảy cây cầu do Euler giải quyết vào khoảng năm 1737. Đường đi Euler có thể tìm thấy trong các bài toán vui vẽ một nét (vẽ một hình nào đó mà không nhấc bút khỏi mặt giấy, không tô lại cạnh nào hai lần).

Carl Hierholzer là người đầu tiên mô tả hoàn chỉnh đồ thị Euler vào năm 1873, bằng cách chứng minh rằng đồ thi Euler là đồ thị liên thông không có đỉnh bậc lẻ.

Ý tưởng[sửa | sửa mã nguồn]

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.

Hình ảnh 7 chiếc cầu nối 4 vùng trong thành phố Konigsberg (Đức)

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.

Đồ thị vô hướng được mô hình hóa từ bài toán 7 chiếc cầu

Các định nghĩa về chu trình và đường đi Euler[sửa | sửa mã nguồn]

  1. Đường đi Euler (tiếng Anh: Eulerian path, Eulerian trail hoặc Euler walk) trong đồ thị vô hướng là đường đi của đồ thị đi qua mỗi cạnh của đồ thị đúng một lần (nếu là đồ thị có hướng thì đường đi phải tôn trọng hướng của cạnh).
  2. Chu trình Euler (tiếng Anh: Eulerian cycle, Eulerian circuit hoặc Euler tour) trong đồ thị vô hướng là một chu trình đi qua mỗi cạnh của đồ thị đúng một lần và có đỉnh đầu trùng với đỉnh cuối.
  3. Dây chuyền Euler là dây chuyền đi qua tất cả các cạnh trong đồ thị và mỗi cạnh được đi qua đúng một lần.
  4. Mạch EulerĐường đi Euler có đỉnh đầu trùng với đỉnh cuối.
  5. Đồ thị Euler
    1. Đồ thị Euler vô hướng là đồ thị vô hướng có chứa ít nhất một chu trình Euler.
    2. Đồ thị Euler có hướng là đồ thị có hướng có chứa ít nhất một mạch Euler.
  6. Đồ thị được gọi là đồ thị Euler nếu có chu trình (mạch) Euler, và gọi là đồ thị nửa Euler nếu nó có dây chuyền (đường đi) Euler.
    • Ghi chú: Một đồ thị là Euler thì sẽ là nửa Euler; điều ngược lại không đúng.

Định lý Euler về chu trình và đường đi Euler[sửa | sửa mã nguồn]

Đồ thị Bảy cây cầu Königsberg có 4 đỉnh bậc lẻ nên không là đồ thị Euler
  1. Đồ thị vô hướng liên thông G = (X, E) có chu trình Euler khi và chỉ khi G không có đỉnh bậc lẻ.
    • Chứng minh:
      • Điều kiện cần: Giả sử (G) là đồ thị Euler, tức là tồn tại chu trình Euler (P) trong (G). Khi đó, cứ mỗi lần chu trình (P) đi qua một đỉnh nào đó của (G) thì bậc của đỉnh đó tăng lên 2.
      • Mặt khác, mỗi cạnh của đồ thị xuất hiện trong (P) đúng 1 lần. Do đó, mỗi đỉnh của đồ thị đều có bậc chẵn.
    • Phát biểu khác: Một đa đồ thị không có điểm cô lập có chu trình Euler nếu và chỉ nếu đồ thị là liên thông và mỗi đỉnh của nó đều có bậc chẵn.
  2. Đồ thị vô hướng liên thông G = (X, E) có đường đi Euler khi và chỉ khi G có đúng hai đỉnh bậc lẻ. Nếu G có hai đỉnh bậc lẻ thì đường đi Euler có hai đầu đường đi nằm ở hai đỉnh bậc lẻ.
  3. Đồ thị có hướng liên thông G = (X, E) có chu trình Euler, khi đó số đỉnh bậc trong của G sẽ bằng số đỉnh bậc ngoài của G (d+(x) = d-(x),∀xϵ X).

Các tính chất khác[sửa | sửa mã nguồn]

  1. Một đồ thị vô hướng là đồ thị Euler nếu nó liên thông và có thể phân tích thành các chu trình có các cạnh rời nhau.
  2. Nếu đồ thị vô hướng G là Euler thì đồ thị đường L(G) cũng là Euler.
  3. Đồ thị có hướng là Euler nếu nó liên thông và mọi đỉnh của nó có bậc vào bằng bậc ra.
  4. Đồ thị có hướng là Euler nếu nó liên thông và có thể phân tích thành các chu trình có hướng với các cung rời nhau.

Ví dụ[sửa | sửa mã nguồn]

Ví dụ 1: Cho các đồ thị vô hướng G1, G2, G3, tìm chu trình Euler

Hình 4: Đồ thị Euler - Đồ thị nửa Euler (vô hướng)
  • Đồ thị G1 là đồ thị Euler vì nó có chu trình Euler a, e, c, d, e, b, a.
  • Đồ thị G2 không có chu trình cũng như đường đi Euler.
  • Đồ thị G3 không có chu trình Euler nhưng nó có đường đi Euler a, c, d, e, b, d, a, b, vì thế G3 là đồ thị nửa Euler.

Ví dụ 2: Cho các đồ thị có hướng H1, H2, H3, tìm chu trình Euler

Hình 5: Đồ thị Euler - Đồ thị nửa Euler (có hướng)
  • Đồ thị H2 là đồ thị Euler vì nó có chu trình Euler a, b, c, d, e, a.
  • Đồ thị H3 không có chu trình Euler nhưng nó có đường đi Euler c, a, b, c, d, b vì thế H3 là đồ thị nửa Euler.
  • Đồ thị H1 không có chu trình cũng như đường đi Euler.

Giải thuật tìm chu trình Euler[sửa | sửa mã nguồn]

Bỏ cây cầu nối B với D, xây cây cầu nối A với C, đồ thị không có đỉnh bậc lẻ nên là đồ thị 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[sửa | sửa mã nguồn]

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.

Giải thuật: Gọi chu trình cần tìm là C.[sửa | sửa mã nguồn]

  1. Khởi tạo: Chọn một đỉnh bất kỳ cho vào C.
  2. Nếu G không còn cạnh nào thì dừng.
  3. Bổ sung: Chọn một cạnh nối đỉnh vừa chọn với một đỉnh kề với nó theo nguyên tắc: chỉ chọn cạnh cầu nếu không còn cạnh nào khác để chọn. Bổ sung cạnh vừa chọn và đỉnh cuối của nó vào C, xóa cạnh ấy khỏi G. Quay về bước 2.

Code mẫu[sửa | sửa mã nguồn]

  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==TRUE
100             {
101                 //printf(" %d",k);//lan luot hien thi nguoc cac Dinh da qua
102                 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) nua
127             ok = Check(i);
128             // xet tiep Dinh i den cac Dinh khac
129             if (ok == FALSE)
130                 S[k][i] = TRUE; //lan nay khong nen qua Dinh i => bo danh dau
131             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 nua
141         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 khac
145     return TRUE;
146     // thanh cong, tra ve cac dinh nguoc tren duong di Euler
147 }

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]