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.
Nội dung trích xuất từ tài liệ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 2.1. Đồ 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ừ phi không còn cách nào khác.  VD: Tìm chu trình Euler trong đồ thị sau: a b c d h g f e 11 Thuật toán xây dựng chu trình Euler  Gọi chu trình Euler cần tìm là C. Thuật toán sẽ tiến hành theo các bước sau:  Khởi tạo: Chọn một đỉnh bất kỳ cho vào C.  Lặp trong khi G vẫn còn cạnh  Chọn cạnh e nối đỉnh vừa chọn với một đỉnh kề với nó theo nguyên tắc: chỉ chọn cầu nếu không còn cạnh nào khác để chọn.  Bổ sung e và đỉnh cuối của nó vào C.  Xóa e khỏi G. Sau đó xoá đỉnh cô lập (nếu có). 12 Ví dụ 13 Ví dụ (tt)  Xuất phát từ u, ta có thể đi theo cạnh (u, v) hoặc (u, x), giả sử là (u, v) (xoá (u,v)). Từ v có thể đi qua một trong các cạnh (v, w), (v, x), (v, t), giả sử (v, w) (xoá (v,w)). Tiếp tục, có thể đi theo một trong các cạnh (w, s), (w, y), (w, z), giả sử (w, s) (xoá (w, s)).  Đi theo cạnh (s, y) (xoá (s, y) và s). Vì (y, x) là cầu nên có thể đi theo một trong hai cạnh (y, w), (y, z), giả sử (y, w) (xoá (y, w)). Đi theo (w, z) (xoá (w, z) và w) và theo (z, y) (xoá (z, y) và z). Tiếp tục đi theo cạnh (y, x) (xoá (y, x) và y). Vì (x, u) là cầu nên đi theo cạnh (x, v) hoặc (x, t), giả sử (x ...