Bài giảng Lý thuyết đồ thị: Chương 2 - ThS. Trần Quốc Việt

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:41

Thêm vào BST

Báo xấu

8
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết đồ thị: Chương 2 Đồ thị euler và đồ thị hamilton, cung cấp cho người đọc những kiến thức như: Đường đi và chu trình euler; đường đi và chu trình hamilton. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 2 - ThS. Trần Quốc Việt

Bài giảng LÝ THUYẾT ĐỒ THỊ (GRAPH THEORY) 1
Chương 2: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON ĐƯỜNG ĐI VÀ CHU TRÌNH EULER ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON 2
Nhà toán học Thụy sĩ 3
Ví dụ :Bài toán về các cây cầu ở Konigsberg (Nga) - 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. 4
Ví dụ :Bài toán về các cây cầu ở Konigsberg (tt)  Gọi 1, 2, 3 và 4 là 4 vùng đất bị ngăn cách bởi các nhánh sông  Biểu diễn mỗi vùng đất bởi một đỉnh của đồ thị  Một cạnh: một cây cầu nối giữa 2 vùng đất  1   3 4  2
Ví dụ :Bài toán về các cây cầu ở Konigsberg (tt)  Bài toán trở thành: Tìm một chu trình đơn đi qua tất cả các cạnh của đồ thị  Chu trình Euler? 1    3 4  2
Đường đi Euler và chu trình Euler  Cho G là một đồ thị liên thông, một chu trình Euler (Eulerian circuit) của G là một chu trình đi đơn đi qua tất cả các cạnh (cung) của G Ví dụ 1 5 1,2,5,3,4,5,1: là một chu trình 2 4 Euler: 3 7
Đường đi Euler và chu trình Euler  Cho G là một đồ thị liên thông, một đường đi Euler (Eulerian path) của G là đường đi đơn đi qua tất cả các cạnh (cung) của G Ví dụ 1 5 2,1,5,2,3,4,5: là một đường đi Euler 2 4 3 8
Định lý Euler 1  Định lý Euler 1: Đồ thị vô hướng G=(V,E) liên thông và |V|>1, G có chu trình Euler  mọi đỉnh của G đều có bậc chẵn Ví dụ: Đồ thị nào sau đây có chu trình Euler, không có chu trình Uuler 3 4 b c a b 3 e d e c 2 5 a d 1 f g G1 G2 G3
Định lý Euler 1 h a 0 1 0 1 0 1 0 2 1 0 b g   A  0 2 0 1 1   e f c 1 1 1 0 1 0  0 1 1 0  d G4 G5 (cho bởi ma trận kề)
Định lý Euler 2 Đồ thị vô hướng liên thông G=(V,E) và có |V|>1, G có đường đi Euler và không có chu trình Euler  G có đúng 2 đỉnh bậc lẻ Ví dụ: Đồ thi nào sau đây có chu trình Euler, đồ thi nào có đường đi Euler nhưng không có chu trình Euler, đồ thị nào không có chu trình Euler và cũng không có đường đi Euler 2 3 h 1 1 6 3 4 a 6 2 b g 3 3 e c 2 f 5 4 1 5 4 d 5 11 G1 G2 G3 G4
Định lý Euler 3  Định lý Euler 3: Đồ thị có hướng G=(V,E) liên thông yếu và |V|>1. G có chu trình Euler  mọi đỉnh trong G đều có nữa bậc trong bằng nữa bậc ngoài (hay G cân bằng) 1 2 1 3 4 3 2 4 G1: G2: cân bằng nên Có chu trình Euler Không cân bằng nên 12 Không Có chu trình Euler
Định lý Euler 4  Định lý Euler 4: Cho G=(V,E) có hướng, không có đỉnh cô lập. Và |V|>1. G có đường đi Euler nhưng không có chu trình Euler  G liên thông yếu và có đúng 2 đỉnh x,y thoả: deg+(x)=deg-(x)+1 deg- (y)=deg+(y)+1 Các đỉnh còn lại cân bằng Ví dụ: Đồ thị nào có chu trình Euler, đồ thị nào chỉ có đường đi Euler G1 G2 G3 13
Ví dụ: 1 e2 2 1 e5 6 e7 5 7 e1 e4 e6 e8 3 e3 4 8 G1 G2 -Đồ thị nào có chu trình Euler, đồ thị nào có đường đi Euler G3 -Tìm đường đi Euler, chu trình Euler (nếu có) trong mỗi đồ thị 14
Bài tập 1 2 6 4 3 5 G H Tìm đường đi và chu trình Euler (nếu có) trong các đồ thị trên? 15
Bài tập  Tìm chu trình Euler trên đồ thị được cho bởi ma trận kề 16
Thuật toán tìm 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. 17
Ví dụ tìm chu trình Euler 1 1 2 3 4 5 6 1 0 1 1 0 0 0 2 3 2 1 0 1 1 1 0 3 1 1 0 1 0 1 4 4 0 1 1 0 0 0 5 0 1 0 0 0 1 5 6 6 0 0 1 0 1 0 C = Ø, v = 1 18
Ví dụ tìm chu trình Euler 1 1 2 3 4 5 6 1 0 0 1 0 0 0 2 3 2 0 0 1 1 1 0 3 1 1 0 1 0 1 4 4 0 1 1 0 0 0 5 0 1 0 0 0 1 5 6 6 0 0 1 0 1 0 C = 1,2 19
Ví dụ tìm chu trình Euler 1 1 2 3 4 5 6 1 0 0 1 0 0 0 2 3 2 0 0 0 1 1 0 3 1 0 0 1 0 1 4 4 0 1 1 0 0 0 5 0 1 0 0 0 1 5 6 6 0 0 1 0 1 0 C = 1,2,3 20