Bài giảng Toán rời rạc 2 - Chương 3: Đồ thị Euler và Hamilton
CHꢀꢁNG 3. ĐỒ THỊ EULER VÀ HAMILTON
3.1 Chu trình vƠ đꢂờng đi Euler
1) Đ̣nh ngh̃a: Cho đồ thị G= (V, E).
- Chu tr̀nh đơn ch́a t́t c̉ ćc c̣nh c̉a G đực g̣i l̀ chu tr̀nh Euler G l̀ đồ
thị Euler.
- Đừng đi Euler trong G l̀ đừng đi đơn ch́a ṃi c̣nh c̉a G G l̀ đồ thị
nửa Euler.
1
2) Điều kiện:
- Đồ thị liên thông vô hướng G l̀ đồ thị Euler ṃi đỉnh v V có bꢀc chẵn.
- Đồ thị liên thông vô hướng G l̀ đồ thị nửa Euler số đỉnh v V có bꢀc lẻ
không vựt qú 2.
- Đồ thị có hướng, liên thông yếu G l̀ đồ thị Euler ṃi đỉnh v V có bꢀc-
v̀o v̀ bꢀc-ra b̀ng nhau.
- Đồ thị có hướng, liên thông yếu G l̀ đồ thị nửa Euler số đỉnh v V có bꢀc-
v̀o v̀ bꢀc-ra chênh lệch
nhau 1 đon vị không vựt qú 2.
2
3) Ví dụ:
Đồ thị có đừng đi Euler:
Đồ thị có chu tr̀nh Euler:
a-b-a-c-d-e-b
a-f-c-d-e-c-b-a
3
4) Thụt tón tìm chu trình/ đừng đi Euler
Input: Cho đồ thị G = (V,E) gồm n đỉnh biểu diễn bởi ma trꢀn kề.
Output: H̃y t̀m chu tr̀nh/đừng đi Euler c̉a đồ thị G nếu có.
4
(1) Kiểm tra G có thỏa m̃n điều kiện hay không? Nếu G không thỏa
m̃n điều kiện th̀ kt= 0, nếu có chu tr̀nh Euler th̀ kt= 1; nếu có
đừng đi Euler th̀ kt= 2.
(2) Nếu kt= 0 thông b́o đồ thị không có chu tr̀nh/đừng đi Euler
v̀ d̀ng;
Nếu kt= 1 cḥn u l̀ đỉnh cho trước v̀ chuyển sang (3);
Nếu kt= 2 u l̀ đỉnh có hiệu b́n bꢀc ra v̀ b́n bꢀc v̀o b̀ng 1
(đỉnh bꢀc lẻ) ; chuyển sang 3 ;
5
(3) Xây ḍng chu tr̀nh/đừng đi Euler trong G:
(3.1) Ṭo m̉ng CE để ghi chu tr̀nh Euler v̀ Stack để
xếp ćc đỉnh s̃ x́t. Xếp đỉnh u v̀o Stack;
(3.2) X́t đỉnh v ǹm trên c̀ng c̉a Stack v̀ tḥc hiện:
- Nếu v l̀ đỉnh cô lꢀp th̀ ĺy v ra khỏi Stack v̀ đưa v̀o
CE.
- Nếu v có đỉnh kề l̀ x th̀ đưa x v̀o Stack sau đó xóa
c̣nh nối v với x;
6
(3.3) Quay ḷi (3.2) cho tới khi stack r̃ng;
(4) Xút chu tr̀nh/đừng đi Euler ch́a trong CE theo th́
ṭ ngực ḷi.
7
CƠi đặt chꢂꢃng trình tìm chu trình Euler với G vô hꢂớng:
int lt(int a[][], int n)
{int x;
int bc(int a[][], int n)
{int i, j, deg;
x = tplt();
for(i= 1; i<= n; i++)
{deg=0;
if (x > 1) return 0;
else return 1;
}
for(j= 1; j<= n; j++)
deg+=a[i][j];
if (deg % 2 > 0) return (0);
}
return (1); }
8
void ceu(int a[][], int n)
{int st[100*100], i, j, k, h, t;
t= 1; st[t]= 1; k= 0;
while (t> 0)
void main()
{clrscr();
if ( lt(a, n)== 0 || bc(a, n) == 0)
cout << “KHONG XET\n”;
else ceu(a, n);
{h= st[t]; j= 0;
for (i= 1; i<= n; i++)
if (a[h][i] ==1)
getch() ; }
{t++; st[t]= i; j= i;
a[h][i]= 0; a[i][h]= 0; break}
if (j== 0)
{k++, ce[k]= h; t--;}
}
for (i= 1; i<= k; i++)
cout << ce[i] << “ “;
}
9
BÀI TꢁP
1. Cho đơn đồ thị vô hướng G =
<V, E> gồm 10 đỉnh được biểu
diễn dưới dạng ma trận kề hình
bên.
1 2 3 4 5 6 8 9
1 0 1 0 0 1 0 0 1 0 1
2 1 0 1 1 0 1 0 0 0 0
3 0 1 0 1 0 0 0 0 0 0
4 0 1 1 0 0 1 0 0 0 0
5 1 0 0 0 0 1 1 1 1 1
6 0 1 0 1 1 0 1 0 0 0
7 0 0 0 0 1 1 0 1 1 0
8 1 0 0 0 1 0 1 0 0 0
9 0 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 0 0 0 0 0
Hãy thực hiện:
a) Chứng minh đồ thị G đã cho là
đồ thị nửa Euler?
b) Tìm đường đi Euler của G?
10
2. Cho đơn đồ thị có hướng G = <V,
E> gồm 10 đỉnh được biểu diễn
dưới dạng ma trận kề như hình bên.
1 2 3 4 5 6 7 8 9 0
1 0 1 1 0 0 0 0 0 0 0
2 0 0 1 1 1 0 0 0 0 0
3 0 0 0 0 0 0 0 0 1 1
4 0 0 0 0 0 1 1 0 0 0
5 0 0 0 0 0 1 0 0 0 0
6 0 0 0 0 0 0 1 1 0 0
7 0 0 0 1 0 0 0 1 0 0
8 1 1 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 1
0 1 1 0 0 0 0 0 0 0 0
Hãy thực hiện:
a) Chứng minh đồ thị G đã cho là đồ
thị Euler?
b) Tìm một chu trình Euler của G
bắt đầu từ đỉnh 1?
11
3.2 Chu trình vƠ đꢂờng đi Hamilton
1) Đ̣nh ngh̃a: Cho đồ thị G = (V, E).
- Chu tr̀nh đơn đi qua t́t c̉ ćc đỉnh c̉a G, m̃i đỉnh 1 lần g̣i l̀ chu tr̀nh Hamilton G l̀ đồ
thị Hamilton.
- Đừng đi Hamilton trong G l̀ đừng đi đi qua t́t c̉ các đỉnh c̉a G, m̃i đỉnh 1 lần G là
đồ thị nửa Hamilton.
12
2) Ví dụ:
Đồ thị có chu trình Hamilton:
Đồ thị có đừng đi Hamilton:
a-b-e-d-c-a
d-e-c-b-a-f
13
3) Liệt kê t́t c̉ chu trình Hamilton trong đ̀ tḥ vô hꢂớng
Input: G = (V, E), V = {v1, v2, ..., vn}.
Output: D̃y đỉnh x0, x1, ..., xn với xn= x0.
14
Gỉi thụt đệ qui quay lui :
Khởi tạo: m̉ng vs[i] = 0 để đ́nh d́u nh̃ng đỉnh đ̃ x́t. Cḥn u
V b́t k̀ l̀m đỉnh xút ph́t v̀ đ̣t x0 = u; k= 0;
Lặp quay lui:
- Trong ćc đỉnh vi kề xk-1 có vs[vi] = 0, cḥn đỉnh vh có chỉ số nhỏ
nh́t v̀ đ̣t xk = vh; vs[vh] = 1;
- Ṭi bước k ǹo đó không cḥn đực đỉnh kề quay ḷi bước k-
1, bỏ đ́nh d́u đỉnh đ̃ cḥn ṭi bước k-1 v̀ cḥn đỉnh kh́c tiếp
theo nếu có thể, nếu cḥn đực th̀ chuyển sang bước k+1,
nếu không cḥn đực th̀ quay về bước k-1,...
- Nếu k= n v̀ cḥn đực xn nếu xn= x0 th̀ xút một chu tr̀nh
Hamilton t̀m đực.
15
15 trang
22740
Free
Bạn đang xem tài liệu "Bài giảng Toán rời rạc 2 - Chương 3: Đồ thị Euler và Hamilton", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_2_chuong_3_do_thi_euler_va_hamilton.pdf
