Để xem lý thuyết đồ thị với các định nghĩa về đường đi, chu trình, đồ thị liên thông bạn có thể xem ở đây.
>> Thuật toán về duyệt các thành phần liên thông của đồ thị bằng C/C++
Định nghĩa: Chu trình đơn trong đồ thị G đi qua mỗi cạnh của đồ thị đúng một lần được gọi là chu trình Euler. Đường đi đơn trong G đi qua mỗi cạnh của nó đúng một lần được gọi là đường đi Euler. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler. Đồ thị có đường đi Euler được gọi là nửa Euler. Rõ ràng, mọi đồ thị Euler đều là nửa Euler nhưng điều ngược lại không đúng.
Chu trình Euler
Đồ thị G1 là đồ thị Euler vì nó có chu trình Euler a, e, c, d, e, b, a. Đồ thị G3 không có chu trình Euler nhưng chứa đường đi Euler a, c, d, e, b, d, a, b vì thế G3 là nửa Euler. G2 không có chu trình Euler cũng như đường đi Euler.
Định lý. Đồ thị vô hướng liên thông G=(V, E) là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Đồ thị vô hướng liên thông G=(V, E) là đồ thị nửa Euler khi và chỉ khi nó không có quá hai đỉnh bậc lẻ.
*Tạo một mảng CE để ghi đường đi và một stack để xếp các đỉnh ta sẽ xét. Xếp vào đó một đỉnh tuỳ ý u nào đó của đồ thị, nghĩa là đỉnh u sẽ được xét đầu tiên.
*Xét đỉnh trên cùng của ngăn xếp, giả sử đỉnh đó là đỉnh v và thực hiện:
*Quay lại bước 2 cho tới khi ngăn xếp rỗng. Kết quả chu trình Euler được chứa trong CE theo thứ tự ngược lại.
void Euler_Cycle(void){
Stack:=φ; CE:=φ;
Chọn u là đỉnh nào đó của đồ thị;
u=>Stack; /* nạp u vào stack*/
while (Stack≠φ) { /* duyệt cho đến khi stack rỗng*/
x= top(Stack); /* x là phần tử đầu stack */
if (ke(x) ≠ φ) ) {
y = Đỉnh đầu trong danh sách ke(x);
Stack<=y; /* nạp y vào Stack*/
Ke(x) = Ke(x) \{y};
Ke(y) = Ke(y)\{x}; /*loại cạnh (x,y) khỏi đồ thị}*/
}
else {
x<= Stack; /*lấy x ra khỏi stack*/;
CE <=x; /* nạp x vào CE;*/
}
}
| Bước | Giá trị trong Stack | Giá trị trong CE | Cạnh còn lại |
| 1 | f | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 | |
| 2 | f, a | 2, 3, 4, 5, 6, 7, 8, 9, 10 | |
| 3 | f, a, c | 3, 4, 5, 6, 7, 8, 9, 10 | |
| 4 | f,a,c,f | 3, 4, 5, 6, 7, 9, 10 | |
| 5 | f, a, c | f | 3, 4, 5, 6, 7, 9, 10 |
| 6 | f, a, c, b | f | 3, 4, 6, 7, 9, 10 |
| 7 | f, a, c, b, d | f | 3, 4, 7, 9, 10 |
| 8 | f, a, c, b, d,c | f | 3, 4, 7, 10 |
| 9 | f, a, c, b, d | f, c | 3, 4, 7, 10 |
| 10 | f, a, c, b, d, e | f, c | 3, 4, 7 |
| 11 | f, a, c, b, d, e, b | f, c | 3, 4 |
| 12 | f, a, c, b, d, e, b, a | f, c | 3 |
| 13 | f, a, c, b, d, e, b, a, d | f, c | |
| 14 | f, a, c, b, d, e, b, a | f, c, d | |
| 15 | f, a, c, b, d, e, b | f, c, d, a | |
| 16 | f, a, c, b, d, e | f, c, d, a, b | |
| 17 | f, a, c, b, d | f, c, d, a, b, e | |
| 18 | f, a, c, b | f, c, d, a, b, e, d | |
| 19 | f, a, c | f, c, d, a, b, e, d, b | |
| 20 | f, a | f, c, d, a, b, e, d, b, c | |
| 21 | f | f, c, d, a, b, e, d, b,c, a | |
| 22 | f, c, d, a, b, e, d, b, c, a, f |
#include<iostream> #include<conio.h> using namespace std; #define MAX 50 #define TRUE 1 #define FALSE 0 int A[MAX][MAX], n, u=1; void Init(void){ freopen("CTEULER.IN","r", stdin); cin>>n; cout<<" So dinh cua do thi n = "<<n<<endl; // nhap ma tran lien ke. for(int i=1; i<=n;i++){ for(int j=1; j<=n;j++){ cin>>A[i][j]; } } } int Kiemtra(){ int s, d; d=0; for(int i=1; i<=n;i++){ s=0; for(int j=1; j<=n;j++) s+=A[i][j];//đếm các bậc của các đỉnh của đồ thị if(s%2) d++; } if(d>0) return(FALSE); //Nếu có 1 đỉnh bậc lẻ thì đồ thị không có chu trình Euler. return(TRUE); //Nếu tất cả các đỉnh của đồ thị là chắn thì đồ thị có thể có chu trình Euler. } void Tim(){ int v, x, top, dCE; int stack[MAX], CE[MAX]; top=1; stack[top]=u;//thêm đỉnh u vào stack. dCE=0; do { v = stack[top];//lấy đỉnh trên cùng của stack. x=1; while (x<=n && A[v][x]==0) //tìm trong danh sách những đỉnh kề với đỉnh v. x++; if (x>n) { //lấy ra khỏi stack. dCE++; CE[dCE]=v;//lưu đỉnh v vào mảng kết quả duyệt CE. top--; } else { //đỉnh x là đỉnh kề với đỉnh v. top++; stack[top]=x; A[v][x]=0; A[x][v]=0; } } while(top!=0); cout<<" Co chu trinh Euler:"; for(x=dCE; x>0; x--) cout<<(char)(CE[x] + 'a' - 1)<<" "; //in ra kết quả dưới dạng char. } void main(void){ Init(); if(Kiemtra()) Tim(); else printf("\n Khong co chu trinh Euler"); _getch(); }
6
0 1 1 1 1 0
1 0 1 1 0 1
1 1 0 1 1 0
1 1 1 0 0 1
1 0 1 0 0 0
0 1 0 1 0 0
So dinh cua do thi n = 6
Co chu trinh Euler : a b c a d b f d c e a
Một đồ thị không có chu trình Euler nhưng vẫn có thể có đường đi Euler. Khi đó, đồ thị có đúng hai đỉnh bậc lẻ, tức là tổng các số cạnh xuất phát từ một trong hai đỉnh đó là số lẻ. Một đường đi Euler phải xuất phát từ một trong hai đỉnh đó và kết thúc ở đỉnh kia. Như vậy, thuật toán tìm đường đi Euler chỉ khác với thuật toán tìm chu trình Euler ở chỗ ta phải xác định điểm xuất phát của đường đi từ đỉnh bậc lẻ này và kết thúc ở đỉnh bậc lẻ khác.
#include<iostream> #include<conio.h> using namespace std; #define MAX 50 #define TRUE 1 #define FALSE 0 int A[MAX][MAX], n, u; void Init(){ freopen("DDEULER.IN", "r",stdin); cin>>n; cout<<"So dinh do thi:"<<n<<endl; //nhập ma trận kề. for(int i=1; i<=n;i++){ for(int j=1; j<=n;j++){ cin>>A[i][j]; } } } int Kiemtra(){ int s, d; d=0; //biến đếm số đỉnh bật lẻ. for(int i=1; i<=n;i++){ s=0; for(int j=1; j<=n;j++) s+=A[i][j]; if(s%2){ d++; //tăng giá trị biến đếm đỉnh bậc lẻ. u=i; //Ghi nhớ đỉnh bặc lẻ. } } if(d!=2) return(FALSE); //nếu số đỉnh bậc lẻ khác 2 thì không có đường đi Euler. return(TRUE); } void DDEULER(){ int v, x, top, dCE; int stack[MAX], CE[MAX]; top=1; stack[top]=u;// nạp đỉnh bậc lẻ vào trong stack. dCE=0; do { v = stack[top];// lấy đỉnh v ra khỏi stack. //tìm đỉnh x kề với v. x=1; while (x<=n && A[v][x]==0) x++; //nếu đỉnh x không kề với v -> lấy v ra khỏi stack và đưa vào CE. if (x>n) { dCE++; CE[dCE]=v; top--; } //nếu đỉnh x kề với đỉnh v -> đưa x vào stack và xóa cạnh (v,x). else { top++; stack[top]=x; A[v][x]=0; A[x][v]=0; } } while(top!=0); cout<<" Co duong di Euler:"; //In kết quả chứa trong CE theo thứ tự ngược lại. for(x=dCE; x>0; x--) cout<<(char)(CE[x] + 'a' - 1)<<" "; //in ra kết quả dưới dạng char. } void main(void){ Init(); if(Kiemtra()) DDEULER(); else printf("Khong co duong di Euler"); _getch(); }
Để tìm tất cả các đường đi Euler của một đồ thị n đỉnh, m cạnh, ta có thể dùng kỹ thuật đệ qui như sau:
Bước 1.Tạo mảng b có độ dài m + 1 như một ngăn xếp chứa đường đi. Đặt b[0]=1, i=1(xét đỉnh thứ nhất của đường đi);
Bước 2.Lần lượt cho b[i] các giá trị là đỉnh kề với b[i-1] mà cạnh (b[i-1],b[i]) không trùng với những cạnh đã dùng từ b[0] đến b[i-1]. Với mỗi giá trị của b[i], ta kiểm tra:
#include<iostream> #include<conio.h> using namespace std; #define MAX 50 #define TRUE 1 #define FALSE 0 int n;//số đỉnh của đồ thị. int m;//số cạnh của đồ thị. int b[MAX];//mảng b có độ dài m + 1 phần tử. int u;//đỉnh bậc lẻ trong đồ thị int OK;//biến kiểm tra đồ thị có đường đi EULER hay không. int A[MAX][MAX];//ma trận kề của đồ thị. int i; void Init(){ freopen("DDEULER.IN", "r",stdin); cin>>n; cout<<"So dinh do thi:"<<n; // nhập ma trận kề. int s;//biến đếm số bậc của đỉnh i. int d = 0;//biến đếm số đỉnh bậc lẻ. for(int i=1; i<=n;i++){ int s = 0; for(int j=1; j<=n;j++){ cin>>A[i][j]; s+=A[i][j]; } if (s%2) { d++;//tắng giá trị biến đếm đỉnh bậc lẻ. u=i;// ghi nhớ đỉnh bậc lẻ. } m=m+s; } m=m /2; if (d!=2) OK=FALSE;// Nếu số đỉnh bậc lẻ khác 2 thì không có đường đi Euler. else OK=TRUE; } void Result(void){ cout<<"Co duong di Euler:"; for(int i=0; i<=m; i++) cout<<(char)(b[i] + 'a' - 1)<<" "; //in ra kết quả dưới dạng char. cout<<endl; } void DDEULER(int i){ for(int j=1; j<=n;j++){ if (A[b[i-1]][j]==1){ A[b[i-1]][j]=0; A[j][b[i-1]]=0; b[i]=j; if(i==m){ Result(); } else{ DDEULER(i+1); } A[b[i-1]][j]=1; A[j][b[i-1]]=1; } } } void main(void){ Init(); b[0]=u;//Gán b[0] nhận giá trị là đỉnh lẻ của đồ thị. i=1; if(OK) DDEULER(i); else printf("\n Khong co duong di Euler"); getch(); }
Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies
Sau khi phát hiện lỗi ngốn pin có nguồn gốc chính là iOS 5, Apple ngay lập tức cho phát hành phiên bản iOS 5.0.1 beta với hứa hẹn cho phép sửa lỗi pin của hệ điều hành này.
Trong thế giới tương hỗ của các cộng đồng trực tuyến, thông tin về các nhóm hỗ trợ chăm sóc sức khỏe được
Tại sao Đỗ Nhật Nam không thể trở thành những Ngô Bảo Châu tiếp theo. Hay chúng ta phải cay đắng thừa nhận: thiên tài sẽ không xuất hiện ở Việt Nam. Ai cho họ xuất hiện?
Bình luận (0)
Add Comment