Bài 10: Đồ thị Euler

Tham khảo Video sau đây :

1.Định nghĩa

• Chu trình đơn chứa tất cả các cạnh của đồ thị G được gọi là chu trình Euler

• Đường đi Euler trong G là đường đi đơn chứa mọi cạnh của G

💡 GHI NHỚ

• Đồ thị có chu trình Euler được gọi là đồ thị Euler

• Đồ thị có đường đi Euler được gọi là đồ thị nửa Euler

==> Một đa đồ thị liên thông có chu trình liên thông khi và chỉ khi mỗi đỉnh của nó đều có bậc chẵn

💡 HỆ QUẢ

Đồ thị vô hướng liên thông G là nửa Euler <=> nó có không quá 2 đỉnh bậc lẻ

2.Thuật toán

BƯỚC KHỞI TẠO

• Tìm chu trình C bất kỳ trong G

• Loại khỏi G các cạnh trong chu trình C

BƯỚC LẶP

Trong khi G khác rỗng thực hiện các bước sau:

• Bước 1: Tìm chu trình C' trong G có đỉnh bắt đầu thuộc C`

• Bước 2: Loại bỏ khỏi G các đỉnh cô lập và các cạnh của C'

• Bước 3: Chèn vào C chu trình C' ở vị trí thích hợp

Kết thúc thuật toán, ta có C là chu trình Euler cần tìm

3.Định lý

Đa đồ thị liên thông có đường đi Euler nhưng không có chu trình Euler <=> nó có đúng 2 đỉnh bậc lẻ

Thuật toán Fleury tìm chu trình Euler:

Bước 1: Chọn 1 đỉnh u tuỳ ý để bắt đầu

Bước 2: Chọn một cạnh để đi tiếp, chỉ chọn cạnh cầu khi nào không có sự lựa chọn khác

Bước 3: Đánh dấu cạnh đã đi qua cho biết ta không thể quay lại cạnh đó

Bước 4: Đi theo cạnh đó đến đỉnh tiếp theo

Bước 5: Lặp lại bước 2 cho đến khi nào mọi cạnh đêu2 đã được duyệt

4.Bài tập