TAILIEUCHUNG - Giáo trình lý thuyết đồ thị - Bài 12

Chu trình euler và chu trình hamilton Chu trình Euler và chu trình Hamilton là hai loại chu trình rất nổi tiếng trong Lý thuyết Đồ thị, mà tên gọi của chúng gắn với tên của các nhà khoa học tìm ra nó. Không những thế, chúng còn nổi tiếng vì một số bài toán liên quan vẫn còn là những bài toán mở. | BÀI 12 Chương 7 Chu trình euler và chu trình hamilton Chu trình Euler và chu trình Hamilton là hai loại chu trình rất nổi tiếng trong Lý thuyết Đồ thị mà tên gọi của chúng gắn với tên của các nhà khoa học tìm ra nó. Không những thế chúng còn nổi tiếng vì một số bài toán liên quan vẫn còn là những bài toán mở. . Chu trình Euler Khái niệm chu trình Euler được ra đời từ bài toán nổi tiếng sau đây. Ví dụ Bài toán 7 cây cầu ở Konigsberg Thành phố Konigsberg thuộc nước Cộng hoà Litva có con sông Pregel chảy qua giữa sông có cù lao Kneiphof tạo nên bốn vùng đất. Người ta đã xây dựng 7 cây cầu để nối các vùng đất này lại với nhau như hình vẽ dưới đây. Hình . Bảy cây cầu trên sông Pregel Năm 1736 L. Euler nhà toán học người Thuỵ sĩ đã đưa ra bài toán sau đây Hỏi có thể đi qua cả 7 cây cầu mỗi cầu chỉ đi qua một lần rồi quay trở về đúng 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. Sau đó chính L. Euler đã chứng minh được rằng bài toán trên là không giải được. Nếu biểu diễn mỗi vùng đất A B C D bằng đỉnh của một đa đồ thị vô hướng và có cạnh nối giữa chúng nếu có cầu nối tương ứng thì bài toán trên đưa về việc tìm một chu trình đi qua mỗi cạnh của đồ thị đúng một lần. Hình . Đa đồ thị biểu diễn thành phố Konigsberg Từ bài toán trên người ta đã đưa ra các khái niệm sau đây Đị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à chu trình đi qua mỗi cạnh của đồ thị đúng một lần. Từ định nghĩa trên ta có điều kiện cần và đủ cho sự tồn tại của chu trình vô hướng Euler như sau. Định lý Đa đồ thị liên thông G có chu trình vô hướng Euler khi và chỉ khi mỗi đỉnh đều có bậc chẵn. Chứng minh Mỗi lần chu trình đi qua một đỉnh thì đỉnh đó bớt đi hai cạnh kề. Cuối cùng số cạnh kề của mỗi đỉnh bằng 0. Do đó số cạnh kề với mỗi đỉnh phải là một số chẵn. Xuất phát từ một đỉnh a nào đó ta lập dãy cạnh kề liên tiếp cho đến khi hết khả năng .

• Toán học
• Chu trình Hamilton
• thuật toán
• đồ thị
• ứng dụng cây
• hàm trên đồ thị
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton