tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 2 - ThS. Nguyễn Khắc Quốc

Bài giảng Lý thuyết đồ thị: Chương 2 Đồ thị Euler và đồ thị Hamilton trình bày về đường đi Euler và đồ thị Hamilton, định nghĩa đồ thị Euler và đồ thị Hamilton, định lý đồ thị Euler và đồ thị giảng trình bày khoa học và súc tích giúp các bạn hiểu thêm về đồ thị Euler và đồ thị Hamilton. | CHƯƠNG 2 ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON Ths. Nguyên Khắc Quốc Tra Vinh University 1 . ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ EULER. Năm 1736 là năm khai sinh lý thuyết đồ thị -Với việc công bố lời giải bài toán về các cầu ở Konigsberg của nhà toán học lỗi lạc Euler 1707-1783 . - Thành phố Konigsberg thuộc Phổ nay gọi là Kaliningrad thuộc Nga được chia thành 4 vùng bằng các nhánh sông Pregel các vùng này gồm hai vùng bên bờ sông đảo Kneiphof và một miền nằm giữa hai nhánh của sông Pregel. Vào thế kỷ 18 người ta xây bảy chiếc cầu nối các vùng này với nhau. ThS. Nguyên Khắc Quốc 2 . ĐƯỜNG ĐI EULER VÀ ĐỒ THI EULER. - D A C Nếu ta coi mỗi khu vực A B C D như một đỉnh và mỗi cầu qua lại hai khu vực là một cạnh nối hai đỉnh thì ta có sơ đồ của Konigsberg là một đa đồ thị G như hình trên. Bài toán tìm đường đi qua tất cả các cầu mỗi cầu chỉ qua một lần có thể được phát biểu lại bằng mô hình này như sau Có tồn tại chu trình đơn trong đa đồ thị G chứa tất cả các cạnh ThS. Nguyên Khắc Quốc