tailieunhanh - Chương 3 Đồ thị Euler và đồ thị Hamilton

Tham khảo tài liệu 'chương 3 đồ thị euler và đồ thị hamilton', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chương 3 Đồ thị Euler và đồ thị Hamilton Giảng viên: Nguyen Ngoc Trung Phần . Đồ thị Euler Giảng viên: Nguyen Ngoc Trung Bài toán 7 cái cầu ở TP Konigsberg 5/13/2020 10:54:47 PM Graph Theory A B C D Bài toán 7 cái cầu ở Tp. Konigsberg 5/13/2020 10:54:47 PM 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/13/2020 10:54:47 PM 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/13/2020 10:54:47 PM 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/13/2020 10:54:47 PM 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/13/2020 10:54:47 PM 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/13/2020 10:54:47 PM 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/13/2020 10:54:47 PM Lý thuyết đồ thị Thuật toán xây dựng chu trình Euler Thuật . | Chương 3 Đồ thị Euler và đồ thị Hamilton Giảng viên: Nguyen Ngoc Trung Phần . Đồ thị Euler Giảng viên: Nguyen Ngoc Trung Bài toán 7 cái cầu ở TP Konigsberg 5/14/2020 12:33:41 AM Graph Theory A B C D Bài toán 7 cái cầu ở Tp. Konigsberg 5/14/2020 12:33:41 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 12:33:41 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 12:33:41 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