Lý thuyết đô thị - Chương 3: Đồ thị euler và đồ thị hamilton

Chương 3Đồ thị Euler và đồ thị HamiltonPhần 3.1.Đồ thị EulerBài toán 7 cái cầu ở TP Konigsberg*Graph Theory*ABCDBài toán 7 cái cầu ở Tp. Konigsberg*Graph Theory*ABCDABDCMô 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ẽ)*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ẽ)*Lý thuyết đồ thị*Đường đi, chu trình EulerXé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 5d2: 1 2 4 3 2 5 1 4 5*Lý thuyết đồ thị*12345Đườ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 1d2: 1 2 4 3 2 5 1 4 5 6 1*Lý thuyết đồ thị*123465Đồ thị EulerXé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.*Lý thuyết đồ thị*12345123465Đồ 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ẻ.*Lý thuyết đồ thị*Thuật toán xây dựng chu trình EulerThuật toán FleuryBắ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:*Lý thuyết đồ thị*abcdefghĐịnh lý Euler cho đồ thị có hướngĐịnh lý: Xét G là đồ thị có hướng, liên thông mạnh. Khi đó G là đồ thị Euler nếu và chỉ nếu mọi đỉnh của G đều có bán bậc ra bằng bán bậc vào.*Lý thuyết đồ thị*Phần 3.2.Đồ thị HamiltonĐường đi, chu trình HamiltonXét đồ thị G = . Một đường đi trên đồ thị được gọi là đường đi Hamilton nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần.Một chu trình trên đồ thị được gọi là chu trình Hamilton nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần.VD: Đồ thị sau có các đường đi và chu trình Euler là:d1: 1 2 3 4 5d2: 1 5 2 4 3C1: 1 2 3 4 5 1C2: 2 5 1 4 3 2*Lý thuyết đồ thị*12345Đồ thị HamiltonXét đồ thị G = . Đồ thị G được gọi là đồ thị Hamilton nếu và chỉ nếu tồn tại một chu trình Hamilton trong G.Đồ thị G được gọi là đồ thị nửa Hamilton nếu và chỉ nếu tồn tại một đường đi Hamilton trong G.*Lý thuyết đồ thị*12345123465Đồ thị nửa HamiltonĐồ thị Hamilton (hiển nhiên cũng là đồ thị nửa Hamilton).Một số kết quả trên đồ thị HamiltonĐịnh lý (Dirak, 1952). Xét G là đơn đồ thị vô hướng với n đỉnh (n>2). Nếu mỗi đỉnh của G đều có bậc không nhỏ hơn n/2 thì G là đồ thị HamiltonĐịnh lý (Dirak, 1952). Xét G là đơn đồ thị có hướng, liên thông mạnh với n đỉnh. Nếu mọi đỉnh của G đều có bán bậc ra và bán bậc vào không nhỏ hơn n/2 thì G là đồ thị Hamilton*Lý thuyết đồ thị*Một số kết quả trên đồ thị Hamilton (tt)Định lý.Mọi đồ thị đấu loại là nửa HamiltonMọi đồ thị đấu loại, liên thông mạnh là HamiltonĐịnh lý (Ore, 1960). Cho đồ thị G có n đỉnh. Nếu hai đỉnh không kề nhau bất kỳ của G đều có tổng bậc không nhỏ hơn n thì G là đồ thị Hamilton. Nghĩa là:*Lý thuyết đồ thị*Kiểm tra đồ thị Hamilton???Các quy tắc để xác định chu trình Hamilton (H) của đồ thị:Quy tắc 1: Nếu có 1 đỉnh bậc 2 thì hai cạnh của đỉnh này bắt buộc phải nằm trong HQuy tắc 2: Không được có chu trình con (độ dài nhỏ hơn n) trong HQuy tắc 3: Ứng với một đỉnh nào đó, nếu đã chọn đủ 2 cạnh vào H thì phải loại bỏ tất cả các cạnh còn lại (vì không thể chọn thêm)Không có đỉnh cô lập hoặc đỉnh treo nào khi áp dụng quy tắc 3.*Lý thuyết đồ thị*Kiểm tra đồ thị Hamilton (tt)Đồ thị sau đây có Hamilton không?*Lý thuyết đồ thị*123456789