Đường đi Euler
Bách khoa toàn thư mở Wikipedia
Trong lý thuyết đồ thị, một đường đi trong đồ thị G=(X,E) được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần. Đường đi Euler có đỉnh cuối cùng trùng với đỉnh xuất phát gọi là chu trình Euler. Khái niệm chu trình Euler xuất phát từ bài toán bảy cây cầu do Euler giải quyết vào khoảng năm 1837. Đường đi Euler có thể tìm thấy trong các bài toán vui vẽ một nét (vẽ một hình nào đó mà không nhấc bút khỏi mặt giấy, không tô lại cạnh nào hai lần).
Carl Hierholzer là người đầu tiên mô tả hoàn chỉnh đồ thị Euler vào năm 1873, bằng cách chứng minh rằng đồ thi Euler là đồ thị liên thông không có đỉnh bậc lẻ.
Mục lục |
[sửa] Định nghĩa về chu trình và đường đi Euler
- Đường đi Euler(tiếng Anh: Eulerian path, Eulerian trail hoặc Euler walk) trong đồ thị vô hướng là đường đi của đồ thị đi qua mỗi cạnh của đồ thị đúng một lần.
- Chu trình Euler(tiếng Anh: Eulerian cycle, Eulerian circuit hoặc Euler tour) trong đồ thị vô hướng) là một chu trình đi qua mỗi cạnh của đồ thị đúng một lần.
- Đồ thị gọi là đồ thị Euler khi nó chứa chu trình Euler và được gọi là nửa Euler khi nó chứa đường đi Euler.
- Đối với các đồ thị có hướng, các thuật ngữ đường đi và chu trình được thay bằng đường đi có hướng và chu trình có hướng.
- Ghi chú: Một đồ thị là Euler thì sẽ là nửa Euler điều ngược lại không đúng.
[sửa] Định lý Euler về chu trình và đường đi Euler
- Đồ thị vô hướng liên thông G=(X, E) có chu trình Euler khi và chỉ khi G không có đỉnh bậc lẻ.
- Đồ thị vô hướng liên thông G=(X, E) có đường đi Euler khi và chỉ khi G có không quá hai đỉnh bậc lẻ. Nếu G có hai đỉnh bậc lẻ thì đường đi Euler có hai đầu đường đi nằm ở hai đỉnh bậc lẻ.
[sửa] Các tính chất khác
- Một đồ thị vô hướng là đồ thị Euler nếu nó liên thông và có thể phân tích thành các chu trình có các cạnh rời nhau.
- Nếu đồ thị vô hướng G là Euler thì đồ thị đường L(G) cũng là Euler.
- Đồ thị có hướng là Euler nếu nó liên thông và mọi đỉnh của nó có bậc vào bằng bậc ra.
- Đồ thị có hướng là Euler nếu nó liên thông và có thể phân tích thành các chu trình có hướng với các cung rời nhau.
[sửa] Giải thuật
Giả sử G=(V,E) là đồ thị vô hướng, liên thông , tất cả các đỉnh đều có bâc chẵn hơn nữa G là hữu hạn. Khi đó, tất cả các đỉnh đều có bậc lớn hơn 1.
[sửa] Giải thuật 1: Xây dựng các chu trình đơn thành phần
- Xây dựng một chu trình đơn. Xuất phát từ đỉnh bất kỳ, chẳng hạn x0, vì bậc x0 lớn hơn 1, nên chọn được cạnh u0 = (xo,x1). Đến lượt x1, vì x1 có bậc lớn hơn 1, nên chọn được cạnh u1 = (x1,x2) khác với u0. Tiếp tục như vậy, vì số đỉnh là hữu hạn nên sau một số hữu hạn bước ta gặp lại x0. Khi đó ta có một chu trình đơn, kí hiệu là C.
- Nếu tất cả các cạnh của G đã nằm trong C thì C là chu trình Euler của G.
- Nếu còn cạnh của G chưa nằm trong C thì loại các cạnh trong C và sau đó loại các đỉnh cô lập khỏi G, gọi phần còn lại của G là G' . Khi đó G' vẫn là liên thông và không có đỉnh bậc lẻ. Thêm nữa, vì G là liên thông nên có ít nhất một đỉnh chung của C với G' .
- Xuất phát từ đỉnh chung của G' và C, xây dựng chu trình đơn C' của G' như trong bước 1, ghép C' vào C và quay về bước 2.
[sửa] Giải thuật 2: Không đi qua cầu
- Một cạnh của đồ thị G được gọi là cầu, nếu khi xóa cạnh đó khỏi đồ thị thì làm tăng số thành phần liên thông của G.
Giải thuật Gọi chu trình cần tìm là C
- Khởi tạo: Chọn một đỉnh bất kỳ cho vào C.
- Nếu G không còn cạnh nào thì dừng.
- Bổ xung: Chọn một cạnh nối đỉnh vừa chọn với một đỉnh kề với nó theo nguyên tắc: chỉ chọn cạnh cầu nếu không còn cạnh nào khác để chọn. Bổ xung cạnh vừa chọn và đỉnh cuối của nó vào C, xóa cạnh ấy khỏi G. Quay về bước 2.
