Chương 2: Đường đi và chu trình

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úcvà 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. Khinà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....
Nội dung trích xuất từ tài liệu:
Chương 2: Đường đi và chu trìnhLýthuyếtđồthịChương2:Đườngđivàchutrình 1ĐườngđivàchutrìnhEuler 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. 2ĐườngđivàchutrìnhEuler Đị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. 3ĐườngđivàchutrìnhEuler Định lý 2.1: (Đị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 E B Chu trình Euler: DEABCEBD C D 4ĐườngđivàchutrìnhEuler 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. 56ĐườngđivàchutrìnhEuler 123456 1 1 011000 3 22 1 0 1 1 1 0 3 1 1 0 1 0 1 4 0 1 1 0 0 0 4 5 0 1 0 0 0 15 6 6 0 0 1 0 1 0 C = Ø, v = 1 7ĐườngđivàchutrìnhEuler 123456 1 1 001000 2 0 0 1 1 1 0 3 2 3 1 1 0 1 0 1 4 0 1 1 0 0 0 4 5 0 1 0 0 0 1 5 6 6 0 0 1 0 1 0 C = 1,2 8ĐườngđivàchutrìnhEuler 123456 1 1 001000 2 0 0 0 1 1 0 3 2 3 1 0 0 1 0 1 4 0 1 1 0 0 0 4 5 0 1 0 0 0 1 5 6 6 0 0 1 0 1 0C = 1,2,3 9ĐườngđivàchutrìnhEuler 123456 1 1 000000 2 0 0 0 1 1 0 3 2 3 0 0 0 1 0 1 4 0 1 1 0 0 0 4 5 0 1 0 0 0 1 5 6 6 0 0 1 0 1 0 E≠ ØC = 1,2,3,1 10ĐườngđivàchutrìnhEuler 123456 1 1 000000 2 0 0 0 0 1 0 3 2 3 0 0 0 1 0 1 4 0 0 1 0 0 0 4 5 0 1 0 0 0 1 5 6 6 0 0 1 0 1 0C = 1,2,4, ,3,1 11ĐườngđivàchutrìnhEuler 123456 1 1 000000 2 0 0 0 0 1 0 3 2 3 0 0 0 0 0 1 4 0 0 0 0 0 0 4 5 0 1 0 0 0 1 5 6 6 0 0 1 0 1 0C = 1,2,4,3, ,3,1 12ĐườngđivàchutrìnhEuler 123456 1 1 000000 2 0 0 0 0 1 0 3 2 3 0 0 0 0 0 0 4 0 0 0 0 0 0 4 5 0 1 0 0 0 1 5 6 6 0 0 0 0 1 0C = 1,2,4,3,6, ,3,1 13ĐườngđivàchutrìnhEuler 123456 1 1 000000 2 0 0 0 0 1 0 3 2 3 0 0 0 0 0 0 4 0 0 0 0 0 0 4 5 0 1 0 0 0 0 5 6 6 0 0 0 0 0 0C = 1,2,4,3,6,5, ,3,1 14ĐườngđivàchutrìnhEuler 123456 1 1 000000 2 0 0 0 0 0 0 3 2 3 0 0 0 0 0 0 4 0 0 0 0 0 0 4 5 0 0 0 0 0 0 5 6 6 0 0 0 0 0 0C = 1,2,4,3,6,5,2,3,1 E=Ø 15ĐườngđivàchutrìnhEuler Định lý 2.2 (Định lý Euler 2): Cho một đồ thi vô hướng G liên thông và c ...