|
Đường đi Euler   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ưởngThành phố Konigsberg (Nga) 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.  Các định nghĩa về chu trình và đường đi Euler
Định lý Euler về chu trình và đường đi Euler
Các tính chất khác
Ví dụVí dụ 1: Cho các đồ thị vô hướng G1, G2, G3, tìm chu trình Euler 
Ví dụ 2: Cho các đồ thị có hướng H1, H2, H3, tìm chu trình Euler 
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ầuMộ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.
Code mẫu#include <stdio.h>
#include <conio.h>
#define TRUE 1
#define FALSE 0
#define VAIN 99
#define MAX 10
int G[MAX][MAX];
// Ma Tran ke Dinh-Dinh (co Khuyen)
int S[MAX][MAX];
// Ma Tran danh dau Cung da su dung
int Pred[MAX];
// Mang Nua-Bac-Trong cua 1 Dinh
int Succ[MAX];
// Mang Nua-Bac-Ngoai cua 1 Dinh
int path[MAX];
// Mang duong di cua chu trinh
// khai bao ham
void ReadData();
void PrintData();
int Check(int k);
//bien toan cuc
int N, k, l = 0;
void Euler();
void main() {
ReadData();
PrintData();
Euler();
}
void ReadData() {
int i, j;
FILE * f = fopen("EU_in.txt", "rt");
if (f == NULL) {
printf("\nError Loading File!\n");
return;
}
fscanf(f, "%d", & N); // gia tri dau tien cho biet so dinh cua Do Thi G
for (i = 1; i <= N; i++) {
Succ[i] = Pred[i] = 0;
for (j = 1; j <= N; j++) {
S[i][j] = FALSE;
// danh dau Cung khong con su dung nua
fscanf(f, "%d", & G[i][j]); //lan luot doc cac phan tu MT ke
}
}
fclose(f);
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
if (G[i][j] > 0) {
S[i][j] = TRUE;
Succ[i]++;
Pred[j]++;
}
// Tinh Bac moi Dinh
}
void PrintData() {
clrscr();
int i, j;
printf("\nMa Tran Ke G[%d*%d]:\n", N, N);
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++)
printf("%4d", G[i][j]);
printf("\n");
}
}
void Euler() {
FILE * g = fopen("EU_out.txt", "wt");
int i;
for (i = 1; i <= N; i++)
if ((Pred[i] + Succ[i]) % 2) // neu co dinh bac Le
{
printf("\nTon tai Dinh %d Bac Le!", i);
printf("\nKhong co chu trinh Euler\n");
fclose(g);
return;
}
printf("\nDo thi co chu trinh Euler\n");
int k, ok;
// kiem tra va in ra man hinh chu trinh Euler 1 net ve
printf("\nKet qua kiem tra xuat phat tu dinh 1:\n");
for (k = 2; k <= N; k++)
// kiem tra xuat phat tu Dinh 1
{
if ((G[1][k] != 0))
// co Cung noi Dinh 1 voi Dinh k
{
S[1][k] = FALSE;
// danh dau Cung(1,k) da duoc su dung
ok = Check(k);
// xet tiep Dinh k
if (ok == FALSE)
S[1][k] = TRUE; //duong nay khong nen qua Dinh k=>tra danh dau
else // ok==TRUE
{
//printf(" %d",k);//lan luot hien thi nguoc cac Dinh da qua
printf("Tong so dinh cua chu trinh: %d\n", l + 2);
fprintf(g, "%d\n", l + 2);
printf("Cac dinh cua duong di chu trinh:\n");
printf("1 %d ", k);
fprintf(g, "1 %d ", k);
for (int r = l - 1; r >= 0; r--) {
printf("%d ", path[r]);
fprintf(g, "%d ", path[r]);
}
fclose(g);
getch();
return;
}
}
}
// end for
}
int Check(int k) // tiep tuc kiem tra, xuat phat tu Dinh k
{
int i, j, ok;
for (i = 1; i <= N; i++) {
if ((S[k][i] == TRUE) && (G[k][i] != 0)) //co Cung tu k den cac Dinh con lai ?
{
S[k][i] = FALSE; // neu co, danh dau khong su dung lai Cung(k,i) nua
ok = Check(i);
// xet tiep Dinh i den cac Dinh khac
if (ok == FALSE)
S[k][i] = TRUE; //lan nay khong nen qua Dinh i => bo danh dau
else {
//printf(" %d",i);
path[l] = i;
l++;
return TRUE;
}
}
}
for (i = 1; i <= N; i++)
// khi khong con Cung di tu Dinh k nua
for (j = 1; j <= N; j++) // quet duyet do thi G xem da het Cung chua?
if (S[i][j] == TRUE)
// neu con sot Cung tren Ma Tran danh dau S =>
return FALSE; //huong di theo Dinh k nay la sai=>chon Dinh k khac
return TRUE;
// thanh cong, tra ve cac dinh nguoc tren duong di Euler
}
Xem thêm Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Đường đi Euler. Tham khảo |