TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị - Bài 2: Đường đi, chu trình Euler

Bài giảng "Lý thuyết đồ thị - Bài 2: Đường đi, chu trình Euler" cung cấp cho người học các kiến thức: Đồ thị Euler, bài toán người phát thư Trung Hoa. Đây là một tài liệu hữu ích dành cho các bạn sinh viên ngành Toán học và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu. | Bài giảng Lý thuyết đồ thị - Bài 2: Đường đi, chu trình Euler Bài 2 Đường đi, chu trình Euler . Đồ thị Euler Bài toán 7 cái cầu ở TP Konigsberg A B D Graph Theory C 03/10/20 3 Bài toán 7 cái cầu ở Tp. Konigsberg A A Mô hình thành B Đồ thị B D D C C 4 Đặ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ẽ) Không vẽ được bằng 1 nét. Không vẽ được bằng 1 nét. Tối thiểu phải vẽ bằng 2 nét. Tối thiểu phải vẽ bằng 6 nét. 5 Đặ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ẽ) 6 Đườ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à: 3 d1: 1 2 3 4 2 5 4 1 5 d2: 1 2 4 3 2 5 1 4 5 2 4 1 5 7 Đường đi, chu trình Euler (tt) VD: Đồ thị sau có các chu trình Euler là: 3 d1: 1 2 3 4 2 5 4 1 5 6 1 d2: 1 2 4 3 2 5 1 4 5 6 1 2 4 1 5 6 8 Đồ 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. 3 3 2 4 2 4 Đồ thị Euler (hiển nhiên cũng là đồ thị nửa Euler). 5 1 5 1 Đồ thị nửa Euler 6 9 Đị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ẻ. 10 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 và xóa luôn đỉnh cô lập, nếu có. Quy tắc 2. Không bao giờ đi qua cầu (cạnh cắt) trừ

• Toán học
• Bài giảng Lý thuyết đồ thị
• Lý thuyết đồ thị
• Chu trình Euler
• Đường đi đồ thị
• Đồ thị Euler
• Bài toán người phát thư Trung Hoa
• 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ị
• Đạ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ị
• 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ị
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Lịch sử của lý thuyết đồ thị
• Ưng dụng của đồ thị
• Tổng quan lý thuyết đồ thị
• Bài toán 7 cái cầu
• 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ề
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Công thức Euler
• Định lý Kuratowski
• Đồ thị không phẳng
• Tô màu đồ thị
• Bài toán lý thuyết đồ thi
• Bài toán lý thuyết đồ thị
• Bất đẳng thức EV
• Biểu diễn đồ thị
• Bậc của đỉnh
• Định nghĩa đồ thị
• Bài tập đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Đồ thị Haminton
• Cây khung của đồ thị
• Đồ thị đẳng cấu
• Đồ thị tổng vành; Đồ thị đơn giản
• Đồ thị liên thông
• Dạng đồ thị đặc biệt
• Chu trình của đồ thị
• Chiều sâu trên đồ thị
• Chiều rộng trên đồ thị
• Tìm kiếm chiều rộng trên đồ thị
• Tìm kiếm trên đồ thị
• Đồ thị hữu hạn
• Đẳng cấu đồ thị
• Các dạng đồ thị
• Toán ứng dụng