PHẦN 2 : ĐỒ THỊ ƠLE, NỬA ƠLE
CHU TRèNH ƠLE - CHU TRèNH HAMINTƠN

I / Định nghĩa :
1 - Trong đồ thị vô hướng : Đường đi qua tất cả cỏc cạnh, mỗi cạnh qua đúng 1 lần , gọi là đường đi Euler. Chu trỡnh đi qua tất cả các cạnh, mỗi cạnh qua đúng 1 lần , gọi là chu trỡnh Euler.
2 - Đồ thị vô hướng có đường đi Euler gọi là đồ thị nửa Euler
Đồ thị vô hướng có chu trỡnh Euler gọi là đồ thị Euler
3 - Định lý Euler : Đồ thị vô hướng,liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh đều có bậc chẵn .
Đồ thị vô hướng , liên thông là đồ thị nửa Ơle khi và chỉ khi nó có không quá 2 đỉnh bậc lẻ .
4 - Trong đồ thị có hướng : Mạch đi qua mọi cung, mỗi cung chỉ 1 lần gọi là mạch Euler
Đồ thị có hướng , nếu tại mỗi đỉnh số cung đi vào bằng số cung đi ra thỡ ta gọi đồ thị này là tựa đối xứng .
Định lý : Đồ thị có hướng,liên thông và tựa đối xứng thỡ cú mạch Euler
5 - Trong đồ thị có hướng : Mạch đi qua tất cả các đỉnh , mỗi đỉnh chỉ 1 lần , gọi là mạch Hamintơn ; nếu mạch này đóng thỡ gọi là mạch đóng Hamintơn . Dây chuyền đơn đi qua tất cả các đỉnh , mỗi đỉnh chỉ 1 lần , gọi là dây chuyền đơn Haminton . đồ thị gọi là nửa Haminton .
6 - Trong đồ thị vô hướng : Đường đi qua tất cả các đỉnh , mỗi đỉnh chỉ 1 lần , gọi là đường đi Hamintơn ; chu trỡnh đi qua tất cả các đỉnh , mỗi đỉnh chỉ 1 lần ( trừ đỉnh đầu trùng đỉnh cuối ) gọi là chu trỡnh Hamintơn ; đồ thị tương ứng cũng gọi là đồ thị nửa Haminton (vô hướng ) hoặc Haminton (vô hướng )
7 - Định lý : (Kơric) Nếu đồ thị đầy đủ ( giữa 2 đỉnh bất kỳ đều có ít nhất 1 cung ) thỡ tồn tại mạch Hamintơn
8 - Định lý : (Dirak) Đơn đồ thị vô hướng G có n đỉnh (n>=3) có bậc của mọi đỉnh đều >= n/2 thỡ đồ thị là Haminton.
Đồ thị có hướng G có n đỉnh (n>=3) liên thông mạnh và có bán bậc vào , bán bậc ra của mọi đỉnh đều >= n/2 thỡ đồ thị là Haminton.
9 - Định lý :
Nếu đỉnh x chỉ có cung đi ra thỡ mọi mạch Hamintơn có đỉnh x là mút đầu tiên
Nếu đỉnh y chỉ có cung đi vào thỡ mọi mạch Hamintơn có đỉnh y là mút cuối cùng
10 - Định lý : Nếu x là đỉnh treo ( chỉ có 1 cung duy nhất dính với nó - đi tới nó hoặc từ nó đi ra - ) thỡ mọi đường đi Hamintơn M đều có mút đầu tiên hoặc cuối cùng là x . Đỉnh kề với x trong đồ thị G cũng là đỉnh kề với x trong mạch Hamintơn M
II / Thuật toỏn Fleury tỡm chu trỡnh Euler ( trong đồ thị vô hướng ):
Bước 1 : Xuất phát từ 1 đỉnh xi tuỳ ý .
Bước 2 : Vũng lặp
+ Chọn 1 cạnh xuất phỏt từ x i tới x k có tính chất : nếu xoá nó khỏi đồ thị thỡ phần đồ thị cũn lại vẫn liờn thụng . ( gọi là tớnh chất A )
+ Xoá cạnh đó chọn .
+ Gỏn x i := x k
+ Bước 2 được lặp cho đến khi không chọn được cạnh có tính chất A nêu trên ; lúc này hoặc là hết cạnh , hoặc cạnh đó là cầu sang vùng liên thông mới . Nếu hết cạnh thỡ kết thỳc cũn khụng thỡ sang bước 3

Bước 3 : Qua cầu , xoá điểm cô lập ( hoặc xử lý gián tiếp : tăng số vùng liên thông ) ,về bước 2.

III / Tỡm đường đi Hamintơn bằng đệ quy:

Giả sử đó tỡm được mạch k đỉnh , cần bổ xung đỉnh thứ k+1 vào chỗ thích hợp của mạch này , ta chọn 1 trong 3 trường hợp sau :
+ Trường hợp 1 : có cung nối xk với xk+1 thỡ cho mạch đi tiếp tới xk+1
+ Trường hợp 2 : có cung nối x k+1 tới x1 thỡ thờm cung (x k+1,x 1) vào đầu mạch
+ Trường hợp 3 : soát từ x k về đầu mạch cho đến khi gặp x m mà cú cung nối xm với xk+1 thỡ chốn vào giữa mạch : cung (xm , xk+1) và cung (xk+1,x m+1) , bỏ cung (xm ,x m+1)
IV / Bài tập cơ bản :
1 ) Cho đồ thị vô hướng
Cõu a ) Tỡm cỏc cầu của đồ thị .
Cõu b ) Hóy kiểm tra xem :
b1 - Có phải là đồ