Tài liệu HSG Pascal Phần 2

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á