Chu trình Euler
Đường đi và chu trình Euler
Bài viết sau được mình sưu tầm từ nhiều nguồn với mục đích để tiện cho việc tra cứu và học tập.
---------------------------------------------------------------------------------------
Nguồn:
2) http://vi.wikipedia.org
3) Blog http://y5k72pk.wordpress.com
---------------------------------------------------------------------------------------
Bài toán thực tế:
Thành phố Konigsberg thuộc Phổ, được chia thành bốn vùng bằng các nhánh sông Pregel. Các vùng này gồm 2 vùng bên bờ sông, đảo Kneiphof và một miền nằm giữa 2 nhánh của sông Pregel. Vào thế kỷ 18 người ta đã xây bảy chiếc cầu nối các vùng này lại với nhau.
.jpg)
Câu hỏi: Hình vẽ trên có được vẽ từ một nét không?
Có, nhưng điểm đầu không trùng điểm cuối
---------------------------------------------------------------------------------------
Nguồn:
2) http://vi.wikipedia.org
3) Blog http://y5k72pk.wordpress.com
---------------------------------------------------------------------------------------
Bài toán thực tế:
Thành phố Konigsberg thuộc Phổ, được chia thành bốn vùng bằng các nhánh sông Pregel. Các vùng này gồm 2 vùng bên bờ sông, đảo Kneiphof và một miền nằm giữa 2 nhánh của sông Pregel. Vào thế kỷ 18 người ta đã xây bảy chiếc cầu nối các vùng này lại với nhau.
.jpg)
Vào chủ nhật, người dân thường đi bộ dọc theo thành phố. Họ tự hỏi không biết có thể xuất phát từ một điểm nào đó trong thành phố, đi qua tất cả các cầu, mỗi cầu không đi qua nhiều hơn một lần, rồi lại trở về điểm xuất phát được không.
Nhà toán học người Thụy Sĩ, Leonard Euler đã giải bài toán này. Lời giải của ông công bố vào năm 1736, có thể là một ứng dụng đầu tiên của lý thuyết đồ thị. Euler đã nghiên cứu bài toán này, mô hình hóa nó là một đa đồ thị, bốn vùng được biểu diễn bằng bốn đỉnh, các cầu là các cạnh.
Bài toán tìm đường đi qua tất cả các cầu, mỗi cầu đi qua không quá một lần có thể được phát biểu lại bằng mô hình như sau: Có tồn tại chu trình đơn trong đa đồ thị chứa tất cả cá cạnh?
Đường đi Euler: Trong lý thuyết đồ thị, một đường đi trong đồ thị G = (V,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 đi đúng một lần.
Chu trình Euler: Là đường đi Euler có đỉnh đầu và đỉnh cuối trùng nhau.
Sau đây là một ví dụ khá dễ hiểu, mình lầy từ nguồn http://vi.wikipedia.org
Câu hỏi: Hình vẽ trên có được vẽ từ một nét không?
Có, nhưng điểm đầu không trùng điểm cuối
=>Đường đi Euler nhưng không là chu trình Euler
Có và điểm đầu trùng với điểm cuối
=> Chu trình Euler
+Đồ thị Euler: là đồ thị chứa chu trình Euler và được gọi là nửa Euler nếu nó chứa đường đi Euler
Thông qua ví dụ trên ta có một vài chú ý về đường đi Euler và chu trình Euler:
1) Chu trình Euler là một đường đi Euler nhưng điều ngược lại thì chưa chắc đúng.
2) Chu trình Euler có thể đi qua một đỉnh 2 lần và có thể không đi qua một số đỉnh nào đó nếu các đỉnh này là các đỉnh cô lập,tức là các đỉnh có bậc là 0.
3) Chu trình Euler chỉ liên quan đến cạnh của đồ thị, vì vậy ta có thể thêm một số bất kỳ các đỉnh có bậc bằng 0 (đỉnh cô lập) vào đồ thị G thì chu trình Euler của G vẫn không thay đổi.
------------------------------------------------------------------------
Định lý Euler về đường đi và chu trình Euler:
1) Một đa đồ thị không có điểm cô lập có chu trình Euler khi và chỉ khi đồ thị đó liên thông và không có đỉnh bậc lẻ.
2) Đồ thị vô hướng liên thông G = (V, E) có đường đi Euler khi và chỉ khi G không có quá 2 đỉnh bậc lẻ. Nếu G có 2 đỉnh bậc lẻ thì đường đi Euler có 2 đầu nằm ở 2 đỉnh bậc lẻ.
-----------------------------------------------------------------------
Các tính chất khác:
1) Một đồ thị vô hướng là đồ thị Euler nếu nó liên thông và phân tích được thành các chu trình 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 có thể phân tích thành các chu trình có hướng với các cung rời rạc nhau.
THUẬT TOÁN TÌM CHU TRÌNH EULER
Bài toán: Cho đồ thị G=(V,E). Hãy tìm chu trình Euler của đồ thị G nếu có.
Thuật toán:
Bước 1: Kiểm tra xem đồ thị có liên thông hay không. Nếu G là liên thông thì chuyển sang bước 2, ngược lại thì thông báo chúng ta chỉ xét đồ thị liên thông và dừng thuật toán. ( Vì có thể thấy rằng nếu đồ thị có 1 thành phần liên thông và các phần còn lại là các điểm cô lập thì vẫn có chu trình Euler, vì chu trình Euler chỉ quan tâm đến việc di chuyển qua các cạnh mà không quan tâm đến việc đi qua các đỉnh).
Bước 2: Kiểm tra xem tất cả các đỉnh trong G có bậc chẵn không. Nếu tất cả các đỉnh có bậc chẵn thì chuyển sang bước tiếp theo. Nếu không thì dừng lại và kết luận rằng đồ thị đã cho không có chu trình Euler.
Bước 3: Xây dựng thuật toán tìm chu trình Euler đơn trong G sao cho tất cả các cạnh của G đều có chu trình đơn đi qua và chỉ đi qua một lần bằng cách sau:
1) Tạo mảng CT để ghi đường đi và một Stack để xếp các đỉnh sẽ xét. Đầu tiên xếp một đỉnh u nào đó của đồ thị vào Stack, thí sụ đỉnh v1.
2)Xét đỉnh v nằm trên cùng của Stack và thực hiện:
+ Nếu v là đỉnh cô lập thì lấy v ra khỏi Stack và đưa vào CT
+ Nếu v liên thông với đỉnh x thì đưa x vào ngăn xếp và xóa cạnh (v,x).
3)Quay lại bước 2: cho tới khi ngăn xếp rỗng thì dừng lại. Kết quả đường đi Euler được chứa trong CE theo thứ tự ngược lại.
Như vậy: Để xác định chu trình Euler của một đồ thị vô hướng, trước hết ta cần kiểm tra xem đồ thị có liên thông hay không, sau đó nếu đồ thị liên thông ta kiểm tra bậc các đỉnh có chẵn không. Nếu những điều kiện này thỏa mãn thì bắt đầu xây dựng chu trình Euler, khi có nhiều đỉnh cùng khả năng lựa chọn thì ưu tiên đỉnh có chỉ số nhỏ hơn.
Quá trình xây dựng chu trình Euler được thực hiện như sau:
Khởi tạo một Stack S chứa các phần tử là các số nguyên. Giả sử thao tác đưa phần tử k vào Stack là S.push(k), lấy phần tử ở đỉnh ra là S.pop(), xem phần tử ở đỉnh Stack là S.viewtop(), hàm S.empty() cho giá trị true nếu Stack rỗng, cho giá trị false nếu Stack không rỗng.
Bước 0: Khởi tạo một Stack S. Ban đầu S rỗng, không có phần tử nào. Khởi tạo một mảng CE để chứa các đỉnh tạo nên chu trình Euler.
Bước 1: Chọn một đỉnh k bất kỳ để đưa vào Stack.
Bước 2: Xem phần tử h ở đỉnh Stack.
+Nếu đỉnh h có đỉnh kề ( tức là trong các phần tử a[h,i], i = 1,2,...,n có phần tử khác 0) thì chọn đỉnh kề có chỉ số nhỏ nhất đưa vào Stack, ví dụ là đỉnh r, đồng thời giảm các giá trị a[h][r] và
a[r][h] xuống một giá trị. Điều này có nghĩa là xóa bớt một cạnh trong số các cạnh nối h và đỉnh r.
+Nếu đỉnh h là cô lập, tức là a[h][i] = 0 với mọi i = 1,2,...,n thì đưa h vào mảng CE.
Bước 3: Nếu Stack rỗng thì kết thúc thuật toán, nếu không thì quay lại bước 2.
Một tài liệu khá hữu ích mô phỏng thuật toán này, bạn có thể xem tại đây
Cài đặt code
#ifndef _cac_thao_tac_voi_stack_h
#define _cac_thao_tac_voi_stack_h
//cac_thao_tac_voi_stack.h
/*:
Khai bao kieu Stack
void Init_Stack(Stack &S); //Khoi tao Stack
bool IsEmpty_Stack(Stack S);//Kiem tra tinh rong cua Stack
void Push_Stack(Stack &S, int v); //Them mot node co gia tri v vao Stack
int Pop_Stack(Stack &S); //Xoa mot node cua Stack
void Print_Sack(const Stack &S);//Duyet toan bo stack va in chung
*/
//Khai bao
typedef struct pStack
{
int Top;
pStack *Next;
}*Stack;
//Khoi tao Stack rong
void Init_Stack(Stack &S)
{
S = NULL;
}
bool IsEmpty_Stack(Stack S)
{
if(S == NULL)
return 1; //Neu Stack rong tra ve 1
return 0; //Nguoc lai tra ve 0
}
void Push_Stack(Stack &S, int v)
{
//Khai bao mot node moi
pStack *p;
p = new pStack; //Cap phat bo nho cho node moi
if(p==NULL)
{
std::cout<<"Memory Empty."; //Neu p rong, thong bao het bo nho
return;
}
p->Top = v;
p->Next = S; //Tao link lien ket tu p den Stack
S = p; //Bay gio p la Stack
}
int Pop_Stack(Stack &S)
{
pStack *p; //p de luu node bi xoa
if(IsEmpty_Stack(S))
{
return 0; //Neu Stack rong thi thoat ra
}
p = S; //p la S
S = p->Next; //S link toi node dang sau no
int v = p->Top; // v luu gia tri cua node bi xoa
delete(p); //Giai phong bo nho cho node bi xoa
return v; //Tra ve gia tri cua node bi xoa
}
void Print_Stack(const Stack &S)
{
pStack *p; //p tro vao node can in ra
p = S ;// p la S
while(!IsEmpty_Stack(p))//Trong khi p khong rong
{
std::cout<<" "<<p->Top;
p = p->Next; // p link toi node ke tiep
}
}
#endif
//Duyet_theo_chieu_sau_su_dung_stack.h
/*:
Chuong trinh nhap du lieu tu file src1.txt
*/
#include<iostream>
#include"cac_thao_tac_voi_stack.h"
#ifndef Duyet_theo_chieu_sau_su_dung_stack_h
#define Duyet_theo_chieu_sau_su_dung_stack_h
using namespace std;
#define TRUE 1
#define FALSE 0
#define MAX 100
int so_TP_lien_thong = 1,n;
int a[MAX][MAX];
bool daxet[MAX];
/*:
n = so dinh cua do thi
a[][] = ma tran lien ke bieu dien do thi
so_TP_lien_thong = dem so thanh phan lien thong cua do thi
daxet[] = danh dau cac dinh da duoc tham
*/
//************************************************************************
//************************************************************************
//Khai bao nguyen mau ham
void Init_Stack(Stack &Q);
bool IsEmpty_Stack(Stack Q);
void Push_Stack(Stack &Q, int v);
int Pop_Stack(Stack &Q);
void Init_daxet();
//************************************************************************
//************************************************************************
void Init_daxet()
{
for(int i =0;i<=n;++i)
daxet[i] = FALSE;
}
void DFS(int v)
{
Stack P;
Init_Stack(P);
daxet[v] = TRUE;
Push_Stack(P,v);
int i;
while(!IsEmpty_Stack(P))
{
v = P->Top;
for(i=1;i<=n;++i)
{
if(a[i][v]!=0 && daxet[i] == FALSE)
{
Push_Stack(P,i);
daxet[i] = TRUE;
v = i;
i =-1;
}
}
Pop_Stack(P);
}
}
bool kiem_tra_lien_thong()
{
for(int i =1;i<=n;++i)
{
if(daxet[i] == FALSE)
return FALSE; //Neu do thi khong lien thong tra ve FALSE
}
return TRUE;
}
#endif
//Chuong trinh sau day tim chu trinh Euler cua do thi vo huong
/*:
Buoc 1: Nhap ma tran ke
Buoc 2: Kiem tra xem do thi co chu trinh Euler khong
dk:do thi lien thong va khong co dinh nao bac le
+Neu co tim ra chu trinh so
+Nguoc lai: Thong bao khong co
*/
#include<iostream>
#include"Duyet_theo_chieu_sau_su_dung_stack.h"
#include<fstream>
#define MAX 100
#define TRUE 1
#define FALSE 0
using namespace std;
ifstream fi("Euler_input.txt");
ofstream fo("Euler_output.txt");
//Khai bao bien toan cuc
//int a[MAX][MAX],n;
/*:
a[][] = Ma tran ke bieu dien do thi
n = do dai hang va cot cua ma tran hay chinh la so dinh cua do thi
*/
//--------------------------------------------------------------------------------
void DFS(int v);
//Nhap ma tran ke
void nhap()
{
int i,j;
//Nhap so dinh cua do thi
fi>>n;
//Nhap ma tran ke bieu dien do thi
for(i =1;i<=n;++i)
for(j=1;j<=n;++j )
{
fi>>a[i][j];
}
}
//Kiem tra xem do thi co dinh nao co bac le khong
bool test_bac()
{
int i,j,t;
for(i =1;i<=n;++i)
{
t = 0;
for(j=1;j<=n;++j)
{
t+=a[i][j];
}
if(t % 2 == 1)return FALSE; //Neu do thi co bac le tra ve FALSE
}
return TRUE; //Neu do thi cho co bac chan tra ve TRUE
}
//Kiem tra xem do thi co chu trinh Euler khong
bool test()
{
//Duyet theo chieu sau
DFS(1);
if(kiem_tra_lien_thong()&& test_bac())
{
return TRUE;
}
else
return FALSE;
}
//Tim chu trinh Euler
void Euler()
{
int i,v,t=0;
Stack p;
Init_Stack(p);
//Day dinh 1 vao Stack
Push_Stack(p,1);
while(!IsEmpty_Stack(p))
{
v = p->Top;
for(i=1;i<=n;++i)
{
if(a[i][v]>0)
{
Push_Stack(p,i);
//Bo bot 1 canh noi giua i va v
--a[i][v];
--a[v][i];
//Duyet lai tu dinh i
i=-1;
v = p->Top; // v = dau cua Stack
}
}
//Loai mot dinh o dau stack
fo<<Pop_Stack(p)<<" ";
}
}
int main()
{
if(!fi.is_open())
{
fo<<endl<<"Can't open the Euler_input file.";
return 0;
}
nhap();
if(test())
{
fo<<endl<<"Chu trinh Euler tim duoc la: "<<endl;
Euler();
}
else
{
fo<<endl<<"Do thi da cho khong co chu trinh Euler";
}
cout<<endl;
//Dong file
fi.close();
fo.close();
return 0;
}
/*Chuong trinh sau tim duong di Euler cua mot do thi vo huong bat ky:
Thoa man:
1) Do thi lien thong
2) Do thi khong co qua 2 dinh bac le
3) Neu do thi co 2 dinh bac le thi duong di Euler se chac chan bat dau
va ket thuc tai 2 dinh do.
*/
//duong_di_euler.cpp
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include"Duyet_theo_chieu_sau_su_dung_stack.h"
#define TRUE 1
#define FALSE 0
#define MAX 100
using namespace std;
ifstream infile("src1.txt");
int v;
//int n,a[MAX][MAX] ;
/*:
n = so dinh
v = dinh bat dau cua duong di Euler
*/
//Nhap ma tran ke bieu dien do thi
void nhap()
{
int i,j;
//Nhap so dinh
infile>>n;
//Nhap ma tran
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
infile>>a[i][j];
for(i=1;i<=n;++i)
{
cout<<endl;
for(j=1;j<=n;++j)
cout<<" "<<a[i][j];
}
}
//Kiem tra xem so dinh bac le cua do thi co nhieu hon 2 hay khong
int test_dinh()
{
v = 1;
int i,j,k, dem = 0;
for(i=1;i<=n;++i)
{
k = 0;
for(j=1;j<=n;++j)
{
k += a[i][j];
}
if(k%2 == 1)
{
v = i;
++dem;
}
}
return dem;
}
//Kiem tra xem do thi co lien thong hay khong
bool test()
{
DFS(1);
if(kiem_tra_lien_thong()== FALSE || test_dinh()>2)
return FALSE;
return TRUE;
}
//Duyet tu dinh u
void Euler_cycle()
{
int i;
Stack Q; // Q = NULL
Init_Stack(Q);
Push_Stack(Q,v); // Take u to Stack Q
while(!IsEmpty_Stack( Q))
{
v = Q->Top; // Get a node of the head of Stack
for(i =1;i<=n;++i)
{
if(a[i][v]>0 )
{
Push_Stack(Q,i);
//Xoa bot 1 canh noi giua i va v
--a[i][v] ;
--a[v][i];
//Bay gio dinh cua Stack la i
v = i;
//Duyet laij tu dau
i = -1;
}
}
cout<<Pop_Stack(Q)<<" ";
}
}
main()
{
if(!infile.is_open())
{
cout<<endl<<"Can't open the file."<<endl;
system("pause");
return 0;
}
nhap();
if(test()== FALSE)
{
cout<<endl<<"Do thi da cho khong co duong di Euler."<<endl;
system("pause");
return 0;
}
cout<<endl<<"Duong di Euler cua do thi da cho la: "<<endl;
Euler_cycle();
cout<<endl;
infile.close();
system("pause");
}
.jpg)
No comments: