Xét một đồ thị liên thông G. Một đường đi Euler của G là một đường đi đơn giản có đỉnh bắt đầu khác đỉnh kết thúc và qua tất cả các cạnh của G. Khi này G còn được gọi là một đường đi Euler. Một chu trình Euler của G là một chu trình đơn giản đi qua tất cả các cạnh của G. Khi này G còn được gọi là một chu trình Euler. Một đồ thị chứa chu trình Euler được gọi là đồ thị Euler | Lý thuyết đồ thị Chương 2: Đường đi và chu trình Đường đi và chu trình Euler Bài toán “Königsburg Bridges” (Leonhard Euler, 1707-1783) Xác định một chu trình đi qua tất cả 7 cây cầu, mỗi cái đúng 1 lần. Đường đi và chu trình Euler Định nghĩa: Xét 1 đồ thị liên thông G. Một đường đi Euler của G là một đường đi đơn giản có đỉnh bắt đầu khác đỉnh kết thúc và qua tất cả các cạnh của G. Khi này G còn được gọi là một đường đi Euler. Một chu trình Euler của G là một chu trình đơn giản đi qua tất cả các cạnh của G. Khi này G còn được gọi là một chu trình Euler. Một đồ thị chứa chu trình Euler được gọi là đồ thị Euler. Đường đi và chu trình Euler Định lý : (Định lý Euler 1) Cho 1 đồ thị vô hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có chu trình Euler nếu và chỉ nếu mọi đỉnh của G đều có bậc chẵn. A B C D E Chu trình Euler: DEABCEBD Đường đi và chu trình Euler Thuật toán tìm chu trình Euler của đồ thị G(V, E) Kết quả sẽ cho ra C là một chu trình Euler bao gồm thứ tự . | Lý thuyết đồ thị Chương 2: Đường đi và chu trình Đường đi và chu trình Euler Bài toán “Königsburg Bridges” (Leonhard Euler, 1707-1783) Xác định một chu trình đi qua tất cả 7 cây cầu, mỗi cái đúng 1 lần. Đường đi và chu trình Euler Định nghĩa: Xét 1 đồ thị liên thông G. Một đường đi Euler của G là một đường đi đơn giản có đỉnh bắt đầu khác đỉnh kết thúc và qua tất cả các cạnh của G. Khi này G còn được gọi là một đường đi Euler. Một chu trình Euler của G là một chu trình đơn giản đi qua tất cả các cạnh của G. Khi này G còn được gọi là một chu trình Euler. Một đồ thị chứa chu trình Euler được gọi là đồ thị Euler. Đường đi và chu trình Euler Định lý : (Định lý Euler 1) Cho 1 đồ thị vô hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có chu trình Euler nếu và chỉ nếu mọi đỉnh của G đều có bậc chẵn. A B C D E Chu trình Euler: DEABCEBD Đường đi và chu trình Euler Thuật toán tìm chu trình Euler của đồ thị G(V, E) Kết quả sẽ cho ra C là một chu trình Euler bao gồm thứ tự các cạnh của chu trình. Đường đi và chu trình Euler 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 3 6 4 5 2 1 2 3 4 5 6 1 2 3 4 5 6 C = Ø, v = 1 Đường đi và chu trình Euler 0 0 1 0 0 0 0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 2 3 4 5 6 1 2 3 4 5 6 1 3 6 4 5 2 C = 1,2 Đường đi và chu trình Euler 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 2 3 4 5 6 1 2 3 4 5 6 1 3 6 4 5 2 C = 1,2,3 Đường đi và chu trình Euler 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 2 3 4 5 6 1 2 3 4 5 6 1 3 6 4 5 2 C = 1,2,3,1 E Ø Đường đi và chu trình Euler 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 2 3 4 5 6 1 2 3 4 5 6 1 3 6 4 5 2 C = 1,2,4, ,3,1 Đường đi và chu trình Euler 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 2 3 4 5 6 1 2 3 4 5 6 1 3 6 4 5 2 C = 1,2,4,3, ,3,1 Đường đi và chu trình Euler 0 0 0 0 0 0 0 0 0
