Đường đi Euler
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. 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ừ ...
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. 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 1737. 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).
Hỏi: Các hình này có vẽ được một nét không?
Trả lời: Được! Nhưng điểm cuối không trùng điểm xuất phát
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ẻ.
- (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.
Đồ thị Bảy cây cầu Königsberg có 4 đỉnh bậc lẻ nên không là đồ thị 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ẻ.
- 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.
Bỏ cây cầu nối B với D, xây cây cầu nối A với C, đồ thị không có đỉnh bậc lẻ nên là đồ thị Euler
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.
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ổ sung: 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ổ sung 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.
