tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 7 - PGS.TS. Hoàng Chí Thành

Bài giảng Lý thuyết đồ thị: Chương 7 Chu trình euler và Chu trình hamilton, cung cấp cho người đọc những kiến thức như: Chu trình Euler; Điều kiện tồn tại chu trình Euler; Chu trình Hamilton; Điều kiện tồn tại chu trình Hamilton. Mời các bạn cùng tham khảo! | CHƯƠNG 7 CHU TRÌNH EULER VÀ CHU TRÌNH HAMILTON 1 55 NỘI DUNG Chu trình Euler Điều kiện tồn tại chu trình Euler Chu trình Hamilton Điều kiện tồn tại chu trình Hamilton 2 55 . CHU TRÌNH EULER Bài toán 7 cây cầu Định nghĩa chu trình Euler Điều kiện tồn tại chu trình Euler vô hướng Điều kiện tồn tại chu trình Euler có hướng Thuật toán tìm chu trình Euler 3 55 BÀI TOÁN 7 CÂY CẦU Sông Pregel và cù lao Kneiphof chia thành phố Konigsberg ở nước CH Litva thành 4 vùng đất. 7 cây cầu nối giữa các vùng đất. B A D Pregel C 4 55 BÀI TOÁN 7 CÂY CẦU tiếp Bài toán Liệu có thể đi qua cả 7 cây cầu mỗi cầu đúng một lần rồi quay về chỗ xuất phát được hay không Bài toán đã làm say mê cư dân của thành phố. Họ háo hức đi thử nhưng không thành công. 5 55 BÀI TOÁN 7 CÂY CẦU tiếp Năm 1736 đã chứng minh rằng bài toán không giải được. Từ bài toán này đưa đến các khái niệm về đường và chu trình Euler. 6 55 BÀI TOÁN 7 CÂY CẦU tiếp Biểu diễn mỗi vùng đất bằng một đỉnh của một đa đồ thị vô hướng hai đỉnh có cạnh nối nếu có cầu nối tương ứng. Bài toán trên đưa về việc tìm một chu trình của đồ thị đi qua mỗi cạnh của đồ thị đúng một lần. b a d c 7 55 ĐƯỜNG VÀ CHU TRÌNH EULER Định nghĩa - Đường Euler của đa đồ thị là đường đi qua mỗi cạnh của đồ thị đúng một lần. - Chu trình Euler của đa đồ thị là đường đi qua mỗi cạnh của đồ thị đúng một lần. 8 55 VÍ DỤ 7 a b 1 3 2 4 6 e 9 10 8 d c 5 Chu trình Euler E 1 2 3 4 5 8 9 10 6 7 9 55 . ĐIỀU KIỆN TỒN TẠI CHU TRÌNH EULER VÔ HƯỚNG Định lý Đa đồ thị G có chu trình vô hướng Euler khi và chỉ khi mọi đỉnh đều có bậc chẵn. 4 3 5 1 6 2 8 7 9 10 55 . ĐIỀU KIỆN TỒN TẠI CHU TRÌNH EULER VÔ HƯỚNG tiếp Chứng minh định lý 1 Điều kiện cần Mỗi lần chu trình đi qua một đỉnh thì đỉnh đó bớt đi 2 cạnh kề. Cuối cùng số cạnh kề của mỗi đỉnh bằng 0. Vì vậy số cạnh kề của mỗi đỉnh phải là một số chẵn. 11 55 . ĐIỀU KIỆN TỒN TẠI CHU TRÌNH EULER VÔ HƯỚNG tiếp Chứng minh định lý 2 Điều kiện đủ Xuất phát từ đỉnh a bất kỳ lập dãy cạnh kề liên tiếp cho .