TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị: Chương 3 - Đồ thị Euler và đồ thị Hamilton

Bài giảng Lý thuyết đồ thị: Chương 3 - Đồ thị Euler và đồ thị Hamilton sau đây bao gồm hai phần trình bày về đồ thị Euler; đồ thị Hamilton. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này. Với các bạn chuyên ngành Toán học thì đây là bài giảng hữu ích. | Chương 3 Đồ thị Euler và đồ thị Hamilton Phần . Đồ thị Euler Bài toán 7 cái cầu ở TP Konigsberg 5/14/2020 4:49:36 AM Graph Theory A B C D Bài toán 7 cái cầu ở Tp. Konigsberg 5/14/2020 4:49:36 AM Graph Theory A B C D A B D C Mô hình thành Đồ thị Đặt vấn đề (tt) Hãy vẽ các hình sau bằng đúng một nét bút (không được nhấc bút lên trong khi vẽ) 5/14/2020 4:49:36 AM Lý thuyết đồ thị Không vẽ được bằng 1 nét. Tối thiểu phải vẽ bằng 2 nét. Không vẽ được bằng 1 nét. Tối thiểu phải vẽ bằng 6 nét. Đặt vấn đề (tt) Hãy vẽ các hình sau bằng đúng một nét bút (không được nhấc bút lên trong khi vẽ) 5/14/2020 4:49:36 AM Lý thuyết đồ thị Đường đi, chu trình Euler Xét đồ thị G = . Một đường đi trên đồ thị được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh, mỗi cạnh một lần. Một chu trình trên đồ thị được gọi là chu trình Euler nếu nó đi qua tất cả các cạnh, mỗi cạnh một lần. VD: Đồ thị sau có các đường đi Euler là: d1: 1 2 3 4 2 5 4 1 5 d2: 1 2 4 3 2 5 1 4 5 5/14/2020 4:49:36 AM Lý thuyết đồ thị 1 2 3 4 5 Đường đi, chu trình Euler (tt) VD: Đồ thị sau có các chu trình Euler là: d1: 1 2 3 4 2 5 4 1 5 6 1 d2: 1 2 4 3 2 5 1 4 5 6 1 5/14/2020 4:49:36 AM Lý thuyết đồ thị 1 2 3 4 6 5 Đồ thị Euler Xét đồ thị G = . Đồ thị G được gọi là đồ thị Euler nếu và chỉ nếu tồn tại một chu trình Euler trong G. Đồ thị G được gọi là đồ thị nửa Euler nếu và chỉ nếu tồn tại một đường đi Euler trong G. 5/14/2020 4:49:36 AM Lý thuyết đồ thị 1 2 3 4 5 1 2 3 4 6 5 Đồ thị nửa Euler Đồ thị Euler (hiển nhiên cũng là đồ thị nửa Euler). Định lý Euler Định lý. Đồ thị vô hướng, liên thông G là đồ thị Euler nếu và chỉ nếu mọi đỉnh của nó đều có bậc chẵn. Hệ quả. Đồ thị vô hướng, liên thông G là đồ thị nửa Euler nếu và chỉ nếu nó có không quá hai đỉnh bậc lẻ. 5/14/2020 4:49:36 AM Lý thuyết đồ thị Thuật toán xây dựng chu trình Euler Thuật toán Fleury Bắt đầu từ một đỉnh bất kỳ của đồ thị và tuân theo các quy tắc sau: Quy tắc 1. Khi đi qua một cạnh nào đó thì xóa nó đi

• Toán học
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị